Take the 2-minute tour ×

Every integer greater than $1$ is divisible by a prime.

Prove it by mathematical induction (of weak form).

share|improve this question

closed as off-topic by Andres Caicedo, Amzoti, L.G., Sasha, Branimir Ćaćić Aug 14 '13 at 15:38


  • "This question is not about mathematics, within the scope defined in the help center." – Andres Caicedo, Amzoti, Sasha

for strong induction: It is true for $n=2,$ since $2|2.$ Now suppose it is true for all $n$ from $2$ to $k-1.$ We must show that $k$ is divisible by a prime. If $k$ is prime, then $k$ is divisible by the prime $k,$ and we are done. If $ k $is not prime, it must be composite. Thus $k=ab,$ where $a$ and $b$ are integers less than k and greater than 1. By the inductive hypothesis, $a$ is divisible by $a$ prime $p$, hence $k$ is also divisible by $p$. –  jon Aug 14 '13 at 14:50
now prove it by weak induction ......... –  jon Aug 14 '13 at 14:50
Why do you have to prove it by weak induction? Weak induction is not good for this kind of proof. It is, however, equivalent to strong induction and to the well-order principle: every non-empty set of natural numbers has a smallest element. Both of these give you a better way to prove the assertion. –  walcher Aug 14 '13 at 15:15
I guess, what you are asking is, whether there is some direct proof for the statment "If $k$ is divisible by a prime, then so is $k+1$". There is most likey no such direct proof. In general the prime factorization of $k$ does not give much information about the factorization of $k+1$. –  Tomas Aug 14 '13 at 15:39
I'm not sure, why this question was downvoted and put on hold. It is a perfect legitimate question to ask, whether there is some argument not using the multiplicative but the additive structure of $\mathbb N$. –  Tomas Aug 14 '13 at 15:41

1 Answer 1

up vote 3 down vote accepted

Let $P(n)$ be the assertion that every integer $i$ such that $2\le i\le n$ is divisible by some prime, that is, there is a prime that divides $i$. We prove by weak induction that $P(n)$ holds for every integer $n\ge 2$. That will imply in particular that every integer $n\ge 2$ is divisible by some prime.

The weak induction proof: It is clear that $P(2)$ is true. Now suppose that $P(k)$ is true for some given $k$. We show that $P(k+1)$ is true.

Certainly every $i$ with $2\le i\le k$ is divisible by some prime, by the induction assumption. So we need only prove that $k+1$ is divisible by some prime.

If $k+1$ is prime then we are finished. If not, there exist integers $a$ and $b$, with $2\le a\lt k+1$, and $2\le b\lt k+1$, such that $k+1=ab$. By the induction assumption, since $2\le a\le k$, the number $a$ is divisible by some prime. It follows that $k+1$ is, and we are finished.

Remark: Note that the argument is less natural than the strong induction argument. The "trick" was to change the induction assumption.

share|improve this answer
(+1) for cheating :) –  Tomas Aug 14 '13 at 15:34
It's a ex of good thinking , thanks . –  jon Aug 14 '13 at 17:15
You are welcome. Unfortunate that the question was closed, more answers/viewpoints/tricks are always good. –  André Nicolas Aug 14 '13 at 17:19
Agree...but unfortunately only some people thing so. –  jon Aug 14 '13 at 17:25
