# If a prime divides a product it divides one of the factors

If a prime $\displaystyle{ p }$ divides a product $\displaystyle{ ab }$ it also divides either $\displaystyle{ a }$ or $\displaystyle{ b }$, also called Euclid's lemma, is a classic result in number theory.

## Proof

Suppose $\displaystyle{ p }$ divides $\displaystyle{ ab }$ but doesn't divide $\displaystyle{ b }$. Then $\displaystyle{ p }$ and $\displaystyle{ b }$ are co-prime, so their greatest common divisor is one. Bézout's lemma ensures that there are integers $\displaystyle{ x\text{, }y }$ such that $\displaystyle{ px + by = 1 }$. Multiplying both sides with $\displaystyle{ a }$ we get $\displaystyle{ apx+aby=a }$. Since $\displaystyle{ p }$ divides $\displaystyle{ ab }$ there is an integer $\displaystyle{ z }$ such that $\displaystyle{ ab=pz }$.

So the equation becomes $\displaystyle{ pax+pzy=a \Rightarrow p\left(ax+zy\right)=a }$, showing that $\displaystyle{ p }$ divides $\displaystyle{ a }$ which proves the assertion.

 Statement of the claim If a prime divides a product it divides one of the factors Level of certainty Proven Nature Theoretical Counterclaim Dependent on Dependency of