Computing large modular numbers How do you compute large modular arithmetic such as $8^{128}$ $mod$ $100$ or $10^{111}$ $mod$ $137$ or $3^{100}$ mod $17$? I know that one way is repeated squaring. For the first one, my book says 16, for the second 96, and third 13. It gives the answers but does not show how to do any of the three, the procedure, or even a example. If anyone could show me how the answers are derived, that would be wonderful!!

Using Fermat's little theorem, we know $a^b \equiv a^{(b \mod \phi(c))} \mod c$. So we can reduce exponents by subtracting any multiple of $\phi(c)$ until we get a number between $0$ and $\phi(c) - 1$. 


*

*First, $\phi(100) = \phi(2^25^2) = \frac{1}{2} \cdot \frac{4}{5} \cdot 100 = 40$ so $8^{128} \equiv 8^{128 - 3 \cdot 40} \equiv 8^8 \mod 100$. Now we do need a few computations, for instance using that $2^{10} = 1024$: $$8^8 \equiv 2^{24} \equiv 2^{10} \cdot 2^{10} \cdot 2^4 \equiv (1024) \cdot (1024) \cdot 16 \equiv 24 \cdot 24 \cdot 16 \equiv 16 \cdot 16 \equiv 16 \mod 100.$$

*Since $111 < \phi(137)$, the trick of subtracting multiples of $\phi(137)$ does not help here. But doing a few computations by hand gives us $10^3 = 1000 \equiv 41 \mod 137$ and $10^4 \equiv 410 \equiv -1 \mod 137$ which is a really nice, small number. So: 
$$10^{111} = 10^{108} \cdot 10^3 \equiv (10^4)^{27} \cdot 41 \equiv (-1)^{27} \cdot 41 \equiv -41 \equiv 96 \mod 137.$$

*Finally, $\phi(17) = 16$ and $100 = 6 \cdot 16 + 4$, so $$3^{100} \equiv (3^{16})^6 \cdot 3^4 \equiv 3^4 \equiv 81 \equiv 13 \mod 17.$$
