Results 1 to 3 of 3
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By Deveno

Math Help - Another modular arithmetic proof

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    England
    Posts
    8

    Another modular arithmetic proof

    "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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: 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.
    Thanks from dom139
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Another modular arithmetic proof

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

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

    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.

    *********

    4th proof:

    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.
    Last edited by Deveno; December 11th 2012 at 10:17 AM.
    Thanks from dom139
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with a modular arithmetic proof
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: December 11th 2012, 06:38 AM
  2. modular arithmetic
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: March 18th 2010, 08:33 AM
  3. modular arithmetic proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 8th 2010, 05:03 AM
  4. Proof Using Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2009, 11:11 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum