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?
 A: For the  first question: use $a^{\Phi(c)}=1 \mod c$, where $\Phi(c)$ is the number of coprimes to $c$ below $c$. For $c=21=7\cdot 3$ we have $\Phi(c)=(7-1)\cdot(3-1)=12$
second question: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and so on. Decompose the exponent into powers of 2 and combine them using $a^n\cdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}\cdot a^4\cdot a^1$
A: 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$.
$$
\Rightarrow 844325 \bmod 12 = 5,\ \text{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<b<\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 &\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 $a$ and $c$ are not coprime, let $g = \gcd(a,c)$. Let $a = g \times d$ and $c = g \times f$, then, assuming $b > 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 $.
A: 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$.
A: There are a few things of note:


*

*Exponent rules help. If b is a large composite, being the product of d,e,f,g,h,i,j,... then powering to b is like powering by d then e then f then g doing each in turn to your results, is easier (maybe as tedious) than one big computation.

*If a and c are coprime, then a raised to any power will also be coprime, so either you use up all coprime remainders or you don't but you can tell by powering until the remainder is 1, and 1 raised to any power is 1 letting you trim b down. (basically behind Euler and Fermat)

*if a and c are not coprime, then powers of a, sit at multiples of their gcd.

*Exponent rules help again if you find a sum equal to b you can use the product of same base powers = sum of exponents rule.(binary exponentiation uses this)

*if a is larger than half of c, use -(c-a) in its place (another name for a) 

*if a>c, take a mod c first.

*etc.

A: Specifically in the case of $\gcd(a,c)\ne1$, we can use a generalization of Euler's totient theorem, which gives us:
$$a^b\equiv a^{(b\bmod\varphi)+\varphi}\pmod c$$
where $b>\varphi=\varphi(c)$.
Using the Chinese remainder theorem, this can be improved to $\varphi=\varphi(c')$, where $c'$ is the greatest factor of $c$ that is coprime to $a$. For a brute force computation of $c'$, one can use $c'=c/\gcd(a^{\lfloor\log_2(c)\rfloor},c)$.
When we have $b<2\varphi$, we can then apply exponentiation by squaring.
In your example:
$\varphi(c')=\varphi(7)=6$, so $\bmod14:$
$6^{103}\\\equiv6^{(103\bmod6)+6}\\=6^7\\=6\times36^3\\\equiv6\times8^3\\=48\times64\\\equiv6\times8\\=48\\\equiv6$
A: 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 $$
A: Adding an example for calculating the remainder of an iterated power. 

Let's find the two last digits of $97^{75^{63}}$.

Equivalently, we want to find its remainder modulo $100$.


*

*First we observe that $\gcd(97,100)=1$. If we had common prime factors here we would deal with each prime power separately using the Chinese remainder theorem. See also this answer (and the following three steps). Given that $\phi(100)=40$, we can immediately deduce that $97^{40}\equiv1\pmod{100}$. 

*Therefore we next need to determine the remainder of the exponent $75^{63}$ modulo $40$. Observe that $\gcd(75,40)=5$, so the power is obviously a multiple of five. We need to determine its residue class modulo $40/5=8$.

*Modulo $8$ we have $75\equiv3$. Therefore $75^{63}\equiv3^{63}\pmod 8$. We see that $3^2=9\equiv1\pmod8$, so $3^{63}\equiv3\pmod8$.

*So we know that $75^{63}$ is divisible by $5$ and leaves remainder $3$ modulo $8$. Because $35$ has these same remainders modulo $5$ and $8$, and $\gcd(5,8)=1$, the Chinese remainder theorem tells us that $75^{63}\equiv35\pmod{40}.$

*The huge number
$97^{75^{63}}$ is thus congruent to $97^{35}\pmod {100}$. Now we can either resort to exponentiation by squaring or use other tricks. Whatever we do, the end result is that 
$$97^{35}\equiv93\pmod{100},$$
so we can conclude that the two last digits are $93$.



Instead of the Euler totient function $\phi(n)$ you may consider using the
Carmichael function $\lambda(n)$ instead. The workload may be reduced considerably. Particularly if an exponent has a small remainder modulo $\lambda(n)$, but a large remainder modulo $\phi(n)$.
A: Here we use a 'work out in place / lazy way / by hand' algorithm for the problem
$\quad$ Solve $5^{69}\,\bmod 101$.
$\; 5^{69} = \big((4 + 1) 5^2\big)^{23} \equiv 24^{23}=  24 \big((4 + 20) {24}\big)^{11} \equiv 24\, (71^{11}) \equiv  -24\, (30^{11}) =
$
$\quad  (-24)(30) \big((15 + 15) 30\big)^{5} \equiv (-24)(30)\, ({-9}^{5}) \equiv 24 \times 30 \times (-20) \times (-20) \times 9 \equiv  $
$\quad 24 \times 30 \times (-4)  \times 9 \equiv 24 \times (-19)  \times 9 \equiv  24 \times (-70) \equiv  24 \times 31 \equiv$
$\quad (24 \times 4) \times 8 - 24  \equiv -64 \equiv  37 \,\bmod 101$

Note: Since some discretion was used, we didn't actually specify an algorithm. But the work could be done to have a computer use simple lookup tables and produce similar outputs without using any math registers.
A: In general, squared exponentiation is used, this is $O(\log(b) \cdot \log(n))$ if multiplication $\bmod n$ is $O(\log (n))$.
def powmod(a, b, c):
    res = 1
    while b > 0:
        if b % 2 == 1:
            res = res * a % c
        a = a * a % c
        b //= 2
    return res

Try it online
Example for $5^{69}\bmod101$:
\begin{align}
5^{69}
& \equiv 5 \times (5^2)^{34} & \equiv 5 \times 25^{34} \\
& \equiv 5 \times (25^2)^{17} & \equiv 5 \times 19^{17} \\
& \equiv 5 \times 19 \times (19^2)^8 & \equiv 95 \times 58^8 \\
& \equiv 95 \times (58^2)^4 & \equiv 95 \times 31^4 \\
& \equiv 95 \times (31^2)^2 & \equiv 95 \times 52^2 \\
& \equiv 95 \times 78 \\
& \equiv 37
\end{align}

When $b$ is huge (much larger than $n$) you can (attempt) to find the rank of the ring ($\varphi(n)$) and find the remainder of $b \pmod {\varphi(n)}$ because $a^b \bmod n= a^{b \mod \varphi(n)} \bmod n$ (for $21$, it is $(3-1) \cdot (7-1)=12$) this requires finding the prime factors of $n$.
In general the rank for $n = \prod{(p_i)^{k_i-1} \cdot (p_i-1)}$ with $p_i^{k_i}$ the prime factors of $n$.
A: The Chinese remainder theorem can reduce the computation needed. For example, we can factor $21 = 3 \cdot 7$, and have 
$$ 1 \cdot 7 - 2 \cdot 3 = 1$$
(in general, we can use the extended Euclidean algorithm to produce this formula)
Consequently, if
$$x \equiv a \pmod 3 \qquad x \equiv b \pmod 7 $$
then
$$ x \equiv a \cdot (1 \cdot 7 ) + b \cdot (-2 \cdot 3) \pmod{21} $$
Thus, we can compute $5^{844325} \bmod 21$ by using our favorite means to compute:
$$ 5^{844325} \equiv 2 \pmod 3 \qquad 5^{844325} \equiv 3 \pmod 7 $$
and thus
$$ 5^{844325} \equiv 2 \cdot 7 + 3 \cdot (-6) \equiv -4 \equiv 17 \pmod{21} $$
A: 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}}
$$
