# Proof that $n^3-n$ is a multiple of $3$. [duplicate]

I'm struggling with this problem of proof by induction:

For any natural number $n$, prove that $n^3-n$ is a multiple of $3$.


I assumed that $k^3-k=3r$

I want to show that $(k+1)^3-(K+1)=3r$

The final statement is $K^3 +3K^2+2K$

Am I missing something ?

-

## marked as duplicate by Steven Stadnicki, Najib Idrissi, copper.hat, TZakrevskiy, SeiriosDec 5 '13 at 17:19

Stick with $k$ or $K$, not both for the same variable. Plus, if you assume $k^3-k=3r$, you don't want to show that $(k+1)^3-(k+1) = 3r$ but that $(k+1)^3-(k+1)= 3s$ with $s$ some natural number (a priori not the same as $r$ at all). – Pece Dec 5 '13 at 16:34

If you have $k^3-k$ divisible by 3, then look at $$(k+1)^3-(k+1)=k^3+3k^2+2k =$$ and this is where you need to spot you can use the inductive hypothesis, because you have a $k^3$ there $$=(k^3-k)+3k^2+3k$$ and the term which doesn't have a coefficient $3$ is divisible by $3$ by the hypothesis.

-

$n^3-n = (n+1)n(n-1).$ The right hand side is a product of three consecutive integers... For a proof by induction, note that $(n+1)^3-(n+1) - n^3 + n = 3n^2 + 3 n,$ which is obviously divisible by $3.$ So, if you prove the statement for $n=0,$ you are good to go.

-
It's a good proof by not a proof by induction I think. – user37238 Dec 5 '13 at 16:25
Is it considered a proof by induction? – user113670 Dec 5 '13 at 16:26
@user113670 No, it is not a proof by induction. – Igor Rivin Dec 5 '13 at 16:28
but one is added. – Igor Rivin Dec 5 '13 at 16:30

Use Fermat's little theorem.

Case1: if n is a multiple of 3 then trivially $n^3 -n$ is a multiple of $3$.

Case 2: If $n$ is not a multiple of $3$ you shall get $n^2 \equiv 1 \pmod 3$. Multiply $n$ and get $n^3 -n \equiv 0 \pmod 3$.

-
@Pratyush Thank you for editing, – Dutta Dec 5 '13 at 17:08
Can you go to chat. I made a room for us. – Pratyush Sarkar Dec 5 '13 at 17:30

If you want induction, here you go :

$k^3-k=3m$

$(k+1)^3-(k+1)=k^3+3k^2+3k+1-k-1=(k^3-k)+3(k^2+k)=3m+3n=3(m+n)$

-

If $n=0 \mod 3$ then is nothing to prove. Suppose that $(n,3)=1.$ Now it follows from the Ferma litle theorem. We have that $n^3=n \mod 3$ or, in other words, $n^3-n$ is multiple of 3.

-

using congruence theory we can make easier our steps. Note that if we show $n^3\equiv n [3]$ then we are done. Cause in that case, we shall have $3|n^3-n$ which was asked to prove.

Now any positive integer $n$ gives 0, 1, 2 as remainder when divided by 3. In other words, $n\equiv 0, 1, 2[3]$.

When $n\equiv 0[3]$ then evidently $n^3\equiv 0\equiv n[3]$ so that $n^3\equiv n[3]$ is done.

When $n\equiv 1[3]$ then $n^3\equiv 1[3]$ and hence $n^3-n\equiv 1-1\equiv 0[3]$ so that $n^3\equiv n[3]$ again holds. Finally when $n\equiv 2\equiv -1[3]$ then $n^3\equiv -1[3]$ and then $n^3-n\equiv (-1)-(-1)\equiv 0[3]$ so that $n^3\equiv n[3]$ holds.

Thus we can see that no matter whatever $n\in\mathbb{N}$ we choose we shall always have $n^3\equiv n[3]$ in otherwords $3|n^3-n$.

Done

-