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?

This is being asked in an effort to cut down on duplicates, see here and here.
Wikipage on modular arithmetic is not bad.


When $b$ is huge, and $a$ and $c$ are coprime, Euler's theorem applies:
$$
    a^b \equiv a^{b \, \bmod  \, \phi(c)} \, \bmod c
$$
For the example at hand, $\phi(21) = \phi(3) \times \phi(7) = 2 \times 6 = 12$. $ 844325 \bmod 12 = 5$, so $5^5 = 5 \times 25^2 \equiv 5 \times 4^2 = 80 \equiv 17 \mod 21$.
When $a$ and $c$ are coprime, but $0&lt;b&lt;\phi(c)$, repeated squaring (or using other compositions of powers) is the fastest way to go (manually):
$$
\begin{eqnarray}
   5^4 \equiv 5 \times 5^3 \equiv 5 \times 24 \equiv 19 &amp;\pmod{101}\\
   19^4 \equiv (19^2)^2 \equiv 58^2 \equiv (-43)^2 \equiv 1849 \equiv 31 &amp;\pmod{101} \\
   31^4 \equiv (31^2)^2 \equiv (961)^2 \equiv 52^2 \equiv 2704 \equiv 78 &amp;\pmod{101} \\
   5^{69} \equiv 5 \times 5^4 \times ((5^4)^4)^4 \equiv 5 \times 19 \times 78 \equiv 5 \times 19 \times (-23)\\
 \equiv 19 \times (-14) \equiv -266 \equiv  37 &amp; \pmod{101} 
\end{eqnarray}
$$
When $a$ and $c$ are not coprime, let $g = \gcd(a,c)$. Let $a = g \times d$ and $c = g \times f$, then, assuming $b &gt; 1$:
$$
   a^b \bmod c = g^b \times d^b \bmod (g \times f) = ( g \times (g^{b-1} d^b \bmod f) ) \bmod c
$$
In the example given, $\gcd(6,14) = 2$. So $2^{102} \times 3^{103} \mod 7$, using Euler'r theorem, with $\phi(7) = 6$,  and $102 \equiv 0 \mod 6$, $2^{102} \times 3^{103} \equiv 3 \mod 7$, so $6^{103} \equiv (2 \times 3) \equiv 6 \mod 14 $.
Its not hard to show that the sequence

$$
x_n=a^n\mod{c}
$$

is periodic, with period $p$ (which is at most $c$). Evaluate the first few terms to get the period $\{x_0,x_1,\dots,x_{p-1}\}$. Then you can evaluate for any huge power $n$ as

$$
x_n=x_{n\mod{p}}
$$