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:

    abx+dby=b

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.

Proof

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

Comment

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}

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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