Euclid’s Lemma

This post presents a proof of a lemma that is called Euclid’s lemma, which is one of the fundamental properties of prime numbers. Euclid’s lemma is the statement that if a prime number divides a product of two integers, it must divide one of the factors.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

We first state all the tools that we need. The notation a \ \lvert \ b refers to the condition that a divides b. The notation \text{GCD}(a,b) refers to the greatest common divisor (GCD) of a and b.


Extended Euclidean Algorithm

Let a and b be integers. Let d be the greatest common divisor of a and b. Then there exist integers x and y such that ax+by=d.

The extended Euclidean algorithm is discussed in this post.


Lemma 1

If d \ \lvert \ a \cdot b and \text{GCD}(d,a)=1, then d \ \lvert \ b.

Proof of Lemma 1

Suppose that d \ \lvert \ a \cdot b and \text{GCD}(d,a)=1. According to the extended Euclidean algorithm, for some integers x and y, we have ax+dy=1. Multiplying both sides by b, we have:


Since d divides each term in the left-hand side of this equation, d \ \lvert \ b. \blacksquare


Euclid’s Lemma

If p is a prime number and p \ \lvert (a \cdot b), then p \ \lvert \ a or p \ \lvert \ b.


If p \ \lvert \ a, then we are done. So assume p \not \lvert \ a, which implies that \text{GCD}(p,a)=1. If \text{GCD}(p,a)>1, \text{GCD}(p,a)=p, which implies that p \ \lvert \ a. Note that the only positive divisors of p are 1 and p. By Lemma 1, p \ \lvert \ b. \blacksquare


We would like to point out that the assumption that p is prime is essential in Euclid’s lemma. Note that 8 \ \lvert \ (4 \cdot 4) and 8 \not \lvert \ 4.


\copyright \ 2013 \text{ by Dan Ma}


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s