Results 1 to 5 of 5

Math Help - finding remainder of a division

  1. #1
    Member
    Joined
    Jan 2008
    Posts
    114

    finding remainder of a division

    Find the remainder of the division of 23^{666342} by 49

    Could someone please explain how I would do this without a calculator??

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    23^{666342} = (23^{333171})^2
    23^{333171} = (23^{166585})^2\cdot 23
    23^{166585} = (23^{83292})^2\cdot 23
    23^{83292} = (23^{41646})^2
    23^{41646} = (23^{20823})^2
    23^{20823} = (23^{10411})^2\cdot 23
    ...
    and so on until you have come down to 23^1, is one way. Then you will have to work your way up again, but use the modulus rule a\cdot b\ (mod\ x) = (a\ (mod\ x))\cdot (b\ (mod\ x)) this time to get the values in the interval [0, 49).

    Another way is to make a table over modulus values for different exponents of 23.

    23^1\ (mod\ 49) = 23
    23^2\ (mod\ 49) = 23^1\cdot 23\ (mod\ 49) = 23\cdot 23\ (mod\ 49) = 39
    23^3\ (mod\ 49) = 23^2\cdot 23\ (mod\ 49) = 39\cdot 23\ (mod\ 49) = 15
    ...
    and so on. Eventually, you will get the same modulu value as you have had before, then you know that the modulu values will begin to repeat. When you have found the period of repetition (in this case 23^{22}\equiv 23^1\ (mod\ 49), so the period will be 21), you can calculate which of the exponents in your table that has the same modulu value as 2^{666342}.
    Last edited by TriKri; February 17th 2008 at 07:00 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,553
    Thanks
    542
    Hello, hunkydory19!

    Find the remainder of the division of 23^{666342} by 49
    There is a rather primitive method for solving these . . .
    . . (I'll omit a LOT of the trial-and-error that I used.)


    We try: . 23^7 \:=\:3,404,825,497

    . . Then: . 3,404,825,497 \;=\;(49)(69,486,233) + 30

    Hence: . 23^7 \;=\;49a + 30



    Then: . 23^{14} \;=\;(23^7)^2

    . . . . . . . . =\;(49a + 30)^2

    . . . . . . . . =\;49^2a^2 + 60\!\cdot\!49a + 900

    . . . . . . . . = \;49^2a^2+60\!\cdot\!49a + (49)(14) + 18

    . . . . . . . . = \;49(49a^2 + 60a + 14) + 18

    Hence: . 23^{14} \;=\;49b + 18



    Then: . 23^{21} \;=\;(23^7)(23^{14})

    . . . . . . . . = \;(49a + 30)(49b + 18)

    . . . . . . . . = \;49^2ab + 18\!\cdot\!49a + 30\!\cdot\!49b + 540

    . . . . . . . . = \;49^2ab + 18\!\cdot\!49a + 30\!\cdot\!49b + (49)(11) + 1

    . . . . . . . . = \;49(49ab + 18a + 30b + 11) + 1

    Hence: . 23^{21} \;=\;49c + 1

    That is: . 23^{21} \div 49 has a remainder of 1.



    Then: . 23^{666342} \;=\;23^{666330}\cdot23^{12} \;=\;(23^{21})^{31730}(23^{12})\;\to \;1^{31730}\cdot23^{12} \:=\:23^{12}


    Now go to work on 23^{12}

    . . [Hint: . 23^4 \:=\:49k + 2]

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    There are 21 mod 49 residues.

    We note that 666342\equiv{12(mod \;\ 21)}

    This tells us that 666342 is 12 more than a multiple of 21.

    So, 23^{666342}=23^{12}\equiv{8(mod \;\ 49)}

    The remainder is 8.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    Soroban, why did you choose 7 as an exponent? And galactus, how did you know that there are 21 mod 49 residues? Are there any quick ways?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division and remainder
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 13th 2011, 04:46 AM
  2. Remainder with polynomial division
    Posted in the Algebra Forum
    Replies: 6
    Last Post: August 8th 2011, 12:52 PM
  3. The remainder of integer division
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: November 9th 2010, 01:51 AM
  4. Replies: 3
    Last Post: November 5th 2010, 03:43 PM
  5. Finding remainder of polynomial division
    Posted in the Algebra Forum
    Replies: 7
    Last Post: October 29th 2008, 02:51 PM

Search Tags


/mathhelpforum @mathhelpforum