Mathematics for Computer Science

(Frankie) #1
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 CC.c1/D

.c1/c
2

:


But then, addingcto both sides we get

1 C 2 C 3 CC.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

Free download pdf