Results 1 to 5 of 5

Math Help - Modular arithmetic problem

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    70

    Modular arithmetic problem

    I'm a little out of practice when it comes to modular arithmetic, so this problem is giving me some trouble. I need to show that for every integer n, (n^3) mod 6 = n mod 6.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by spoon737 View Post
    I'm a little out of practice when it comes to modular arithmetic, so this problem is giving me some trouble. I need to show that for every integer n, (n^3) mod 6 = n mod 6.
    It is standard to write,
    n^3\equiv n (\mbox{ mod }6)
    Note, the we can factor 6 as 2 times 3.
    Where 2 and 3 are relatively prime.
    Thus, it is equivalent to saying the system of congruences is satisfied:
    n^3\equiv n(\mbox{ mod } 2) (1)
    n^3\equiv n(\mbox{ mod } 3) (2)
    The first congruence is true because consider cases when n is even or odd. It is true in both of them.
    The second congruence is true by Fermat's little theorem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,243
    Thanks
    430
    Awards
    1
    A question about this:
    n^3 \equiv n \text{ (mod 6)}

    n^3 - n \equiv 0 \text{ (mod 6)}

    n(n^2 - 1) \equiv 0 \text{ (mod 6)}

    n(n + 1)(n - 1) \equiv 0 \text{ (mod 6)}

    So n \equiv -1, 0 , 1 \equiv 0, 1, 5 \text{ (mod 6)}

    Why isn't this producing all the solutions?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by topsquark View Post

    Why isn't this producing all the solutions?
    Because of the property of Zero divisors..

    In general when you have a ring of multiplication mudolu n>1, \mathbb{Z}_n there shall always be zero divisros unless n is prime.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,243
    Thanks
    430
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    Because of the property of Zero divisors..

    In general when you have a ring of multiplication mudolu n>1, \mathbb{Z}_n there shall always be zero divisros unless n is prime.
    Gotcha. The missing solutions are -2, 2, and 3 which are all divisors of 6.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 8th 2011, 11:45 AM
  2. Modular arithmetic problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2010, 01:12 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: October 31st 2009, 02:56 AM
  4. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2009, 01:17 PM
  5. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 04:17 PM

Search Tags


/mathhelpforum @mathhelpforum