Find the remainder when dividing 37^(217) by 11.
I already know that the answer to this is 7, I just am not sure why. I'd really appreciate it if someone could show me the steps please. Thanks!
37 = 4 (mod 11)
37^2 = 4^2 (mod 11) = 5 (mod 11)
37^4 = (37^2)^2 = 5^2 (mod 11) = 3 (mod 11)
37^8 = ... = 9 (mod 11)
37^16 = 81 (mod 11) = 4 (mod 11)
37^32 = 4^2 (mod 11) = 5 (mod 11)
37^64 = 5^2 (mod 11) = 3 (mod 11)
37^128 = 9 (mod 11)
37^192 = 37^128 * 37^64 = 9*3 (mod 11) = 5 (mod 11)
37^208 = 37^192 * 37^16 = 5*4 (mod 11) = 9 (mod 11)
37^216 = 37^208 * 37^8 = 9*9 (mod 11) = 4 (mod 11)
37^217 = 37^216 * 37 = 4*4 (mod 11) = 5 (mod 11)
quite simple and quick method for calculating big modulos. and sorry, the answer is not 7, it's 5. this was verified using calculator.
Doing all the operations modulo 11 and using Fermat's Little Theorem we get:
$\displaystyle 37=4\!\!\!\pmod{11}\,,\,217=11\cdot 20-3\Longrightarrow 37^{217}=(4^{11})^{20}4^{-3}$ $\displaystyle =4^{11}4^94^{-3}=4\cdot 4^6=4^7=2^{14}=2^{11}2^3=2^4=5\!\!\!\pmod{11}$
Tonio