How to compute things like $528^{843^{418}} \pmod {25}$?

Question

What is the general algorithm to find modulo of this type of numbers: $528^{\large843^{418}}$ for modulo $25$ for example? I've tried to find $528$ by modulo $25$, but it was useless for me.

Answer 1

Generically one has that $a^{\varphi(n)} \equiv 1 \pmod n$ for positive integers $a$ and $n$, and where $\varphi(n)$ is the Euler totient function of $n$, which gives the number of positive integers up to $n$ which are relatively prime to $n$. This is called Euler's Theorem.

In this problem $\varphi(25) = 20$, so for example $528^{843} \equiv 528^3 \equiv 3^{3} \equiv 2 \pmod{25}$.

However you have an additional exponent, and this requires some thought.

Since $528^b \equiv 528^{b + k\varphi(25)} \equiv 528^{b + 20k} \pmod{25}$ for any (wlog positive) integers $b$ and $k$, it is clear that the exponent $b$ is defined mod $\varphi(25) = 20$. In fact this follows from Euler's Theorem above.

In your problem, the exponent is $843^{418}$, and we see this is to be considered modulo $\varphi(25) = 20$. In trying to understand $$ 843^{418} \pmod{20},$$ we can again use Euler's Theorem. Now, $\varphi(20) = 8$. So $$ 843^{418} \equiv 843^{418 \pmod 8} \equiv 843^{2} \equiv 3^2 \equiv 9 \pmod{20}.$$ And so $$528^{843^{418}} \equiv 3^9 \pmod {25},$$ and the initially intractable problem has been reduced to a much easier problem. The rest follows quickly if one notes that $3^3 = 27 \equiv 2 \pmod{25}$, so that $3^9 = (3^3)^3 \equiv 2^3 \pmod {25}$.

Answer 2

Hint:

Use $a\equiv b\pmod m\implies a^t\equiv b^t$

and for $(b,m)=1,$

$$b^r\equiv b^{r\pmod{\lambda(m)}}\pmod m$$

Here $a=528,b=?$(choose the smallest possible positive integer)

Answer 3

Reducing $528 \bmod 25$ is a reasonable place to start, giving you $528^{\large843^{418}} \equiv 3^{\large843^{418}} \bmod 25$. Then you can set about investigating the powers of $3 \bmod 25$, which do in fact cycle through the $20$ values $0<a<25$ coprime to $25$. There are results that predict this but it is worthwhile to work through the cycle to satisfy yourself of this.

Then you can establish the same logic to the next portion of the tower, reducing $843^{418} \bmod 20$. Then once this is complete you can feed the results back down into the original expression.

---

Continuing to completion$\newcommand{thrice}{\overset{{}_{\times 3}}{\to}}$

So considering $843^{418} \equiv 3^{418} \bmod 20$, we can check the values of $3^k \bmod 20$:
$1\thrice 3 \thrice 9\thrice (27\equiv 7)\thrice (21\equiv 1)$ for a cycle of length $4$.

Then - last step up - we can reduce $418 \equiv 2\bmod 4$.

Thus we have $843^{418} \equiv 3^{418} \equiv 3^2 \equiv 9 \bmod 20$.

And $528^{\large843^{418}} \equiv 3^{\large843^{418}} \equiv 3^9 \equiv 27^3 \equiv 2^3 \equiv 8 \bmod 25$.