Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 5 down vote accepted

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$.

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.