Another modular arithmetic proof

"By considering all possible residue classes modulo 6, or otherwise, prove that n³ - n is a multiple of 6 for all integers n."
I've been staring at this one for a while now and i've got tunnel vision.
Thanks in advance.

The idea is the same as in the previous problem. When you are performing the four basic arithmetic operations and take the remainder modulo some q, you can take the remainder at any time; the result will be the same. Let us denote by (x mod q) the remainder of x when divided by q. Then

(x * y) mod q =
((x mod q) * (y mod q)) mod q =
((x mod q) * y) mod q =
(x * (y mod q)) mod q

That is, you can take the remainder either before or after the operation.

Therefore, to find (n^3 - n) mod 6, it is sufficient to find ((n mod 6)^3 - (n mod 6)) mod 6, and there are only 6 possible values for n mod 6.

Edit: Questions about modular arithmetic should go to the Number Theory forum.

the statement n³ - n is divisible by 6 is the same as:

n³ - n = 6t (for some integer t).

note that if a = b, then a (mod 6) = b (mod 6).

hence (n³ - n) (mod 6) = 6t (mod 6) = 0 (mod 6).

since [a (mod 6)] + [b ( mod 6)] = (a+b) (mod 6), which can be seen like so:

if a = a' (mod 6) (that is (a (mod 6)) = a'), then a = a' + 6k.

if b = b' (mod 6), then b = b'+ 6m.

hence a + b = a' + 6k + b' + 6m = (a'+b') + 6(k+m), so a+b = a'+b' (mod 6).

continuing, this means:

n³ = n (mod 6).

note that this is true, even though it is NOT true that n² = 1 (mod 6) for every n = 0,1,2,3,4,5. for example: 2² = 4 ≠ 1 (mod 6). we can't "cancel the n's" (1/n does not always exist, mod 6).

********

of course this can also be proved in other ways:

by induction on |n|:

base case: n = 0.

0³ - 0 = 0 = 6*0.

assume true for |n| = k. let |n| = k+1.

case 1: |n| = n

then n³ - n = (k+1)³ - (k+1)= k³ + 3k² + 3k + 1 - k - 1 = k³ - k + 3k² + 3k = 6t + 3k(k + 1).

if k = 2m, then 6t + 3(2m)(2m + 1) = 6(m² + m), a multiple of 6.

if k = 2m+1, then 6t + 3(2m+1)((2m+1)+1) = 3(2m+1)(2m+2) = 6(2m+1)(m+1), also a multiple of 6.

case 2: |n| = -n

then n³ - n = (-|n|)³ - (-|n|) = -|n|³ + |n| = -(|n|³ - |n|), so we can use case 1 (for |n|, since |(|n|)| = |n|).

*********
3rd proof:

n³ - n = (n - 1)(n)(n + 1), at least one (possibly two) of these numbers are even, and exactly one is divisible by 3. thus:

n³ - n = 2t = 3u. since 3 is prime, and does not divide 2, but divides 2t = 3u, 3 divides t, so n³ - n = 2t = 2(3v) = 6v.

*********

4th proof:

consider the surjective ring homomorphism h:Z-->Z₂ given by: h(1) = 1. this sends n³ - n--> h(n³ - n) = h(n³) - h(n)

= h(n)³ - h(n) = h(n)(h(n)² - h(n)) = h(n)(h(n) - h(n)) = h(n)(0) = 0.

(since in Z₂, a² = a, for all a),

hence n³ - n is in the ideal generated by 2, which is the kernel of this homomorphism.

similarly, considering the ring homomorphism g:Z-->Z₃ given by g(1) = 1, we have: g(n³ - n) = g(n)³ - g(n) = g(n) - g(n) = 0

(since in Z₃, a³ = a, for all a. a similar consideration holds for a^p in Z_p, where p is any prime, this is a variant of "Fermat's Little Theorem").

hence n³ - n is in the ideal (3), so n³-n is in (2)∩(3) = (lcm(2,3)) = ((2*3)/gcd(2,3)) = (6).

*********
while proof #4 may seem "abstract" it's actually the underlying reason why the original proof (using (mod 6)) works.