Proving every positive natural has a factorization in prime numbers with strong induction

Question

The question is in the title.

I think my base case should start at 1, which would be valid because the product of the empty set of primes would be 1.

In my textbook it says that to conclude $\forall n:P(n)$ I need to prove $Q(n)\rightarrow P(n+1)$, where $Q(n)$ is $\forall i:(i\leq n)\rightarrow P(i)$.

How do I go about doing this last part?

Answer 1

Hint:

Make the strong induction hypothesis, and consider the number $n+1$. Then

• either it's prime, and you're done;
• or it isn't prime, which means you can factor it as $n+1=rs$, $\; 1<r,s<n+1$, i.e. $\; 2\le r,s\le n$. To each of $r,s $ you can apply the strong induction hypothesis.

Answer 2

The theorem really only holds for numbers $n \ge 2$, so there are two things you can do:

• You can consider all natural numbers, and for $P(n)$ take "if $n \ge 2$ then $n$ has a prime factorisation."

To prove this, take an arbitrary number, and show that if for all $m<n$: if $m \ge 2$ then $m$ has a prime factorization, then if $n \ge 2$ then $n$ has a prim factorisation

• restrict yourself to just the numbers greater or equal to 2. Now you can let $P(n)$ simply be that $n$ has a prime factorization, and it is understood that when you consider any number, it is a number greater or equal to 2

To prove this, take an arbitrary number, and show that if for all numbers $m<n$, $m$ has a prime facorization, then $n$ has a prime factorization (but again, the $n$ and all $m$'s are considered greater or equal to 2)

The second way is probably a little easier, though do keep in mind the special (base) case where $n=2$, because then there are no $m<n$ with $m$ greater or equal 2. So, you need to show that 2 has a prime factorization.