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.