I am reading the book Mathematics for Computer Science and have reached the chapter 2.3 Factoring into Primes where there is an explanation how Well Ordering can be used to prove the following:
Theorem 2.3.1. Every positive integer greater than one can be factored as a product of primes.
Here is the excerpt of the proof:
Let C be the set of all integers greater than one that cannot be
factored as a product of primes. We assume C is not empty and derive a
contradiction.
If C is not empty, there is a least element n ∈ C by
well ordering. The n can’t be prime, because a prime by itself is
considered a (length one) product of primes and no such products are
in C.
So n must be a product of two integers a and b where 1 < a; b <
n. Since a and b are smaller than the smallest element in C, we know
that a; b ∉ C. In other words, a can be written as a product of primes
p1p2…pk and b as a product of primes q1…ql.
Therefore, n =
p1….pkq1….ql can be written as a product of primes, contradicting
the claim that n ∈ C. Our assumption that C is not empty must
therefore be false.
I've managed to understand the proof, but I'm stuck on the following statement:
So n must be a product of two integers
Why is this a 'must'?
Best Answer
Since $n$ is in $C$, it cannot be factored into a product of primes. $n$ cannot itself be prime, otherwise it would have the trivial factorization. Since $n$ is not prime, it has proper integer divisors.