# Modular exponentiation by hand (abmodca^b\bmod c)

How do I efficiently compute $$abmodca^b\bmod c$$:

• When $$bb$$ is huge, for instance $$5844325mod215^{844325}\bmod 21$$?
• When $$bb$$ is less than $$cc$$ but it would still be a lot of work to multiply $$aa$$ by itself $$bb$$ times, for instance $$569mod1015^{69}\bmod 101$$?
• When $$(a,c)≠1(a,c)\ne1$$, for instance $$6103mod146^{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 $$bb$$ is huge, and $$aa$$ and $$cc$$ are coprime, Euler’s theorem applies:
$$ab≡abmodϕ(c)modc a^b \equiv a^{b \, \bmod \, \phi(c)} \, \bmod c$$
For the example at hand, $$ϕ(21)=ϕ(3)×ϕ(7)=2×6=12\phi(21) = \phi(3) \times \phi(7) = 2 \times 6 = 12$$.
$$\Rightarrow 844325 \bmod 12 = 5,\ \text{so}\ 5^5 = 5 \times 25^2 \equiv 5 \times 4^2 = 80 \equiv 17 \mod 21 \Rightarrow 844325 \bmod 12 = 5,\ \text{so}\ 5^5 = 5 \times 25^2 \equiv 5 \times 4^2 = 80 \equiv 17 \mod 21$$.

• When $$aa$$ and $$cc$$ are coprime, but $$0, 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 &\pmod{101}\\ 19^4 \equiv (19^2)^2 \equiv 58^2 \equiv (-43)^2 \equiv 1849 \equiv 31 &\pmod{101} \\ 31^4 \equiv (31^2)^2 \equiv (961)^2 \equiv 52^2 \equiv 2704 \equiv 78 &\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 & \pmod{101} \end{eqnarray} \begin{eqnarray} 5^4 \equiv 5 \times 5^3 \equiv 5 \times 24 \equiv 19 &\pmod{101}\\ 19^4 \equiv (19^2)^2 \equiv 58^2 \equiv (-43)^2 \equiv 1849 \equiv 31 &\pmod{101} \\ 31^4 \equiv (31^2)^2 \equiv (961)^2 \equiv 52^2 \equiv 2704 \equiv 78 &\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 & \pmod{101} \end{eqnarray}$$

• When $$aa$$ and $$cc$$ are not coprime, let $$g = \gcd(a,c)g = \gcd(a,c)$$. Let $$a = g \times da = g \times d$$ and $$c = g \times fc = g \times f$$, then, assuming $$b > 1b > 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 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\gcd(6,14) = 2$$. So $$2^{102} \times 3^{103} \mod 72^{102} \times 3^{103} \mod 7$$, using Euler'r theorem, with $$\phi(7) = 6\phi(7) = 6$$, and $$102 \equiv 0 \mod 6102 \equiv 0 \mod 6$$, $$2^{102} \times 3^{103} \equiv 3 \mod 72^{102} \times 3^{103} \equiv 3 \mod 7$$, so $$6^{103} \equiv (2 \times 3) \equiv 6 \mod 14 6^{103} \equiv (2 \times 3) \equiv 6 \mod 14$$.