"By considering all possible residue classes modulo 6, or otherwise, prove that n3 - 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 n3 - n is divisible by 6 is the same as:
n3 - n = 6t (for some integer t).
note that if a = b, then a (mod 6) = b (mod 6).
hence (n3 - 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:
n3 = n (mod 6).
note that this is true, even though it is NOT true that n2 = 1 (mod 6) for every n = 0,1,2,3,4,5. for example: 22 = 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.
03 - 0 = 0 = 6*0.
assume true for |n| = k. let |n| = k+1.
case 1: |n| = n
then n3 - n = (k+1)3 - (k+1)= k3 + 3k2 + 3k + 1 - k - 1 = k3 - k + 3k2 + 3k = 6t + 3k(k + 1).
if k = 2m, then 6t + 3(2m)(2m + 1) = 6(m2 + 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 n3 - n = (-|n|)3 - (-|n|) = -|n|3 + |n| = -(|n|3 - |n|), so we can use case 1 (for |n|, since |(|n|)| = |n|).
n3 - n = (n - 1)(n)(n + 1), at least one (possibly two) of these numbers are even, and exactly one is divisible by 3. thus:
n3 - n = 2t = 3u. since 3 is prime, and does not divide 2, but divides 2t = 3u, 3 divides t, so n3 - n = 2t = 2(3v) = 6v.
consider the surjective ring homomorphism h:Z-->Z2 given by: h(1) = 1. this sends n3 - n--> h(n3 - n) = h(n3) - h(n)
= h(n)3 - h(n) = h(n)(h(n)2 - h(n)) = h(n)(h(n) - h(n)) = h(n)(0) = 0.
(since in Z2, a2 = a, for all a),
hence n3 - n is in the ideal generated by 2, which is the kernel of this homomorphism.
similarly, considering the ring homomorphism g:Z-->Z3 given by g(1) = 1, we have: g(n3 - n) = g(n)3 - g(n) = g(n) - g(n) = 0
(since in Z3, a3 = a, for all a. a similar consideration holds for ap in Zp, where p is any prime, this is a variant of "Fermat's Little Theorem").
hence n3 - n is in the ideal (3), so n3-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.