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