Results 1 to 3 of 3

Math Help - Modular Arithmetic

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    1

    Angry Modular Arithmetic

    Hi,
    I'm not too confident about some mod simplification.
    I am wondering if anyone can help me simplify this:
    2^(28) (mod 37)
    Basically, I don't know how to get it to become a 2^x = 1 or -1 (mod 37)
    Here's my attempt
    1) (2^2) (3^2) = -1 (mod 37)
    Therefore...
    Well, let's face it, I have no idea where to go from there.

    Thanks for any help
    P.S.: Please forgive me, I'm having some trouble with LaTex right now
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by pawnag3 View Post
    Hi,
    I'm not too confident about some mod simplification.
    I am wondering if anyone can help me simplify this:
    2^(28) (mod 37)
    Basically, I don't know how to get it to become a 2^x = 1 or -1 (mod 37)
    Here's my attempt
    1) (2^2) (3^2) = -1 (mod 37)
    Therefore...
    Well, let's face it, I have no idea where to go from there.

    Thanks for any help
    P.S.: Please forgive me, I'm having some trouble with LaTex right now

    2^{28}=(2^7)^4=17^4=12\!\!\pmod {37}

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    There's another way to do it, using intuitive ideas and only 6 operations. Start with 2; you know of course that 2 = 2 (mod 37). Successively square this until you have 2^16:

    2^1\equiv 2 \text{ (mod 37)}, \qquad 2^2\equiv 4 \text{ (mod 37)}, \qquad 2^4\equiv 16 \text{ (mod 37)},
    2^8\equiv 256 \equiv -3 \text{ (mod 37)},\qquad 2^{16}\equiv 9 \text{ (mod 37)}.

    Now you notice that 28 = 16 + 8 + 4. So you calculate the product:

    2^{28} \equiv 2^{16+8+4} \equiv 9 \times -3\times 16 \equiv 12\text{ (mod 37)}.

    Tonio's method is essentially the same but uses 9 operations.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 4th 2011, 12:07 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 02:37 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 06:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 04:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 09:39 PM

Search Tags


/mathhelpforum @mathhelpforum