Question

Let n be a natural number. Show that 3 | n3 −n

Answer 1

Let $n=1$. Then $n^3-n=1^3-1=0$. By convention, every non-zero integer $n$ divides 0, so $3\vert n^3-n$.

Suppose this relation holds for $n=k$, i.e. $3\vert k^3-k$. We then hope to show it must also hold for $n=k+1$.

You have

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

We assumed that $3\vert k^3-k$, and it's clear that $3\vert 3(k^2+k)$ because $3(k^2+k)$ is a multiple of 3. This means the remainder upon divides $(k+1)^3-(k+1)$ must be 0, and therefore the relation holds for $n=k+1$. This proves the statement.