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

How do I successfully calculate $a^b\bmod c$ :

- When $b$ is massive, as an example $5^{844325}\bmod 21$ ?
- When $b$ is much less than $c$ yet it would certainly still be a great deal of job to increase $a$ on its own $b$ times, as an example $5^{69}\bmod 101$ ?
- When $(a,c)\ne1$ , as an example $6^{103}\bmod 14$ ?

Exist any kind of various other methods for reviewing backers in modular arithmetic?

This is being asked in an initiative to lower matches, see here and also here.

For the first inquiry: make use of $a^{\Phi(c)}=1 \mod c$, where $\Phi(c)$ is the variety of coprimes to $c$ listed below $c$. For $c=21=7\cdot 3$ we have $\Phi(c)=(7-1)\cdot(3-1)=12$

2nd inquiry: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and more. Decay the backer right into powers of 2 and also incorporate them making use of $a^n\cdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}\cdot a^4\cdot a^1$.

Let is attempt $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 increasing by $5$ 6 times coincides as increasing by $1$. We intend to increase by $5$ a lot of times: $844325$. The amount of times do we increase by $5$ 6 times? The variety of times $6$ enters into $844325$ is $140720$ with a rest of $5$. That rest is what issues. Multiply by $5^6$ specifically $140720$ times which coincides as increasing by $1$ that sometimes. After that increase by $5$ simply $5$ extra times, and also get $17$.

So $5^{844325} \equiv 17 \bmod 21$.

In basic, made even exponentiation is made use of, this is $O(\log(b) \cdot \log(n))$ if reproduction $\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
```

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 massive (much bigger than $n$ ) you can (effort) to locate the ranking of the ring ( $\varphi(n)$ ) and also locate the rest of $b \pmod {\varphi(n)}$ due to the fact that $a^b \bmod n= a^{b \mod \varphi(n)} \bmod n$ (for $21$ , it is $(3-1) \cdot (7-1)=12$ ) this calls for locating the prime variables of $n$ .

As a whole the ranking for $n = \prod{(p_i)^{k_i-1} \cdot (p_i-1)}$ with $p_i^{k_i}$ the prime variables of $n$ .

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

Related questions