Euclid's lemma

In number theory, Euclid's lemma, named after the ancient Greek geometer and number theorist Euclid of Alexandria, states that if a prime number p is a divisor of the product of two integers, ab, then either p is a divisor of a or p is a divisor of b (or both).

Euclid's lemma is used in the proof of the unique factorization theorem, which states that a number cannot have more than one prime factorization.

Proof of the lemma

Let a, b, p $\in \mathbb {Z}$ with p prime, and suppose that p is a divisor of ab, p|ab. Then there exists an integer n such that ab = pn. But this means that the fraction

${\frac {ab}{p}}=n$

must be an integer as well. Now, since p is prime the greatest common divisor of p and a is either 1 or p. If it is p then the proof is complete since p|a, so suppose that p does not divide a. In this case we write

$a{\frac {b}{p}}=n\ ,$

and since gcd(a, p) = 1 and n is an integer, b/p must also be an integer, say m. But then b = mp so p divides b.

Therefore in either case we have p dividing (at least) one of a and b, and the proof is complete.