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

In order to prove Euclid's lemma we will first prove another, unnamed, lemma that will become useful later. This additional lemma is

Lemma 1: Suppose p and q are relatively prime integers and that p|kq for some integer k. Then p|k.

Proof: Because p and q are relatively prime, the Euclidean Algorithm tells us that there exist integers r and s such that 1=gcd(p,q)=rp+sq. Next, since p|kq there exists some integer n such that np=kq. Now write

k=(rp+sq)k = rpk + s(kq) = rpk + snp = p(rk+sn).

Since rk+sn is an integer, this shows that p|k as desired.

Now we can prove Euclid's lemma. Let a, b, p $\in \mathbb {Z}$ with p prime, and suppose that p is a divisor of ab, p|ab. Now let g=gcd(a,p). Since p is prime and g divides it, then either g=p or g=1. In the first case, p divides a by the definition of the gcd, so we are done. In the second case we have that a and p are relatively prime and that p|ba so by the Lemma 1, p divides b. Thus in either case p divides (at least) one of a and b. Note that is is of course possible for p to divide both a and b, the simplest example of which is the case a=b=p.