For a ∈ Z, de¬ne aZ := {az : z ∈ Z}; that is, aZ is the set of all integer

multiples of a. It is easy to see that aZ is an ideal: for az, az ∈ aZ and

z ∈ Z, we have az + az = a(z + z ) ∈ aZ and (az)z = a(zz ) ∈ aZ. The

set aZ is called the ideal generated by a, and any ideal of the form aZ

for some a ∈ Z is called a principal ideal.

We observe that for all a, b ∈ Z, we have a ∈ bZ if and only if b | a.

We also observe that for any ideal I, we have a ∈ I if and only if aZ ⊆ I.

Both of these observations are simple consequences of the de¬nitions, as the

reader may verify. Combining these two observations, we see that aZ ⊆ bZ

if and only if b | a.

We can generalize the above method of constructing ideals. For

1.2 Ideals and greatest common divisors 5

a1 , . . . , ak ∈ Z, de¬ne

a1 Z + · · · + ak Z := {a1 z1 + · · · + ak zk : z1 , . . . , zk ∈ Z}.

That is, a1 Z + · · · + ak Z consists of all linear combinations, with integer

coe¬cients, of a1 , . . . , ak . We leave it to the reader to verify that a1 Z + · · · +

ak Z is an ideal and contains a1 , . . . , ak ; it is called the ideal generated by

a1 , . . . , ak . In fact, this ideal is the “smallest” ideal containing a1 , . . . , ak , in

the sense that any other ideal that contains a1 , . . . , ak must already contain

this ideal (verify).

Example 1.1. Let a := 3 and consider the ideal aZ. This consists of all

integer multiples of 3; that is, aZ = {. . . , ’9, ’6, ’3, 0, 3, 6, 9, . . .}. 2

Example 1.2. Let a1 := 3 and a2 := 5, and consider the ideal a1 Z + a2 Z.

This ideal contains 2a1 ’ a2 = 1. Since it contains 1, it contains all integers;

that is, a1 Z + a2 Z = Z. 2

Example 1.3. Let a1 := 4 and a2 := 6, and consider the ideal a1 Z + a2 Z.

This ideal contains a2 ’ a1 = 2, and therefore, it contains all even integers.

It does not contain any odd integers, since the sum of two even integers is

again even. 2

The following theorem says that all ideals of Z are principal.

Theorem 1.5. For any ideal I ⊆ Z, there exists a unique non-negative

integer d such that I = dZ.

Proof. We ¬rst prove the existence part of the theorem. If I = {0}, then

d = 0 does the job, so let us assume that I = {0}. Since I contains non-zero

integers, it must contain positive integers, since if z ∈ I then so is ’z. Let

d be the smallest positive integer in I. We want to show that I = dZ.

We ¬rst show that I ⊆ dZ. To this end, let c be any element in I. It

su¬ces to show that d | c. Using the division with remainder property, write

c = qd + r, where 0 ¤ r < d. Then by the closure properties of ideals, one

sees that r = c ’ qd is also an element of I, and by the minimality of the

choice of d, we must have r = 0. Thus, d | c.

We next show that dZ ⊆ I. This follows immediately from the fact that

d ∈ I and the closure properties of ideals.

That proves the existence part of the theorem. As for uniqueness, note

that if dZ = d Z, we have d | d and d | d, from which it follows by

Theorem 1.2 that d = ±d. 2

For a, b ∈ Z, we call d ∈ Z a common divisor of a and b if d | a and

6 Basic properties of the integers

d | b; moreover, we call such a d a greatest common divisor of a and b if

d is non-negative and all other common divisors of a and b divide d.

Theorem 1.6. For any a, b ∈ Z, there exists a unique greatest common

divisor d of a and b, and moreover, aZ + bZ = dZ.

Proof. We apply the previous theorem to the ideal I := aZ + bZ. Let d ∈ Z

with I = dZ, as in that theorem. We wish to show that d is a greatest

common divisor of a and b. Note that a, b, d ∈ I and d is non-negative.

Since a ∈ I = dZ, we see that d | a; similarly, d | b. So we see that d is a

common divisor of a and b.

Since d ∈ I = aZ + bZ, there exist s, t ∈ Z such that as + bt = d. Now

suppose a = a d and b = b d for a , b , d ∈ Z. Then the equation as + bt = d

implies that d (a s + b t) = d, which says that d | d. Thus, any common

divisor d of a and b divides d.

That proves that d is a greatest common divisor of a and b. As for

uniqueness, note that if d is a greatest common divisor of a and b, then

