Proof by well ordering: Every positive integer greater than one can be factored as a product of primes.

Question

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'?

Answer 1

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.

Answer 2

This proof is appallingly convoluted! Here's a formulation that cleanly distinguishes the conceptually important parts, and is furthermore constructive. Your question is indirectly answered by the key lemma.

Lemma. Given any number $n$, the smallest factor $p$ of $n$ such that $p>1$ is prime.

Proof. Given a number $n$, let $C$ be the set of factors $a$ of $n$ with $a>1$. Since any factor $a$ of $n$ satisfies $1\leq a\leq n$, if $n=1$ then $C$ is empty and the statement is vacuous.

Otherwise, if $1<n$, then $C$ is non-empty since $n$ is a factor of itself; hence by well-ordering $C$ has a least element $p$. Since $1<p$ by definition of $C$, to show that $p$ is prime it suffices to show that the only factor $a$ of $p$ such that $1<a$ is $a=p$. But if $a$ is factor of $p$ with $1<a\leq p$, we also have that $a$ is a factor of $n$ such that $1<a$ (since $a$ is a factor of $p$ which is a factor of $n$). This means $a$ is in $C$, and since $p$ is the least element of $C$ we must have $p\leq a$. But since $a\leq p$ already it follows that $p=a$.

Proposition. Any number $n>1$ has a prime factorization.

Proof. Let $C$ be the set of quotients of $n$ by products of primes, i.e. let $C$ consist of numbers $m$ such that $n=p_1\cdots p_k\cdot m$ for some sequence of (not necessarily distinct) primes $p_1,\dots,p_k$. The set $C$ is not empty when $n>1$ since by the lemma $n$ has a prime factor $p$ (given by the smallest factor $p$ of $n$ such that $p>1$), in which case the quotient $m$ in $n=pm$ is an element of $C$.

It follows by well-ordering that $C$ has a minimal element $m$ so that $n=p_1\cdots p_k\cdot m$ for sequence of (not necessarily distinct) primes $p_1,\dots,p_k$. If $m>1$, then by the lemma $m=pq$ for some prime $p$, hence $n=p_1\cdots p_k\cdot p\cdot q$ implies $q$ is in $C$. But $1\leq q<m$ since $q$ is a quotient of $m$, which contradicts $m$ being minimal in $C$. Therefore, it cannot be the case that $m>1$, so we must have $m=1$. This shows that $n=p_1\cdots p_k$ for some sequence of primes $p_1,\dots,p_k$. Furthermore, the sequence may be constructed by successively taking smallest factors $p$ such that $p>1$.

Answer 3

$n$ is not prime so it factors as $n=ab$ where $1<a;b<n$ and since $n$ was the smallest element of $C$ , $a$ and $ b$ are not in $C$ so they factor as product of primes.