1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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$ $\endgroup$
    – user17762
    Oct 31 '11 at 22:04
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks guys. This discrete math...nothing but hard times. $\endgroup$
    – Chris
    Oct 31 '11 at 22:24
  • $\begingroup$ 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. $\endgroup$
    – N. S.
    Oct 31 '11 at 22:31
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nice observation, but I think Ross's suggestion is closer to what the OP's source meant by "using congruences". $\endgroup$ Oct 31 '11 at 22:08

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