1. ## Find the remainder

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!

2. 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.

3. Originally Posted by steph3824
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!
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

4. Thanks to both of you..I see how to do it now