22 CHAPTER 2. THE REAL AND COMPLEX NUMBERS

2.8 Arithmetic of IntegersHere we consider some very important algebraic notions including the Euclidean algorithmjust mentioned and issues related to whether two numbers are relatively prime, prime num-bers and so forth. The following definition describes what is meant by a prime number andalso what is meant by the word “divides”.

Definition 2.8.1 The number a divides the number b if, in Theorem 2.7.11, r = 0.That is, there is zero remainder. The notation for this is a|b, read a divides b and a is calleda factor of b. A prime number is one which has the property that the only numbers whichdivide it are itself and 1 and it is at least 2. The greatest common divisor of two positiveintegers m,n is that number p which has the property that p divides both m and n and alsoif q divides both m and n, then q divides p. Two integers are relatively prime if their greatestcommon divisor 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 2.8.2 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 2.7.11, 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.

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).This amazing theorem will now be used to prove a fundamental property of prime

numbers which leads to the fundamental theorem of arithmetic, the major theorem whichsays every integer can be factored as a product of primes.

Theorem 2.8.3 If p is a prime and p|ab then either p|a or p|b.

Proof: Suppose p does not divide a. Then since p is prime, the only factors of p are 1and p so follows (p,a)= 1 and therefore, there exists integers, x and y such that 1= ax+yp.Multiplying this equation by b yields b = abx+ ybp. Since p|ab, ab = pz for some integerz. Therefore, b = abx+ ybp = pzx+ ybp = p(xz+ yb) and this shows p divides b.