Prime factorization/Existence/Fact/Proof2

Proof

We prove the existence by induction over ${}n$, and we consider the statement ${}A(n)$ saying that every natural number ${}m$ with ${}2\leq m\leq n$ has a prime factorization. For ${}n=2$ we have a prime number. So suppose that ${}n\geq 2$ and assume that, by the induction hypothesis, every number ${}m\leq n$ has a prime factorization. We have to show that every number ${}m\leq n+1$ has a prime factorization. The only new number to consider is ${}n+1$. In the proof of this induction step, another important proof scheme occurs, the proof by cases. Here one argues depending on whether an additional property holds or not, and in both cases one has to prove the result.

Here we consider the cases whether ${}n+1$ is a prime number or not. If ${}n+1$ is a prime number, then we have immediately the prime factorization, just take the number itself. In this case we do not even use the induction hypothesis.

So now we consider the case where ${}n+1$ is not prime. This means that there exists a non-trivial decomposition ${}n+1=ab$ with smaller numbers ${}a,b<n+1$. For these numbers ${}a$ and ${}b$, there exist, due to the induction hypothesis, factorizations into prime numbers, and we can put these together to gain a prime factorization of ${}n+1$. 

To fact