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
    9
    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
    9,670
    Thanks
    298
    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
    9
    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
    9,670
    Thanks
    298
    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, 10:45 AM
  2. Modular arithmetic problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2010, 12:12 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: October 31st 2009, 01:56 AM
  4. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2009, 12:17 PM
  5. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 03:17 PM

Search Tags


/mathhelpforum @mathhelpforum