# How do I compute $a^b\,\bmod c$ by hand?

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) \neq 1$, 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: Coping with *abstract* duplicate questions.

-
How do I make this community wiki? I couldn't find the option, so I flagged it for moderator attention... – user7530 Nov 11 '11 at 22:07
fermat's little theorem – geraldgreen Nov 11 '11 at 22:37
It may be laborious when $c$ is huge, but $b$ being huge should be no problem. – Michael Hardy Nov 11 '11 at 22:45

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 \equiv = 5 \times 25^2 \equiv 5 \times 1^2 = 5 \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$.

-
Carmichael function often reduces the exponent more than Euler's totient function. – user26486 Feb 18 '15 at 9:56

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$

-

In general, squared exponentiation is used, this is $O(\log(b) \cdot \log(n))$ if multiplication $\bmod n$ is $O(\log (n))$.

powmod(a,b,n){
res=1;
fact=a;
while(b>0){
res=(res*(b%2)==1?fact:1)%n;
fact=(fact*fact)%n;
b=floor(b/2);
}
}


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

-

Let's try $5^{844325} \mod 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$.

-
You may want to check my arithmetic, but this method will do it when you get that right. – Michael Hardy Nov 11 '11 at 23:05
This method won't be so nice when $(5,21)\neq 1$... – mathmath8128 Nov 11 '11 at 23:53
@aengle: it will be similar: for example for $6^{844325} \mod 21$ you would look at $6^0 \equiv 1$, $6^1 \equiv 6$, $6^2 \equiv 15$, $6^3 \equiv 6$, $6^4 \equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} \equiv 15 \mod 21$ and thus $6^{844325} \equiv 6 \mod 21$. – Henry Nov 12 '11 at 1:38