Modular exponentiation by hand ($a^b\bmod c$) How do I efficiently compute $a^b\bmod c$:

*

*When $b$ is huge, for instance $5^{844325}\bmod 21$?

*When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, for instance $5^{69}\bmod 101$?

*When $(a,c)\ne1$, for instance $6^{103}\bmod 14$?

Are there any other tricks for evaluating exponents in modular arithmetic?

Here are two examples of the square and multiply method for $5^{69} \bmod 101$:
$$ \begin{matrix}
5^{69} &\equiv& 5 &\cdot &(5^{34})^2 &\equiv & 37
\\ 5^{34} &\equiv& &&(5^{17})^2 &\equiv& 88 &(\equiv -13)
\\ 5^{17} &\equiv& 5 &\cdot &(5^8)^2 &\equiv& 54
\\ 5^{8} &\equiv& &&(5^4)^2 &\equiv& 58
\\ 5^{4} &\equiv& &&(5^2)^2 &\equiv& 19
\\ 5^{2} &\equiv& &&(5^1)^2 &\equiv& 25
\\ 5^{1} &\equiv& 5 &\cdot &(1)^2 &\equiv& 5
\end{matrix} $$
The computation proceeds by starting with $5^{69}$ and then working downward to create the first two columns, then computing the results from the bottom up. (normally you'd skip the last line; I put it there to clarify the next paragraph)
As a shortcut, the binary representation of $69$ is $1000101_2$; reading the binary digits from left to right tell us the operations to do starting from the value $1$: $0$ says "square" and $1$ says "square and multiply by $5$".

The other way is to compute a list of repeated squares:
$$ \begin{matrix}
5^1 &\equiv& 5
\\ 5^2 &\equiv& 25
\\ 5^4 &\equiv& 19
\\ 5^8 &\equiv& 58
\\ 5^{16} &\equiv& 31
\\ 5^{32} &\equiv& 52
\\ 5^{64} &\equiv& 78
\end{matrix} $$
Then work out which terms you need to multiply together:
$$ 5^{69} \equiv 5^{64 + 4 + 1} \equiv 78 \cdot 19 \cdot 5 \equiv 37 $$
