# 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.

## Answer

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$$.

Attribution
Source : Link , Question Author : user7530 , Answer Author : upe