[proofplan]
We prove the statement by the [principle of strong induction](/theorems/720) on the natural number $n \ge 2$. The base case is $n = 2$, where the number is already prime. For the induction step, a prime $n$ is already a one-factor product of primes, while a composite $n$ splits as $n = ab$ with $a$ and $b$ strictly between $1$ and $n$; the strong induction hypothesis then gives prime product decompositions for both factors, which concatenate to a prime product decomposition of $n$.
[/proofplan]
[step:Prove the base case $n = 2$]
The natural number $2$ is a [prime number](/pages/prime-number). Therefore $2$ is a product of primes with one factor, namely
\begin{align*}
2 = 2.
\end{align*}
Thus the theorem holds for $n = 2$.
[/step]
[step:Assume prime product decompositions for all smaller natural numbers]
Let $n \in \mathbb{N}$ with $n > 2$. Assume the strong induction hypothesis: for every $k \in \mathbb{N}$ satisfying $2 \le k \le n - 1$, the number $k$ can be written as a product of primes. We prove that $n$ can be written as a product of primes.
[/step]
[step:Handle the case where $n$ is prime]
If $n$ is prime, then $n$ is a product of primes with one factor:
\begin{align*}
n = n.
\end{align*}
Hence the desired conclusion holds in this case.
[/step]
[step:Factor a composite $n$ into smaller factors and apply the induction hypothesis]
Suppose $n$ is composite. By the definition of composite number, there exist natural numbers $a,b \in \mathbb{N}$ such that
\begin{align*}
n = ab,
\qquad
1 < a < n,
\qquad
1 < b < n.
\end{align*}
Since $a,b \in \mathbb{N}$ and both are strictly larger than $1$, we have $2 \le a$ and $2 \le b$. Since both are strictly smaller than $n$, we also have $a \le n - 1$ and $b \le n - 1$. Therefore the strong induction hypothesis applies to both $a$ and $b$.
Thus there exist primes $p_1,\dots,p_r$ and $q_1,\dots,q_s$, for some $r,s \in \mathbb{N}$, such that
\begin{align*}
a = p_1p_2\cdots p_r,
\qquad
b = q_1q_2\cdots q_s.
\end{align*}
Multiplying these two decompositions and using $n = ab$, we obtain
\begin{align*}
n = ab = p_1p_2\cdots p_r q_1q_2\cdots q_s.
\end{align*}
Every factor displayed on the right-hand side is prime, so $n$ is a product of primes.
[guided]
Suppose $n$ is composite. The point of using strong induction is that a composite number breaks into smaller natural numbers, and strong induction lets us use the theorem for every smaller number, not only for $n - 1$.
By the definition of composite number, there exist natural numbers $a,b \in \mathbb{N}$ such that
\begin{align*}
n = ab,
\qquad
1 < a < n,
\qquad
1 < b < n.
\end{align*}
We must check that the induction hypothesis applies to both factors. Since $a,b \in \mathbb{N}$ and $1 < a,b$, the ordering of the natural numbers gives
\begin{align*}
2 \le a,
\qquad
2 \le b.
\end{align*}
Since $a < n$ and $b < n$, and $a,b,n$ are natural numbers, we also have
\begin{align*}
a \le n - 1,
\qquad
b \le n - 1.
\end{align*}
Therefore both $a$ and $b$ lie in the range covered by the strong induction hypothesis:
\begin{align*}
2 \le a \le n - 1,
\qquad
2 \le b \le n - 1.
\end{align*}
Applying the induction hypothesis first to $a$, there exist primes $p_1,\dots,p_r$, for some $r \in \mathbb{N}$, such that
\begin{align*}
a = p_1p_2\cdots p_r.
\end{align*}
Applying the induction hypothesis to $b$, there exist primes $q_1,\dots,q_s$, for some $s \in \mathbb{N}$, such that
\begin{align*}
b = q_1q_2\cdots q_s.
\end{align*}
Now substitute these two prime product decompositions into the factorisation $n = ab$:
\begin{align*}
n = ab = p_1p_2\cdots p_r q_1q_2\cdots q_s.
\end{align*}
The right-hand side is a finite product whose factors are all prime. Hence $n$ is a product of primes.
[/guided]
[/step]
[step:Conclude by strong induction]
The base case $n = 2$ has been proved, and the induction step proves that whenever every natural number $k$ with $2 \le k \le n - 1$ is a product of primes, the natural number $n$ is also a product of primes. By the principle of strong induction, every natural number $n \ge 2$ can be written as a product of primes.
[/step]
