If a prime divides a product it divides one of the factors
If a prime [math]\displaystyle{ p }[/math] divides a product [math]\displaystyle{ ab }[/math] it also divides either [math]\displaystyle{ a }[/math] or [math]\displaystyle{ b }[/math], also called Euclid's lemma, is a classic result in number theory.
Proof
Suppose [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ ab }[/math] but doesn't divide [math]\displaystyle{ b }[/math]. Then [math]\displaystyle{ p }[/math] and [math]\displaystyle{ b }[/math] are co-prime, so their greatest common divisor is one. Bézout's lemma ensures that there are integers [math]\displaystyle{ x\text{, }y }[/math] such that [math]\displaystyle{ px + by = 1 }[/math]. Multiplying both sides with [math]\displaystyle{ a }[/math] we get [math]\displaystyle{ apx+aby=a }[/math]. Since [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ ab }[/math] there is an integer [math]\displaystyle{ z }[/math] such that [math]\displaystyle{ ab=pz }[/math].
So the equation becomes [math]\displaystyle{ pax+pzy=a \Rightarrow p\left(ax+zy\right)=a }[/math], showing that [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ a }[/math] 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 |
|