How to find high power numbers modulo 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$
 A: 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}$$
A: 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}$$
