How to find high power numbers modulo

Question

How can I find high power number modulo number. What If I have to do it with the calculator or if the calculator is not allowed in exam.

For example: $174^{55} \pmod {221} \equiv 47$

Answer 1

Some of the useful tools to do this are

• Fermat's little theorem (special case of below)
• Euler's totient theorem (general case of above)
• Repeated squaring, i.e., $a \equiv b \pmod{n} \implies a^n \equiv b^n \pmod{n}$. You can do this more efficiently by exponentiation by squaring.
• Aryabhatta's remainder theorem

For the specific problem, note that $221 = 13 \times 17$. From Fermat's little theorem, we have $$174^{12} \equiv 1\pmod{13} \text{ and }174^{16} \equiv 1\pmod{17}$$ Hence, $$174^{48} \equiv 1 \pmod{13} \text{ and }174^{48} \equiv 1 \pmod{17}$$ Further, $$174 \equiv 5\pmod{13} \implies 174^2 \equiv -1\pmod{13} \implies 174^7 \equiv 8\pmod{13}$$ $$174 \equiv 4\pmod{17} \implies 174^2 \equiv -1\pmod{17} \implies 174^7 \equiv 13\pmod{17}$$ This gives us that $$174^{55} \equiv 8 \pmod{13} \text{ and }174^{55} \equiv 13 \pmod{17}$$ Now use Aryabhatta's remainder theorem to conclude that $$174^{55} \equiv 47 \pmod{221}$$

Answer 2

I'll add an example of fast exponentiation at it can be programmed on a hand-held calculator.

A pseudo-code is this:

Input: $a, n, k, m$: integers;

Output: $P=a^n\mod m$

$k:=n$; $P:=1$;

Repeat

If $k$ is odd then $P:= P*a\,$; endif

$a:=a^2$; $k:=\Bigl\lfloor\dfrac k2\Bigr\rfloor$

until $k=1$.

Here is a example with $a=174$, $n=55$, $m=211$ (which is prime):

$$\begin{array}{rrcr} n&P&&a^k\\ \hline 55&174&\times&103\\ 27&198&\times&59\\ 13&77&&105\\ 6&77&\times&53\\ 3&72&\times&66\\ 1&\color{red}{110}\\ \hline \end{array}$$