# Proof:Every natural number has a prime factorization

Here is a simplified version of the proof that every natural number has a prime factorization.

We use strong induction to avoid the notational overhead of strengthening the inductive hypothesis. This proof has the simplicity of the incorrect weak induction proof, but it actually works. You should compare the three versions of the proofs to understand the differences.

For all , if then there exists prime numbers with .
Proof: using strong induction
We will prove the claim using strong induction. Let be the statement that "there exists prime numbers with . We will prove and assuming .

In the base case, when we see that 2 is prime. Therefore, we can choose ; clearly .

For the inductive step, we assume (or in other words, we strong induction for all ; our goal is to show , in other words that has a prime factorization.

There are two cases: could be prime or composite. If is prime, we can proceed as in the base case: simply choose .

If, on the other hand, is composite, then we know that for some natural numbers and .

Since and must be less than , we can apply and to conclude that both and have prime factorizations.

Let be the prime factorization of , and let be the prime factorization of . If we let be the sequence starting with the and ending with the s (in other words, ). Then clearly .