1. ## Divisibility

I need to prove this by induction.

Let n be in Z. prove that 3 divides n^3 - n

This is what I have:

Let n=1, 3 divides 0 so the base case holds

assuming k=n so 3 divides k^3-k

so it is left to show that 3 divides (K+1)^3 -(K+1)

.......

2. Originally Posted by JCIR
I need to prove this by induction.

Let n be in Z. prove that 3 divides n^3 - n

This is what I have:

Let n=1, 3 divides 0 so the base case holds

assuming k=n so 3 divides k^3-k

so it is left to show that 3 divides (K+1)^3 -(K+1)

.......
Expanding the cube we get

$\displaystyle k^3+3k^2+3k+1-k-1=k^3-k+3k^2+3k=(k^3-k)+3(k^2+k)$

3 divides the first term by the induction hypothsis and 3 divides the 2nd term because it is a multiple of 3.

So we are done.

3. Thanks alot I just need that last step.

4. Here's a generalisation

Given a prime $\displaystyle p$ for every natural number $\displaystyle n$ we have: $\displaystyle n^p\equiv{n}(\bmod.p)$ (Fermat's little Theorem)

Let us show it by induction as well.

The assertion is obvious for $\displaystyle n=0$

Now suppose it holds for $\displaystyle n$ (1), we'll show it's also true for $\displaystyle n+1$

By the Binomial Theorem: $\displaystyle (n+1)^p=\sum_{k=0}^{p}\binom{p}{k}\cdot{n^k}$

But now note that: $\displaystyle \binom{p}{k}\equiv{0}(\bmod.p)$ whenever $\displaystyle 1 \leq k\leq{p-1}$ (k natural) indeed $\displaystyle \binom{p}{k}=p\cdot{\frac{(p-1)...(p-k+1)}{k!}}$ is a natural number, but since $\displaystyle 1 \leq k\leq{p-1}$ then $\displaystyle k!$ doesn't divide $\displaystyle p$ so it must be that $\displaystyle \binom{p}{k}\equiv{0}(\bmod.p)$

Thus we have: $\displaystyle (n+1)^p=\sum_{k=0}^{p}\binom{p}{k}\cdot{n^k}\equiv {n^p+1}(\bmod.p)$

And by (1) we have: $\displaystyle n^p\equiv{n}(\bmod.p)$ so that $\displaystyle (n+1)^p\equiv{n+1}(\bmod.p)$