Mathematics for Computer Science

Chapter 2 The Well Ordering Principle28

meansc 1 is a nonnegative integer, and since it is less thanc, equation (2.1) is

true forc 1. That is,

1 C 2 C 3 C


C.c1/D

.c1/c

2

:

But then, addingcto both sides we get

1 C 2 C 3 C


C.c1/CcD

.c1/c

2

CcD

c^2 cC2c

2

D

c.cC1/

2

;

which means that (2.1) does hold forc, after all! This is a contradiction, and we

are done. 

2.4 Factoring into Primes

We’ve previously taken for granted thePrime Factorization Theoremthat every

integer greater than one has a unique^2 expression as a product of prime numbers.

This is another of those familiar mathematical facts which are not really obvious.

We’ll prove the uniqueness of prime factorization in a later chapter, but well order-

ing gives an easy proof that every integer greater than one can be expressed assome

product of primes.

Theorem 2.4.1.Every natural number can be factored as a product of primes.

Proof. The proof is by Well Ordering.

LetC be the set of all integers greater than one that cannot be factored as a

product of primes. We assumeCis not empty and derive a contradiction.

IfCis not empty, there is a least element,n 2 C, by Well Ordering. Thencan’t

be prime, because a prime by itself is considered a (length one) product of primes

and no such products are inC.

Sonmust be a product of two integersaandbwhere1 < a;b < n. Sincea

andbare smaller than the smallest element inC, we know thata;b...C. In other

words,acan be written as a product of primesp 1 p 2 


pkandbas a product of

primesq 1 


ql. Therefore,nDp 1 


pkq 1 


qlcan be written as a product of

primes, contradicting the claim thatn 2 C. Our assumption thatC is not empty

must therefore be false. 

(^2)... unique up to the order in which the prime factors appear