1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...