Notation. The “natural numbers”, which we will denote by N, are

{1, 2, 3, . . . }.

The integers Z are

{. . . , ’2, ’1, 0, 1, 2, . . . }.

We will also use the non-negative integers, denoted either by N0 or Z+ , which is N ∪

{0}. There are also the rational numbers Q and the real numbers R.

Given a set S, we write x ∈ S if x belongs to S, and x ∈ S otherwise.

/

There are operations + and · on Z. They have certain “nice” properties which we

will take for granted. There is also “ordering”. N is said to be “well-ordered”, which

means that every non-empty subset of N has a least element. The principle of induction

follows from well-ordering.

Proposition (Principle of Induction). Let P (n) be a statement about n for each n ∈

N. Suppose P (1) is true and P (k) true implies that P (k + 1) is true for each k ∈ N.

Then P is true for all n.

Proof. Suppose P is not true for all n. Then consider the subset S of N of all numbers

k for which P is false. Then S has a least element l. We know that P (l ’ 1) is true

(since l > 1), so that P (l) must also be true. This is a contradiction and P holds for all

n.

1.1 Division

Given two integers a, b ∈ Z, we say that a divides b (and write a | b) if a = 0 and

b = a · q for some q ∈ Z (a is a divisor of b). a is a proper divisor of b if a is not ±1

or ±b.

Note. If a | b and b | c then a | c, for if b = q1 a and c = q2 b for q1 , q2 ∈ Z then

c = (q1 · q2 )a. If d | a and d | b then d | ax + by. The proof of this is left as an exercise.

1

CHAPTER 1. INTEGERS

2

1.2 The division algorithm

Lemma 1.1. Given a, b ∈ N there exist unique integers q, r ∈ N with a = qb + r,

0 ¤ r < b.

Proof. Take q the largest possible such that qb ¤ a and put r = a’qb. Then 0 ¤ r < b

since a ’ qb ≥ 0 but (q + 1)b ≥ a. Now suppose that a = q1 b + r with q1 , r1 ∈ N and

0 ¤ r1 < b. Then 0 = (q ’ q1 )b + (r ’ r1 ) and b | r ’ r1 . But ’b < r ’ r1 < b so

that r = r1 and hence q = q1 .

It is clear that b | a iff r = 0 in the above.

De¬nition. Given a, b ∈ N then d ∈ N is the highest common factor (greatest common

divisor) of a and b if:

1. d | a and d | b,

2. if d | a and d | b then d | d (d ∈ N).

The highest common factor (henceforth hcf) of a and b is written (a, b) or hcf(a, b).

The hcf is obviously unique ” if c and c are both hcf™s then they both divide each

other and are therefore equal.

Theorem 1.1 (Existance of hcf). For a, b ∈ N hcf(a, b) exists. Moreover there exist

integers x and y such that (a, b) = ax + by.

Proof. Consider the set I = {ax + by : x, y ∈ Z and ax + by > 0}. Then I = … so let

d be the least member of I. Now ∃x0 , y0 such that d = ax0 + by0 , so that if d | a and

d | b then d | d.

Now write a = qd + r with q, r ∈ N0 , 0 ¤ r < d. We have r = a ’ qd =

a(1’qx0 )+b(’qy0 ). So r = 0, as otherwise r ∈ I: contrary to d minimal. Similiarly,

d | b and thus d is the hcf of a and b.

Lemma 1.2. If a, b ∈ N and a = qb + r with q, r ∈ N0 and 0 ¤ r < b then

(a, b) = (b, r).

Proof. If c | a and c | b then c | r and thus c | (b, r). In particular, (a, b) | (b, r). Now

note that if c | b and c | r then c | a and thus c | (a, b). Therefore (b, r) | (a, b) and

hence (b, r) = (a, b).

1.3 The Euclidean algorithm

Suppose we want to ¬nd (525, 231). We use lemmas (1.1) and (1.2) to obtain:

525 = 2 — 231 + 63

231 = 3 — 63 + 42

63 = 1 — 42 + 21

42 = 2 — 21 + 0

So (525, 231) = (231, 63) = (63, 42) = (42, 21) = 21. In general, to ¬nd (a, b):

1.3. THE EUCLIDEAN ALGORITHM 3

a = q1 b + r 1 with 0 < r1 < b

b = q2 r1 + r2 with 0 < r2 < r1

r1 = q3 r2 + r3 with 0 < r3 < r2

.

.

.

ri’2 = qi ri’1 + ri with 0 < ri < ri’1

.

.

.

rn’3 = qn’1 rn’2 + rn’1 with 0 < rn < rn’1

rn’2 = qn rn’1 + 0.

This process must terminate as b > r1 > r2 > · · · > rn’1 > 0. Using Lemma

(1.2), (a, b) = (b, r1 ) = · · · = (rn’2 , rn’1 ) = rn’1 . So (a, b) is the last non-zero

remainder in this process.

We now wish to ¬nd x0 and y0 ∈ Z with (a, b) = ax0 + by0 . We can do this by

backsubstitution.

21 = 63 ’ 1 — 42

= 63 ’ (231 ’ 3 — 63)

= 4 — 63 ’ 231

= 4 — (525 ’ 2 — 231) ’ 231

= 4 — 525 ’ 9 — 231.

This works in general but can be confusing and wasteful. These numbers can be

calculated at the same time as (a, b) if we know we shall need them.

We introduce Ai and Bi . We put A’1 = B0 = 0 and A0 = B’1 = 1. We

iteratively de¬ne

Ai = qi Ai’1 + Ai’2

Bi = qi Bi’1 + Bi’2 .

Now consider aBj ’ bAj .

Lemma 1.3.

aBj ’ bAj = (’1)j+1 rj .

Proof. We shall do this using strong induction. We can easily see that (1.3) holds for

j = 1 and j = 2. Now assume we are at i ≥ 2 and we have already checked that

ri’2 = (’1)i’1 (aBi’2 ’ bAi’2 ) and ri’i = (’1)i (aBi’1 ’ bAi’1 ). Now

ri = ri’2 ’ qi ri’1

= (’1)i’1 (aBi’2 ’ bAi’2 ) ’ qi (’1)i (aBi’1 ’ bAi’1 )

= (’1)i+1 (aBi ’ bAi ), using the de¬nition of Ai and Bi .

CHAPTER 1. INTEGERS

4

Lemma 1.4.

Ai Bi+1 ’ Ai+1 Bi = (’1)i

Proof. This is done by backsubstitution and using the de¬nition of Ai and Bi .