Euclid's lemma

From Citizendium, the Citizens' Compendium

	Main Article	Talk	Related Articles  [?]	Bibliography  [?]	External Links  [?]
	This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer. [edit intro]

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 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.