# Use congruences to show that $6$ divides $n^3 – n$ for every integer $n$

Use congruences to show that $6$ divides $n^3 – n$ for every integer $n$.

I did this same problem using induction, and I don't understand how to do it using congruences. Is this using modulo?

-
For instance, if $n \equiv 4 \bmod 6$, then $n^3 \equiv 4^3 \bmod 6$ i.e. $n^3 \equiv 64 \bmod 6$ i.e. $n^3 \equiv 4 \bmod 6$ –  user17762 Oct 31 '11 at 22:04

## 2 Answers

One simple approach is just to try all the residues modulo $6$: $0^3-0=0\equiv 0 \pmod {6},\ldots 5^3-5=120\equiv 0 \pmod {6}$. Alternately, you can factor $n^3-n$ and argue there must be a factor that is divisible by $2$ and one divisible by $3$.

-
Thanks guys. This discrete math...nothing but hard times. –  Chris Oct 31 '11 at 22:24
Short comment: To prove that $n^3-n \equiv 0 \pmod {6}$ you could prove instead that $n^3-n \equiv 0 \pmod {2}$ and $n^3-n \equiv 0 \pmod {3}$, which leads in the general case to sligtly shorter computations.... But also to a trap. –  N. S. Oct 31 '11 at 22:31

well $n^3-n=n(n-1)(n+1)$. Now $n-1,n,n+1$ are three consecutive numbers, so it is sure that one is a multiple of $2$ and one is a multiple of $3$. Hence $6=2\cdot3$ divides their product. If you want to see explicitly the congruence, just write down the observation above using them: for instance $n=0\pmod 2$ and $n+1=0\pmod3$. Since $2,3$ are coprime, then $n(n+1)=0 \pmod 6$.

-
Nice observation, but I think Ross's suggestion is closer to what the OP's source meant by "using congruences". –  Henning Makholm Oct 31 '11 at 22:08