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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.