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?

Let's try $5^{844325} \bmod 21$:
$$
\begin{align}
5^0 & & & \equiv 1 \\
5^1 & & &\equiv 5 \\
5^2 & \equiv 25 & & \equiv 4 \\
5^3 & \equiv 4\cdot 5 & & \equiv 20 \\
5^4 & \equiv 20\cdot 5 & & \equiv 16 \\
5^5 & \equiv 16\cdot 5 & & \equiv 17 \\
5^6 & \equiv 17\cdot 5 & & \equiv 1
\end{align}
$$
So multiplying by $5$ six times is the same as multiplying by $1$.  We want to multiply by $5$ a large number of times: $844325$.  How many times do we multiply by $5$ six times?  The number of times $6$ goes into $844325$ is $140720$ with a remainder of $5$.  That remainder is what matters.  Multiply by $5^6$ exactly $140720$ times and that's the same as multiplying by $1$ that many times.  Then multiply by $5$ just $5$ more times, and get $17$.
So $5^{844325} \equiv 17 \bmod 21$.
