Evaluate $7^{8^9}\mod 100$

Question

I'm preparing myself for discrete math exam and here's one of the preparation problems:

Evaluate $$7^{8^9}\mod 100$$

Here's my solution: $7^2\equiv49 \mod 100\implies (7^2)^2\equiv49^2=2401\equiv 1\mod 100$

So, as it turns out $7^4\equiv 1\mod 100$. It will be useful later. Now let's examine $8^9\mod 100$.

We have $512=8^3\equiv 12 \mod 100$, so $(8^3)^3\equiv 12^3 = 1728 \equiv 28 \mod 100$. So, as $8^9\equiv 28 \mod 100$, then $8^9=100x+28$ for some natural $x$. So:

$7^{8^9}=7^{100x+28}=7^{100x}7^{28}=(7^4)^{25x}(7^4)^7\equiv 1^{25x}1^7 \equiv 1 \mod 100$

Which means the final answer is that $7^{8^9}\mod 100=1$.

That's my solution, but I'm curious about other ones. Has anybody have any ideas?

Answer 1

$7^2\equiv -1\mod 50$, hence $7^4\equiv 1\mod 100$.

Thus $\,7^{8^9}=\bigl(7^8\bigr)^{8^8}=\bigl((7^4)^2\bigr)^{8^8}\equiv 1\mod 100$.

Answer 2

If you know $7^4 = 1 \mod 100$, then since your desired quantity is a power of this $7^4$, you will have that that also is $1 \mod 100$ automatically.

Answer 3

Carmichael's function $\lambda(100) = \text{lcm}(\lambda(25),\lambda(4)) = \text{lcm}(20,2) = 20$.

$7$ is coprime to $100$, so $7^{8^9} \equiv 7^{8^9 \bmod 20} \bmod 100$

$\lambda(20) = \text{lcm}(\lambda(5),\lambda(4)) = \text{lcm}(4,2) = 4$ and $9 \equiv 1 \bmod 4$

$8$ has a higher exponent than $20$ in $2$, their only shared prime factor, so $8^9 \equiv 8 \bmod 20$

This gives $7^{8^9} \equiv 7^{8^9 \bmod 20} \equiv 7^{8} \bmod 100$

So we just need to square $7$ three times to get our answer... but when we get to $49^2$ we happily discover that $49^2 = (50-1)^2 \equiv 1 \bmod 100$.

So $7^{8^9} \equiv 7^{8} \equiv ((7^2)^2)^2 \equiv (49^2)^2 \equiv 1^2 \equiv 1 \bmod 100$

It's perfectly legitimate, of course, to find out $7^8 \bmod 100$ first in the hope that it will be something convenient, but this is a method that will work in the absence of good fortune.