[proofplan] Existence of a prime factorisation is supplied by the already established theorem that every natural number greater than $1$ is a product of primes, with $1$ represented by the empty product. It remains to prove uniqueness, and we do this by strong induction on $n$. Given two prime factorisations of $n$, [Euclid's Lemma](/theorems/729) forces the first prime in one factorisation to equal some prime in the other; after reordering and cancelling this common prime, the induction hypothesis applies to the smaller quotient. [/proofplan] [step:Reduce the theorem to uniqueness of prime factorisations] By the [Natural Numbers as Products of Primes](/theorems/723), every natural number $n \geq 1$ has at least one prime factorisation, with $n = 1$ represented by the empty product. Therefore it remains to prove uniqueness up to reordering. We prove the following assertion by strong induction on $n$: if \begin{align*} n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s \end{align*} are two prime factorisations of $n$, where $r,s \in \mathbb{N} \cup \{0\}$ and every listed $p_i$ and $q_j$ is prime, then $r = s$ and, after reordering the second list, $p_i = q_i$ for every $i = 1,\ldots,r$. [/step] [step:Settle the empty product case] For $n = 1$, a product of one or more primes is at least $2$, because every prime is at least $2$. Hence no non-empty product of primes equals $1$. Therefore the only prime factorisation of $1$ is the empty product, so uniqueness holds for $n = 1$. [/step] [step:Assume uniqueness below $n$ and compare two factorisations of $n$] Let $n \in \mathbb{N}$ with $n > 1$. Assume as the strong induction hypothesis that uniqueness of prime factorisation holds for every natural number $k$ satisfying $1 \leq k < n$. Suppose \begin{align*} n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s \end{align*} are two prime factorisations of $n$, where $p_1,\ldots,p_r$ and $q_1,\ldots,q_s$ are primes listed with multiplicity. Since $n > 1$, neither factorisation is empty, so $r \geq 1$ and $s \geq 1$. [/step] [step:Use Euclid's Lemma to match $p_1$ with one of the $q_j$] Since \begin{align*} p_1 \mid n \end{align*} and \begin{align*} n = q_1 q_2 \cdots q_s, \end{align*} we have \begin{align*} p_1 \mid q_1 q_2 \cdots q_s. \end{align*} We justify the repeated use of Euclid's Lemma by induction on the number of factors in the product $q_1 q_2 \cdots q_s$. For $s = 1$ the conclusion is immediate. For $s > 1$, Euclid's Lemma applied to \begin{align*} p_1 \mid q_1(q_2 \cdots q_s) \end{align*} gives either $p_1 \mid q_1$ or $p_1 \mid q_2 \cdots q_s$; in the second case the induction hypothesis applied to the product of $s-1$ factors gives an index $j \in \{2,\ldots,s\}$. Hence there exists an index $j \in \{1,\ldots,s\}$ such that \begin{align*} p_1 \mid q_j. \end{align*} Because $q_j$ is prime, its only positive divisors are $1$ and $q_j$. Since $p_1$ is prime, $p_1 > 1$, so $p_1 = q_j$. Reorder the $q$-factors by moving $q_j$ to the first position. After this reordering, we have \begin{align*} p_1 = q_1. \end{align*} [guided] We need to show that the first prime $p_1$ appearing in the first factorisation also appears somewhere in the second factorisation. Since $p_1$ is one of the factors in \begin{align*} n = p_1 p_2 \cdots p_r, \end{align*} we have $p_1 \mid n$. Using the second factorisation of the same number, \begin{align*} n = q_1 q_2 \cdots q_s, \end{align*} this gives \begin{align*} p_1 \mid q_1 q_2 \cdots q_s. \end{align*} We now apply Euclid's Lemma. Its hypothesis is that a prime divides a product of two natural numbers, so to use it on a product with $s$ factors we argue by induction on $s$. If $s=1$, then $p_1 \mid q_1$ and we are done. If $s>1$, write the product as \begin{align*} q_1(q_2 \cdots q_s). \end{align*} Euclid's Lemma applied to \begin{align*} p_1 \mid q_1(q_2 \cdots q_s) \end{align*} gives either $p_1 \mid q_1$ or $p_1 \mid q_2 \cdots q_s$. In the second case, the induction hypothesis for the product of $s-1$ factors gives an index $j \in \{2,\ldots,s\}$ such that $p_1 \mid q_j$. Therefore in all cases there exists an index $j \in \{1,\ldots,s\}$ such that \begin{align*} p_1 \mid q_j. \end{align*} Since $q_j$ is prime, its positive divisors are exactly $1$ and $q_j$. Since $p_1$ is also prime, $p_1 > 1$, so the divisibility relation $p_1 \mid q_j$ cannot mean $p_1 = 1$. Therefore \begin{align*} p_1 = q_j. \end{align*} The theorem only claims uniqueness up to order, so we may reorder the second list of prime factors without changing the factorisation. Move this matched factor $q_j$ to the first position. After this reordering, \begin{align*} p_1 = q_1. \end{align*} [/guided] [/step] [step:Cancel the matched prime and apply the induction hypothesis] Define the natural number \begin{align*} m := \frac{n}{p_1}. \end{align*} Since $p_1 \geq 2$ and $n > 1$, we have \begin{align*} 1 \leq m < n. \end{align*} Using $p_1 = q_1$ and cancellation in $\mathbb{N}$, the two factorisations of $n$ give \begin{align*} m = p_2 \cdots p_r = q_2 \cdots q_s. \end{align*} By the strong induction hypothesis applied to $m$, the two remaining prime factorisations have the same length and the same factors up to reordering. Hence \begin{align*} r - 1 = s - 1, \end{align*} so $r = s$, and after reordering the remaining factors, \begin{align*} p_i = q_i \end{align*} for every $i = 2,\ldots,r$. Together with $p_1 = q_1$, this proves uniqueness for $n$. [guided] Once we have matched one prime factor, the goal is to reduce the problem from $n$ to a smaller natural number. Define \begin{align*} m := \frac{n}{p_1}. \end{align*} This is a natural number because $p_1$ divides $n$. Also $p_1 \geq 2$, since $p_1$ is prime, so \begin{align*} 1 \leq m = \frac{n}{p_1} \leq \frac{n}{2} < n. \end{align*} Thus $m$ lies in the range where the strong induction hypothesis applies. From the two factorisations of $n$ and the equality $p_1 = q_1$, we have \begin{align*} p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s = p_1 q_2 \cdots q_s. \end{align*} Cancelling the common positive factor $p_1$ in $\mathbb{N}$ gives \begin{align*} m = p_2 \cdots p_r = q_2 \cdots q_s. \end{align*} These are two prime factorisations of the smaller natural number $m$. The induction hypothesis says that any two prime factorisations of $m$ have the same number of factors and agree after reordering. Therefore \begin{align*} r - 1 = s - 1, \end{align*} and hence $r = s$. After reordering the remaining factors, we also have \begin{align*} p_i = q_i \end{align*} for every $i = 2,\ldots,r$. Since the first factors were already matched by $p_1 = q_1$, the whole factorisation of $n$ is unique up to reordering. [/guided] [/step] [step:Conclude uniqueness for every natural number] The base case $n = 1$ holds, and the induction step proves uniqueness for each $n > 1$ assuming uniqueness for all smaller natural numbers. By strong induction, every natural number $n \geq 1$ has a unique prime factorisation up to the order of the factors. Combined with existence from the Natural Numbers as Products of Primes, this proves the Fundamental Theorem of Arithmetic. [/step]