22 CHAPTER 1. PRELIMINARIES

1.10 Division

First recall Theorem 1.9.10, the Euclidean algorithm.

Theorem 1.10.1 Suppose 0 < a and let b ≥ 0. Then there exists a unique integer p andunique real number r such that 0 ≤ r < a and b = pa+ r.

The following definition describes what is meant by a prime number and also what ismeant by the word “divides”.

Definition 1.10.2 The number, a divides the number, b if in Theorem 1.9.10, r = 0. Thatis there is zero remainder. The notation for this is a|b, read a divides b and a is called afactor of b. A prime number is one which has the property that the only numbers whichdivide it are itself and 1. The greatest common divisor of two positive integers, m,n is thatnumber, p which has the property that p divides both m and n and also if q divides both mand n, then q divides p. Two integers are relatively prime if their greatest common divisoris 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.10.3 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.9.10,

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. Similarlyp|n.

Now suppose q divides both m and n. Then m = qx and n = qy for integers, x and y.Therefore,

p = mx0 + ny0 = x0qx+ y0qy = q (x0x+ y0y)

showing q|p. Therefore, p = (m,n) . ■There is a relatively simple algorithm for finding (m,n) which will be discussed now.

Suppose 0 < m < n where m,n are integers. Also suppose the greatest common divisor is(m,n) = d. Then by the Euclidean algorithm, there exist integers q, r such that

n = qm+ r, r < m (1.1)