# Use mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes.

I know the steps of weak mathematical induction...
Basis step: $p(n)$ for $n=1$ or any arbitrary $n_0$ ... show that it is true
Inductive hypothesis: $p(n)$ for $n=k$ ... Assume that it is true for $n=k$
Inductive step: $P(n)$ for $n=k+1$ ... Show that this is true for $n=k+1$

Strong induction means following: suppose $P(0)$ and that $P(k),k<n$ implies $P(n)$. Then $P(n)$ for all $n\in\mathbb{N}$.
For this question, our base is $n=2$, which is prime, so the statement holds. Now assume $n>2$ and that every $k<n$ is either prime or a product of primes. If $n$ is prime then there's nothing to prove, so assume $n$ is not prime. Then there exists $a,b\in\mathbb{N}$ with $1<a,b<n$ such that $n=ab$. By induction hypothesis, $a=p_1\cdot\ldots\cdot p_r$ and $b=q_1\cdot\ldots\cdot q_s$ for primes $p_1,\ldots,p_r,q_1,\ldots,q_s$. Then $n=p_1\cdot\ldots\cdot p_rq_1\cdot\ldots\cdot q_s$ is the product of primes, completing the proof.