d | d and d | d, and hence d = ±d, and the requirement that d is

non-negative implies that d = d. 2

For a, b ∈ Z, we denote by gcd(a, b) the greatest common divisor of a and

b. Note that as we have de¬ned it, gcd(a, 0) = |a|. Also note that when at

least one of a or b are non-zero, gcd(a, b) is the largest positive integer that

divides both a and b.

An immediate consequence of Theorem 1.6 is that for all a, b ∈ Z, there

exist s, t ∈ Z such that as + bt = gcd(a, b), and that when at least one of

a or b are non-zero, gcd(a, b) is the smallest positive integer that can be

expressed as as + bt for some s, t ∈ Z.

We say that a, b ∈ Z are relatively prime if gcd(a, b) = 1, which is

the same as saying that the only common divisors of a and b are ±1. It is

immediate from Theorem 1.6 that a and b are relatively prime if and only

if aZ + bZ = Z, which holds if and only if there exist s, t ∈ Z such that

as + bt = 1.

Theorem 1.7. For a, b, c ∈ Z such that c | ab and gcd(a, c) = 1, we have

c | b.

Proof. Suppose that c | ab and gcd(a, c) = 1. Then since gcd(a, c) = 1, by

Theorem 1.6 we have as+ct = 1 for some s, t ∈ Z. Multiplying this equation

by b, we obtain

abs + cbt = b. (1.2)

1.2 Ideals and greatest common divisors 7

Since c divides ab by hypothesis, and since c clearly divides cbt, it follows

that c divides the left-hand side of (1.2), and hence that c divides b. 2

As a consequence of this theorem, we have:

Theorem 1.8. Let p be prime, and let a, b ∈ Z. Then p | ab implies that

p | a or p | b.

Proof. Assume that p | ab. The only divisors of p are ±1 and ±p. Thus,

gcd(p, a) is either 1 or p. If p | a, we are done; otherwise, if p a, we must

have gcd(p, a) = 1, and by the previous theorem, we conclude that p | b. 2

An obvious corollary to Theorem 1.8 is that if a1 , . . . , ak are integers,

and if p is a prime that divides the product a1 · · · ak , then p | ai for some

i = 1, . . . , k. This is easily proved by induction on k. For k = 1, the

statement is trivially true. Now let k > 1, and assume that statement holds

for k ’ 1. Then by Theorem 1.8, either p | a1 or p | a2 · · · ak’1 ; if p | a1 , we

are done; otherwise, by induction, p divides one of a2 , . . . , ak’1 .

We are now in a position to prove the uniqueness part of Theorem 1.3,

which we can state as follows: if p1 , . . . , pr and p1 , . . . , ps are primes (with

duplicates allowed among the pi and among the pj ) such that

p 1 · · · p r = p 1 · · · ps , (1.3)

then (p1 , . . . , pr ) is just a reordering of (p1 , . . . , ps ). We may prove this by

induction on r. If r = 0, we must have s = 0 and we are done. Now suppose

r > 0, and that the statement holds for r ’ 1. Since r > 0, we clearly must

have s > 0. Also, as p1 is obviously divides the left-hand side of (1.3), it

must also divide the right-hand side of (1.3); that is, p1 | p1 · · · ps . It follows

from (the corollary to) Theorem 1.8 that p1 | pj for some j = 1, . . . , s, and

indeed, since pi and pj are both prime, we must have pi = pj . Thus, we may

cancel pi from the left-hand side of (1.3) and pj from the right-hand side of

(1.3), and the statement now follows from the induction hypothesis. That

proves the uniqueness part of Theorem 1.3.

Exercise 1.7. Let I be a non-empty set of integers that is closed under

addition, that is, a + b ∈ I for all a, b ∈ I. Show that the condition

’a ∈ I for all a ∈ I

holds if and only if

az ∈ I for all a ∈ I, z ∈ Z.

8 Basic properties of the integers

Exercise 1.8. Let a, b, c be positive integers, with gcd(a, b) = 1 and c ≥ ab.

Show that there exist non-negative integers s, t such that c = as + bt.

Exercise 1.9. Show that for any integers a, b with d := gcd(a, b) = 0, we

have gcd(a/d, b/d) = 1.

1.3 Some consequences of unique factorization

The following theorem is a consequence of just the existence part of Theo-

rem 1.3:

Theorem 1.9. There are in¬nitely many primes.

Proof. By way of contradiction, suppose that there were only ¬nitely many

primes; call them p1 , . . . , pk . Then set n := 1 + k pi , and consider a