# Proof:Every natural number has a prime factorization (strengthened induction hypothesis)

Here is a corrected version of the proof that Every natural number has a prime factorization wherein we strengthen the inductive hypothesis. You may find it useful to read them side by side to understand the differences.

There is a lot of technicality involved in this proof that doesn't really help explain what's going on; it is much clearer to write essentially the same proof using strong induction. This is an example to demonstrate that you can always rewrite a strong induction proof using weak induction.

The key idea is that, instead of proving that every number has a prime factorization, we prove that, for any given , every number has a prime factorization. Of course, this means that itself has a prime factorization, but by proving even more, we allow our inductive step to go through.

For all , if then there exists prime numbers with .
We will prove the claim using weak induction, but with a strengthened induction hypothesis. Let be the statement "for all with , there exists prime numbers with . We will prove and assuming .

In the base case, when , we will choose an arbitrary between and ; we see that must be 2. 2 is prime. Therefore, we can choose ; clearly .

For the inductive step, we assume ; our goal is to show , in other words that every has a prime factorization.

Choose an arbitrary . Since and are natural numbers, we see that either or . If , then we can apply to find a prime factorization for . Thus, the only remaining case is when .

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 .

If we knew that and had prime factorizations, then we could combine them to form a prime factorization of . But now we do know that! Since and , we see that ; similarly . Therefore we can apply to conclude that and have prime factorizations.

We can therefore finish the proof: 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 .