The Four Nines

No need to multiply anything more than the last 2 digits. How the last 2 digits of powers of 9 cycle: 9, 81, 29, 61, 49, 41, 69, 21, 89, 1, 9 The 9th power will be 89. How the last 2 digits of the powers of 89 cycle: 89, 21, 69, 41... Wait... aren't these all in reverse?

Using logic, 9^9 = 89, 89^9 = 9. Cycling this back and forth from 9 to 89 to 9 to 89, I came up with 89 as the answer.

$9^{9^{9^9}} \equiv ? \pmod{100}$

First, we know that $100=4\times25$ and (4,25) are coprime integers. Therefore, we can find these values separately.

$9^{9^{9^9}}\equiv ? \pmod{4}$

$9^{9^{9^9}}\equiv ? \pmod{25}$

The former is easy to find as $9^n \equiv 1^n \equiv 1 \pmod{4}$

Now we find the latter.

Using Euler's theorem,

$9^{20} \equiv 1 \pmod{25}$

Thus we first find $9^{9^9} \pmod{20}$

Since $9^{9^9}\equiv 1 \pmod{4}$ and $9^{9^9} \equiv 4 \pmod{5}$ ,

By Chinese Remainder Theorem,

$9^{9^9} \equiv 9 \pmod{20}$

$\therefore 9^{9^9} = 20k + 9$

Substituting yields:

$9^{9^{9^9}} \equiv 9^{20k+9} \equiv 9^9 \equiv 14 \pmod{25}$

Now we have

$9^{9^{9^9}} \equiv 1 \pmod{4}$

and

$9^{9^{9^9}} \equiv 14 \pmod{25}$

By Chinese Remainder Theorem again yields:

$9^{9^{9^9}} \equiv \boxed{89} \pmod{100}$