1.12. DIVISION OF NUMBERS 19

b = −(p+1)a+ r and a > r ≥ 0. As to uniqueness, say ri works and r1 > r2. Then youwould have

b = p1a+ r1, b = p2a+ r2

and p2− p1 = r1−r2a ∈ (0,1) which is impossible because p2− p1 is an integer. Hence

r1 = r2 and so also p1 = p2. ■

Corollary 1.12.3 Suppose a,b ̸= 0, then there exists r such that |r| < |a| and for some pan integer,b = ap+ r.

Proof: This is done in the above except for the case where a < 0. So suppose this is thecase. Then b = p(−a)+ r where r is positive and 0≤ r <−a = |a|. Thus b = (−p)a+ rsuch that 0≤ |r|< |a|. ■

This theorem is called the Euclidean algorithm when a and b are integers and this is thecase of most interest here. Note that if a,b are integers, then so is r. Note that

7 = 2×3+1, 7 = 3×3−2, |1|< 3, |−2|< 3

so in this last corollary, the p and r are not unique.The following definition describes what is meant by a prime number and also what is

meant by the word “divides”.

Definition 1.12.4 The number, a divides the number, b if in Theorem 1.12.1, r = 0. That isthere is zero remainder. The notation for this is a|b, read a divides b and a is called a factorof b. A prime number is a number at least 2 which has the property that the only numberswhich divide it are itself and 1. The greatest common divisor of two positive integers, m,nis that number, p which has the property that p divides both m and n and also if q dividesboth m and n, then q divides p. Two integers are relatively prime if their greatest commondivisor is one. The greatest common divisor of m and n is denoted as (m,n) .

There is a phenomenal and amazing theorem which relates the greatest common divisorto the smallest number in a certain set. Suppose m,n are two positive integers. Then if x,yare integers, so is xm+ yn. Consider all integers which are of this form. Some are positivesuch as 1m+ 1n and some are not. The set S in the following theorem consists of exactlythose integers of this form which are positive. Then the greatest common divisor of m andn will be the smallest number in S. This is what the following theorem says.

Theorem 1.12.5 Let m,n be two positive integers and define

S≡ {xm+ yn ∈ N : x,y ∈ Z } .

Then the smallest number in S is the greatest common divisor, denoted by (m,n) .

Proof: First note that both m and n are in S so it is a nonempty set of positive integers.By well ordering, there is a smallest element of S, called p = x0m+y0n. Either p divides mor it does not. If p does not divide m, then by Theorem 1.12.1, m = pq+r where 0 < r < p.Thus m = (x0m+ y0n)q+ r and so, solving for r,

r = m(1− x0)+(−y0q)n ∈ S.

However, this is a contradiction because p was the smallest element of S. Thus p|m. Simi-larly p|n.