Skip to main content

Subsection A.3 The 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.

login