<s>[INST] Evaluate $7^{8^9}\mod 100$ 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?
 [/INST] 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. 
</s>