Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Brainteaser: remainder of 11^345678 / 13

  1. Aug 18, 2008 #1
    I stumbled upon this seamingle impossible question (without calculator!), any ideas to find the remainer of

    [tex]\frac{11^{345678}}{13}[/tex]?
     
  2. jcsd
  3. Aug 18, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    11^0 = 1 (mod 13)
    11^1 = 11 (mod 13)
    11^2 = 4 (mod 13)
    11^3 = 5 (mod 13)
    11^4 = 3 (mod 13)
    11^5 = 7 (mod 13)
    11^6 = 12 (mod 13)
    11^7 = 2 (mod 13)
    11^8 = 9 (mod 13)
    11^9 = 8 (mod 13)
    11^10 = 10 (mod 13)
    11^11 = 6 (mod 13)
    11^12 = 1 (mod 13)
    11^13 = 11 (mod 13)
    11^14 = 4 (mod 13)
    . . .

    where x = y (mod 13) means x = y + 13k for some integer k.

    See how it 'loops around' at 11^0 = 11^12 = 1 (mod 13)? Can you see how this lets you solve the problem quickly?
     
  4. Aug 18, 2008 #3
    Well by a well-known theorem of Fermat's, I've got it down to finding the remainder when [tex]11^6[/tex] is divided by 13.
     
    Last edited: Aug 18, 2008
  5. Aug 18, 2008 #4
    And due to CRGreathouse's pattern, the problem is solved (unless of course I made an error).
     
  6. Aug 18, 2008 #5
    That's great. So I see what remains of 345678 when divided by 12, i.e. 6. Then I get that 345678 is dividable by 12 with a remainder of 6, so that 11^345678 = 11^(k*12+6). 11^(k*12)/13 has remainder 0 just as 11^0 / 13 from your list above. Then it is down to the remainder of 11^6/13 which can be calculated to be 12, nice!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Brainteaser: remainder of 11^345678 / 13
  1. Graph of Remainders (Replies: 1)

Loading...