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.

[edit] 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 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 it is of course possible for p to divide both a and b, the simplest example of which is the case a=b=p.

Some content on this page may previously have appeared on Citizendium.