Results 1 to 7 of 7

Math Help - A question on modular arithmetic

  1. #1
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    A question on modular arithmetic

    I'm preparing for a contest, and for some of the practice questions, I've managed to simplify things greatly, but I can't figure out how to simplify what I have further.

    For example:
    17^17 mod 25
    18^16 mod 25
    19^19 mod 25

    How do I simplify these expressions any further...
    I don't think CRT and Euler's formula can help me any further.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68
    I got 18^16 mod 25.
    Since 18^4 = 1 mod 25, we have
    18^16 = 1 mod 25.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2
    For instance,

    All mod 25

    17^17
    = (-8)^17
    = -8 * (-8)^16
    = -8 * 64^8
    = -8 * 14^8
    = -8 * 196 ^ 4
    = -8 * (-4)^4
    = -8 * 256
    = -8 * 6
    = -48
    = 2
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,686
    Thanks
    617
    Hello, elemental!

    18^{16}\text{ mod 25}


    \text{Since }18^4 \equiv 1\text{ (mod 25)}

    . . \text{we have: }\:(18^4)^4 \,\equiv\,1^4\text{ (mod 25)}

    \text{Therefore: }\:18^{16} \:\equiv\:1\text{ (mod 25)} . Good!

    17^{17}\text{ (mod 25)}

    We have: . 17\:\equiv\:\text{-}8\text{ (mod 25)}

    (\text{-}8)^4 \:=\:4096 \:\equiv\:\text{-}4\text{ (mod 25)}

    [(\text{-}8)^4]^4 \:\equiv\:(\text{-}4)^4 \:\equiv\:256\text{ (mod 25)}

    (\text{-}8)^{16} \:\equiv\:6\text{ (mod 25)}

    (\text{-}8)^{16}\cdot(\text{-}8) \:\equiv\:6\cdot(\text{-}8) \text{ (mod 25)}

    (\text{-}8)^{17} \:\equiv\:-48\text{ (mod 25)}

    \text{Therefore: }\:17^{17} \:\equiv\:2\text{ (mod 25)}




    19^{19}\text{ (mod 25)}

    \text{We have: }\:19 \:\equiv\:\text{-}6\text{ (mod 25)}

    (\text{-}6)^4 \;=\;1296 \:\equiv\:\text{-}4\text{ (mod 25)}

    [(\text{-}6)^4]^4 \:\equiv\:(\text{-}4)^4 \:\equiv\:256\text{ (mod 25)}

    (\text{-}6)^{16} \:\equiv\:6\text{ (mod 25)}

    (\text{-}6)^{16}\!\cdot\!(\text{-}6)^3 \:\equiv\:6\!\cdot\!(\text{-}6)^3 \text{ (mod 25)}

    (\text{-}6)^{19} \:\equiv\:\text{-}1296\text{ (mod 25)}

    \text{Therefore: }\:19^{19} \:\equiv\:4\text{ (mod 25)}

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68
    Thanks... I got it differently, though.

    I just used Euler's formula again.
    Since phi(25) = 20, we know
    17^20 = 1 mod 25.

    We know 3 = 17^-1 mod 25.

    So 17^17 = 3^3 = 2 mod 25.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    A different approach is by the Binomial Theorem.

    We have 17\equiv2\pmod5, namely 17=2+5k, where k is some integer. Then (2+5k)^5=2^5+\binom{5}{1}\cdot2^4(5k)^1+\binom{5}{  2}\cdot2^3(5k)^2+\binom{5}{3}\cdot2^2(5k)^3+\binom  {5}{4}\cdot2^1(5k)^5+(5k)^5 by the Binomial Theorem.
    Note that all the terms except for the first one are divisible by 25. Therefore, 17^5\equiv2^5\equiv7\pmod{25}. Hence, 17^{17}=(17^5)^3\cdot17^2\equiv7^3\cdot17^2\equiv(-7)\cdot14\equiv2\pmod {25}.

    Similarly, from the congruence 18\equiv3\pmod5 it follows that 18^5\equiv3^5\equiv(-7)\pmod{25}, so 18^{16}=18^5\cdot18\equiv(-7)\cdot(-7)\equiv1\pmod{25}.

    Again 19\equiv4\pmod5 and then 19^5\equiv4^5\equiv(-1)\pmod{25}. Therefore 19^{19}=(19^5)^3\cdot19^4\equiv(-1)^3\cdot19^4; so 19^4=19^2\cdot19^2\equiv11\cdot11\equiv(-4)\pmod {25} gives 19^{19}\equiv4\pmod{25}.
    Last edited by melese; November 19th 2010 at 04:43 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by qmech View Post
    For instance,

    All mod 25

    17^17
    = (-8)^17
    = -8 * (-8)^16
    = -8 * 64^8
    = -8 * 14^8


    *** 64=13\!\!\pmod {17} ***


    = -8 * 196 ^ 4
    = -8 * (-4)^4
    = -8 * 256
    = -8 * 6
    = -48
    = 2
    *** -48=3\!\!\pmod{17}...and nevertheless the result is correct! Mistake + mistake = correct.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 11th 2011, 08:50 PM
  2. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 8th 2011, 10:45 AM
  3. Modular Arithmetic- Quick question
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 30th 2011, 05:12 PM
  4. Quick question on graphs and modular arithmetic
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: March 25th 2010, 06:36 PM
  5. Modular arithmetic
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: February 28th 2010, 10:45 AM

Search Tags


/mathhelpforum @mathhelpforum