## SubsectionA.3The Proof of the Fundamental Theorem of Arithmetic

Uniqueness. To show uniqueness we will use induction on $n\text{.}$ The theorem is certainly true for $n = 2$ since in this case $n$ is prime. Now assume that the result holds for all integers $m$ such that $1 \leq m \lt n\text{,}$ and

\begin{equation*} n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l, \end{equation*}

where $p_1 \leq p_2 \leq \cdots \leq p_k$ and $q_1 \leq q_2 \leq \cdots \leq q_l\text{.}$ By Lemma 5.3.1, $p_1 \mid q_i$ for some $i = 1, \ldots, l$ and $q_1 \mid p_j$ for some $j = 1, \ldots, k\text{.}$ Since all of the $p_i$'s and $q_i$'s are prime, $p_1 = q_i$ and $q_1 = p_j\text{.}$ Hence, $p_1 = q_1$ since $p_1 \leq p_j = q_1 \leq q_i = p_1\text{.}$ By the induction hypothesis,

\begin{equation*} n' = p_2 \cdots p_k = q_2 \cdots q_l \end{equation*}

has a unique factorization. Hence, $k = l$ and $q_i = p_i$ for $i = 1, \ldots, k\text{.}$

Existence. To show existence, suppose that there is some integer that cannot be written as the product of primes. Let $S$ be the set of all such numbers. By the Principle of Well-Ordering, $S$ has a smallest number, say $a\text{.}$ If the only positive factors of $a$ are $a$ and $1\text{,}$ then $a$ is prime, which is a contradiction. Hence, $a = a_1 a_2$ where $1 \lt a_1 \lt a$ and $1 \lt a_2 \lt a\text{.}$ Neither $a_1\in S$ nor $a_2 \in S\text{,}$ since $a$ is the smallest element in $S\text{.}$ So

\begin{align*} a_1 & = p_1 \cdots p_r\\ a_2 & = q_1 \cdots q_s\text{.} \end{align*}

Therefore,

\begin{equation*} a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s\text{.} \end{equation*}

So $a \notin S\text{,}$ which is a contradiction.