Existence of prime factorization

Statement

Each positive integer $n$ has a prime factorization. That is, there are prime numbers $p_1, \dots, p_k$, with $k \ge 0$, such that $n = p_1 p_2 \cdots p_k$.

Remarks

The proof uses strong induction on $n$. If $n = 1$, take $k = 0$. If $n$ is prime, take $k = 1$. Otherwise $n = a b$ with $1 < a, b < n$, and we join the factorizations of $a$ and $b$. The fundamental theorem of arithmetic adds that the factorization is unique, up to the order of the factors.

Explanations

L1 human

Split each number that is not prime into two smaller factors. Continue until all the pieces are prime. The pieces always get smaller, so the splitting stops. For example, $84 = 2 \cdot 42 = 2 \cdot 2 \cdot 21 = 2 \cdot 2 \cdot 3 \cdot 7$.