Brainteaser: remainder of 11^345678 / 13

[Wiemster]

I stumbled upon this seamingle impossible question (without calculator!), any ideas to find the remainer of

\frac{11^{345678}}{13}?

 

[CRGreathouse]

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 let's you solve the problem quickly?

 

[snipez90]

Well by a well-known theorem of Fermat's, I've got it down to finding the remainder when 11^6 is divided by 13.

 

[snipez90]

And due to CRGreathouse's pattern, the problem is solved (unless of course I made an error).

 

[Wiemster]

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 let's you solve the problem quickly?

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!