24 CHAPTER 1. PRELIMINARIES

The two new numbers are 3, 1. Then

3 = 3× 1

and so 1 is the greatest common divisor. Of course you could see this right away when thetwo new numbers were 15 and 11. Recall the process delivers numbers which have the samegreatest common divisor.

This amazing theorem will now be used to prove a fundamental property of prime num-bers which leads to the fundamental theorem of arithmetic, the major theorem which saysevery integer can be factored as a product of primes.

Theorem 1.10.7 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 integer z. Therefore,

b = abx+ ybp = pzx+ ybp = p (xz + yb)

and this shows p divides b. ■

Theorem 1.10.8 (Fundamental theorem of arithmetic) Let a ∈ N\ {1}. Then a =∏n

i=1 piwhere pi are all prime numbers. Furthermore, this prime factorization is unique except forthe order of the factors.

Proof: If a equals a prime number, the prime factorization clearly exists. In particularthe prime factorization exists for the prime number 2. Assume this theorem is true for alla ≤ n− 1. If n is a prime, then it has a prime factorization. On the other hand, if n is nota prime, then there exist two integers k and m such that n = km where each of k and mare less than n. Therefore, each of these is no larger than n− 1 and consequently, each hasa prime factorization. Thus so does n. It remains to argue the prime factorization is uniqueexcept for order of the factors.

Supposen∏

i=1

pi =

m∏j=1

qj

where the pi and qj are all prime, there is no way to reorder the qk such that m = n andpi = qi for all i, and n +m is the smallest positive integer such that this happens. Thenby Theorem 1.10.7, p1|qj for some j. Since these are prime numbers this requires p1 = qj .Reordering if necessary it can be assumed that qj = q1. Then dividing both sides by p1 = q1,

n−1∏i=1

pi+1 =

m−1∏j=1

qj+1.

Since n+m was as small as possible for the theorem to fail, it follows that n− 1 = m− 1and the prime numbers, q2, · · · , qm can be reordered in such a way that pk = qk for allk = 2, · · · , n. Hence pi = qi for all i because it was already argued that p1 = q1, and thisresults in a contradiction. ■

There is a similar division result for polynomials. This will be discussed more intensivelylater. For now, here is a definition and the division theorem.