"By considering all possible residue classes modulo 6, or otherwise, prove that n^{3}- 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.

Printable View

- December 11th 2012, 09:00 AMdom139Another modular arithmetic proof
"By considering all possible residue classes modulo 6, or otherwise, prove that n

^{3}- 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. - December 11th 2012, 09:22 AMemakarovRe: Another modular arithmetic proof
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. - December 11th 2012, 11:11 AMDevenoRe: Another modular arithmetic proof
the statement n

^{3}- n is divisible by 6 is the same as:

n^{3}- n = 6t (for some integer t).

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

hence (n^{3}- 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^{3}= n (mod 6).

note that this is true, even though it is NOT true that n^{2}= 1 (mod 6) for every n = 0,1,2,3,4,5. for example: 2^{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^{3}- 0 = 0 = 6*0.

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

case 1: |n| = n

then n^{3}- n = (k+1)^{3}- (k+1)= k^{3}+ 3k^{2}+ 3k + 1 - k - 1 = k^{3}- k + 3k^{2}+ 3k = 6t + 3k(k + 1).

if k = 2m, then 6t + 3(2m)(2m + 1) = 6(m^{2}+ 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^{3}- n = (-|n|)^{3}- (-|n|) = -|n|^{3}+ |n| = -(|n|^{3}- |n|), so we can use case 1 (for |n|, since |(|n|)| = |n|).

*********

3rd proof:

n^{3}- 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^{3}- n = 2t = 3u. since 3 is prime, and does not divide 2, but divides 2t = 3u, 3 divides t, so n^{3}- n = 2t = 2(3v) = 6v.

*********

4th proof:

consider the surjective ring homomorphism h:Z-->Z_{2}given by: h(1) = 1. this sends n^{3}- n--> h(n^{3}- n) = h(n^{3}) - 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 Z_{2}, a^{2}= a, for all a),

hence n^{3}- n is in the ideal generated by 2, which is the kernel of this homomorphism.

similarly, considering the ring homomorphism g:Z-->Z_{3}given by g(1) = 1, we have: g(n^{3}- n) = g(n)^{3}- g(n) = g(n) - g(n) = 0

(since in Z_{3}, a^{3}= 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^{3}- n is in the ideal (3), so n^{3}-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.