I'm trying to find the modular exponentiation for $60^{53} \text{ mod } 299$. I know it is $21$, but I would like to to show the answer step by step so that a normal calculator (with no modulo function) would be able to follow the solution steps.
I calculated the binary representation of $53$ = $110101_{2}$ = $2^{0+2+4+5} = 1+4+16+32$.
In the next step, I keep getting wrong results, I just find it very confusing. Can someone show me the correct approach?
Best Answer
Since $299 = 13 \cdot 23$, we can use Fermat's theorem for each factor:
$ \bmod 13: 60^{53} \equiv 8^5 \equiv 2^{15} \equiv 2^3 = 8 $
$ \bmod 23: 60^{53} \equiv 14^9 \equiv (-9)^9 \equiv -3^{18} \equiv -27^{6} \equiv -4^6 = -16^{3} \equiv 7^3 \equiv 21 $
Since $21 \equiv 8 \bmod 13$, we get $60^{53} \equiv 21 \bmod 299$.