Suppose every positive integer less than n is divisible by 2 or 3. If n is even, then n is divisible by 2. If n is odd, then n-6 is odd and must be divisible by three, i.e., for some x
n - 6 = 3x
So we can write
n = n - 6 + 6 = 3x + 6 = 3(x + 2)
Therefore n is divisible by 3.
That proves the induction step; now we need to show that the hypothesis is true for a particular n. Consider n = 1. There are no positive integers less than 1, so the hypothesis holds trivially.
Therefore, we conclude by induction that every positive integer is divisible by 2 or 3.
|
