Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers

up vote 4 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|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
add comment

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|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
add comment

Your Answer

 
discard

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.