20 Chapter 3

Next, we prove B

´

ezout’s identity. Recall from chapter 1 that integers are relatively prime

if they have no common factor larger than 1.

Lemma 12 (B

´

ezout’s identity). If integers a and b are relatively prime, then there are

integers x and y for which 1 = ax + by.

Proof. Assume that integers a and b are relatively prime. Let d be the smallest positive

integer that is expressible as an integer linear combination of a and b, that is, as d = ax +by

for some choice of integers x and y. Certainly d ≤ a, since we can write a = a · 1 + b · 0.

I claim that d divides both a and b. To see this, apply the Euclidean algorithm to express

a = kd + r for some integer k and remainder r, with 0 ≤ r < d.

Putting our equations together, observe that

r = a − kd = a − k(ax + by) = (1 −kx)a + (−ky)

b.

We have therefore expressed r as an integer linear combination of a and b. Since r < d and

d was the smallest positive such combination, it follows that r must be 0. In other words,

a = kd is a multiple of d, as claimed. A similar argument shows that b also is a multiple

of d, and so d is a common factor of a and b. Since these numbers are relatively prime, it

must be that d = 1, and so we have achieved 1 = ax + by, as desired.

Lemma 13 (Euclid’s lemma). If p is prime and p divides ab in the integers, then p divides

a or p divides b.

Proof. Assume that p is prime and that p divides ab.Ifp does not divide a, then a and

p must be relatively prime, since there are no other nontrivial factors of p.ByB

´

ezout’s

lemma (lemma 12), it follows that 1 = ax+ py for some integers x and y. Multiplying both

sides by b, we see that

b = abx + pby.

Since p divides ab, it follows that p divides the right-hand side of this equation, and so p

divides b. So we have proved that if p does not divide a, then it divides b. And so p must

divide one of them.

We can generalize lemma 13 to the situation of many primes:

Lemma 14. If a prime p divides a product of integers n

1

n

2

···n

k

, then p divides some n

i

.

Proof. We know by lemma 13 that this lemma is true when there are only two factors.

Suppose that this lemma holds when there are fewer than k factors, and that we have a

prime number p that divides a product n

1

·n

2

···n

k

with k factors. The trick is to look upon

the product n

1

n

2

···n

k

as a product of just two things, like this: n

1

· (n

2

···n

k

). Since p

divides this product of two things, we may conclude by lemma 13 that either p divides n

1

or p divides the rest of the product n

2

···n

k

. In the first case, we are done immediately, and