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.