If n is an integer with n>1, then n has a prime factor. How do you do this using strong induction??

Question

If $n$ is an integer with $n>1$, then $n$ has a prime factor. How do you do this using strong induction??

Answer 1

Let $P(n)$ be "n has a prime factor". You need to prove "$P(2)$ is true" (Basis step) and "if $P(2)\land P(3)\cdots \land P(k)$ is true, then $P(k+1)$ is true" (Inductive step).

There are 2 case of $k+1$, prime or not prime. If it's prime then you are done. If it's not prime then exist $a,b$ such that $k+1=ab$. Since $2\le a \le b < k$, by inductive hypothesis $a,b$ both have prime factor. So $k+1=ab$ also have prime factor.