TAOCP 1.2.4 Exercise 21
The existence of a factorization into primes follows by induction on $n$, using exercise 1.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 21. [M22] (Fundamental theorem of arithmetic.) Use Law B and exercise 1.2.1–5 to prove that every integer $n>1$ has a unique representation as a product of primes (except for the order of the factors). In other words, show that there is exactly one way to write
$$n=p_1p_2\cdots p_k,$$
where each $p_j$ is prime and $p_1 \le p_2 \le \cdots \le p_k$.
Verified: no
Solve time: 7m21s
Solution
The existence of a factorization into primes follows by induction on $n$, using exercise 1.2.1, 5.
If $n$ is prime, then $n$ itself is a product of primes.
If $n$ is composite, exercise 1.2.1, 5 implies that $n$ has a prime divisor $p$. Hence
$$ n=pm, $$
where $1<m<n$. By the induction hypothesis, $m$ can be written as a product of primes. Therefore $n$ can also be written as a product of primes. Rearranging the factors into nondecreasing order gives a representation
$$ n=p_1p_2\cdots p_k, \qquad p_1\le p_2\le\cdots\le p_k. $$
Thus every integer $n>1$ has at least one such representation.
It remains to prove uniqueness.
Suppose that
$$ n=p_1p_2\cdots p_k =q_1q_2\cdots q_\ell, $$
where
$$ p_1\le p_2\le\cdots\le p_k, \qquad q_1\le q_2\le\cdots\le q_\ell, $$
and all $p_i$ and $q_j$ are prime.
We shall show that
$$ k=\ell \quad\text{and}\quad p_i=q_i \ \ (1\le i\le k). $$
Since
$$ p_1 \mid q_1q_2\cdots q_\ell, $$
Euclid's lemma implies that $p_1$ divides one of the factors $q_j$. Here Euclid's lemma is obtained from Law B: if a prime $p$ divides $ab$ and does not divide $a$, then $\gcd(p,a)=1$, so Law B gives $p\mid b$. Repeating this argument yields the corresponding statement for any finite product.
Therefore $p_1\mid q_j$ for some $j$. Since $q_j$ is prime, its only positive divisors are $1$ and $q_j$. Because $p_1$ is also prime and $p_1\mid q_j$, we must have
$$ p_1=q_j. $$
We now show that in fact $j=1$.
Since the $q$'s are arranged in nondecreasing order,
$$ q_1\le q_j=p_1. $$
Similarly, because
$$ q_1\mid p_1p_2\cdots p_k, $$
the same argument shows that $q_1=p_i$ for some $i$. Since the $p$'s are arranged in nondecreasing order,
$$ p_1\le p_i=q_1. $$
Combining the inequalities gives
$$ p_1\le q_1\le p_1, $$
hence
$$ p_1=q_1. $$
Substituting this into
$$ p_1p_2\cdots p_k=q_1q_2\cdots q_\ell $$
and dividing both sides by the common nonzero factor $p_1=q_1$, we obtain
$$ p_2\cdots p_k=q_2\cdots q_\ell. $$
The same reasoning applied to this new equality yields
$$ p_2=q_2. $$
Dividing again gives
$$ p_3\cdots p_k=q_3\cdots q_\ell. $$
Continuing in this way, we obtain successively
$$ p_r=q_r $$
for every index $r$ for which both sides still contain factors.
Suppose, for example, that $k<\ell$. After cancelling the first $k$ common prime factors, we would obtain
$$ 1=q_{k+1}\cdots q_\ell, $$
which is impossible because each $q_j$ is a prime and therefore greater than $1$. Similarly, $k>\ell$ is impossible. Hence
$$ k=\ell. $$
Since the cancellation process yields $p_r=q_r$ for every $r=1,\dots,k$, we conclude that
$$ p_1=q_1,\quad p_2=q_2,\quad \ldots,\quad p_k=q_k. $$
Therefore the representation
$$ n=p_1p_2\cdots p_k, \qquad p_1\le p_2\le\cdots\le p_k, $$
is unique.
$\square$