Basic properties of the integers

This chapter discusses some of the basic properties of the integers, including

the notions of divisibility and primality, unique factorization into primes,

greatest common divisors, and least common multiples.

1.1 Divisibility and primality

Consider the integers Z := {. . . , ’2, ’1, 0, 1, 2, . . .}. For a, b ∈ Z, we say

that b divides a, or alternatively, that a is divisible by b, if there exists

c ∈ Z such that a = bc. If b divides a, then b is called a divisor of a, and

we write b | a. If b does not divide a, then we write b a.

We ¬rst state some simple facts:

Theorem 1.1. For all a, b, c ∈ Z, we have

(i) a | a, 1 | a, and a | 0;

(ii) 0 | a if and only if a = 0;

(iii) a | b and a | c implies a | (b + c);

(iv) a | b implies a | ’b;

(v) a | b and b | c implies a | c.

Proof. These properties can be easily derived from the de¬nition using ele-

mentary facts about the integers. For example, a | a because we can write

a = a · 1; 1 | a because we can write a = 1 · a; a | 0 because we can write

0 = a·0. We leave it as an easy exercise for the reader to verify the remaining

properties. 2

Another simple but useful fact is the following:

Theorem 1.2. For all a, b ∈ Z, we have a | b and b | a if and only if a = ±b.

1

2 Basic properties of the integers

Proof. Clearly, if a = ±b, then a | b and b | a. So let us assume that a | b and

b | a, and prove that a = ±b. If either of a or b are zero, then part (ii) of the

previous theorem implies that the other is zero. So assume that neither is

zero. Now, b | a implies a = bc for some c ∈ Z. Likewise, a | b implies b = ad

for some d ∈ Z. From this, we obtain b = ad = bcd, and canceling b from

both sides of the equation b = bcd, we obtain 1 = cd. The only possibility

is that either c = d = ’1, in which case a = ’b, or c = d = 1, in which case

a = b. 2

Any integer n is trivially divisible by ±1 and ±n. We say that an integer

p is prime if p > 1 and the only divisors of p are the trivial divisors ±1

and ±p. Conversely, an integer n is called composite if n > 1 and it is

not prime. So an integer n > 1 is composite if and only if n = ab for some

integers a, b with 1 < a < n and 1 < b < n. The ¬rst few primes are

2, 3, 5, 7, 11, 13, 17, . . . .

The number 1 is not considered to be either prime or composite. Also, we

do not consider the negative of a prime (e.g., ’2) to be prime (although one

can, and some authors do so).

A basic fact is that any non-zero integer can be expressed as a signed

product of primes in an essentially unique way. More precisely:

Theorem 1.3 (Fundamental theorem of arithmetic). Every non-zero

integer n can be expressed as

n = ±pe1 · · · per ,

r

1

where the pi are distinct primes and the ei are positive integers. Moreover,

this expression is unique, up to a reordering of the primes.

Note that if n = ±1 in the above theorem, then r = 0, and the product

of zero terms is interpreted (as usual) as 1.

To prove this theorem, we may clearly assume that n is positive, since

otherwise, we may multiply n by ’1 and reduce to the case where n is

positive.

The proof of the existence part of Theorem 1.3 is easy. This amounts

to showing that every positive integer n can be expressed as a product

(possibly empty) of primes. We may prove this by induction on n. If n = 1,

the statement is true, as n is the product of zero primes. Now let n > 1,

and assume that every positive integer smaller than n can be expressed as

a product of primes. If n is a prime, then the statement is true, as n is the

1.1 Divisibility and primality 3

product of one prime; otherwise, n is composite, and so there exist a, b ∈ Z

with 1 < a < n, 1 < b < n, and n = ab; by the induction hypothesis, both a

and b can be expressed as a product of primes, and so the same holds for n.

The uniqueness part of Theorem 1.3 is by no means obvious, and most

of the rest of this section and the next section are devoted to developing a

proof of this. We give a quite leisurely proof, introducing a number of other

very important tools and concepts along the way that will be useful later.

An essential ingredient in this proof is the following:

Theorem 1.4 (Division with remainder property). For a, b ∈ Z with

b > 0, there exist unique q, r ∈ Z such that a = bq + r and 0 ¤ r < b.

Proof. Consider the set S of non-negative integers of the form a ’ zb with

z ∈ Z. This set is clearly non-empty, and so contains a minimum. Let r be

the smallest integer in this set, with r = a ’ qb for q ∈ Z. By de¬nition,

we have r ≥ 0. Also, we must have r < b, since otherwise, we would have

0 ¤ r ’ b < r and r ’ b = a ’ (q + 1)b ∈ S, contradicting the minimality of

r.

That proves the existence of r and q. For uniqueness, suppose that a =

bq + r and a = bq + r , where 0 ¤ r < b and 0 ¤ r < b. Then subtracting

these two equations and rearranging terms, we obtain

r ’ r = b(q ’ q ). (1.1)

Now observe that by assumption, the left-hand side of (1.1) is less than b in

absolute value. However, if q = q , then the right-hand side of (1.1) would

be at least b in absolute value; therefore, we must have q = q . But then by

(1.1), we must have r = r . 2

In the above theorem, it is easy to see that q = a/b , where for any real

number x, x denotes the greatest integer less than or equal to x. We shall

write r = a mod b; that is, a mod b denotes the remainder in dividing a by

b. It is clear that b | a if and only if a mod b = 0.

One can generalize the notation a mod b to all integers a and b, with b = 0:

we de¬ne a mod b := a ’ bq, where q = a/b .

In addition to the “¬‚oor” function · , the “ceiling” function · is also

useful: for any real number x, x is de¬ned as the smallest integer greater

than or equal to x.

Exercise 1.1. Let n be a composite integer. Show that there exists a prime

p dividing n, such that p ¤ |n|1/2 .

4 Basic properties of the integers

Exercise 1.2. For integer n and real x, show that n ¤ x if and only if

n¤ x .

Exercise 1.3. For real x and positive integer n, show that x /n = x/n .

In particular, for positive integers a, b, c, a/b /c = a/(bc) .

Exercise 1.4. For real x, show that 2 x ¤ 2x ¤ 2 x + 1.

Exercise 1.5. For positive integers m and n, show that the number of

multiples of m among 1, 2, . . . , n is n/m . More generally, for integer m ≥ 1

and real x ≥ 0, show that the number of multiples of m in the interval [1, x]

is x/m .

Exercise 1.6. For integers a, b with b < 0, show that b < a mod b ¤ 0.

1.2 Ideals and greatest common divisors

To carry on with the proof of Theorem 1.3, we introduce the notion of an

ideal of Z, which is a non-empty set of integers that is closed under addition,

and under multiplication by an arbitrary integer. That is, a non-empty set

I ⊆ Z is an ideal if and only if for all a, b ∈ I and all z ∈ Z, we have

a + b ∈ I and az ∈ I.

Note that for an ideal I, if a ∈ I, then so is ’a, since ’a = a · (’1) ∈ I.

It is easy to see that any ideal must contain 0: since an ideal I must contain

some element a, and by the closure properties of ideals, we must have 0 =

a + (’a) ∈ I. It is clear that {0} and Z are ideals. Moreover, an ideal I is

equal to Z if and only if 1 ∈ I ” to see this, note that 1 ∈ I implies that

for all z ∈ Z, z = 1 · z ∈ I, and hence I = Z; conversely, if I = Z, then in