# Math Help - Divisibility

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

$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 $p$ for every natural number $n$ we have: $n^p\equiv{n}(\bmod.p)$ (Fermat's little Theorem)

Let us show it by induction as well.

The assertion is obvious for $n=0$

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

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

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

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

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