# The last two digits of $9^{9^9}$

I tried to calculate the last two digits of $9^{9^9}$ using Euler's Totient theorem, what I got is that it is same as the last two digits of $9^9$.

How do I proceed further?

-

At this point, it would seem to me the easiest thing to do is just do $9^9 \mod 100$ by hand. The computation should only take a few minutes. In particular, you can compute $9^3$ and then cube that.

-
Another route is 9*((9^2)^2)^2 mod 100, because repeated modular squaring is faster and just about as easy as repeated modular multiplication. –  anon Sep 18 '11 at 7:09
Both take 4 multiplications in this case. For me this was faster because I knew $9^3=729$ off the top of my head, but repeated squaring is certainly faster in most cases. –  Logan Maingi Sep 18 '11 at 7:16

Euler's Theorem is not needed. It can be solved completely using only the Binomial Theorem:

$$\rm 9^{10}\: =\ (10-1)^{10} =\: (-1)^{10} - 10\cdot 10 + 10^2\:(\cdots)\ \equiv\ 1\ \ (mod\ 100)$$

Hence $\rm\ mod\ 100:\ \ 9^{\:9^9}\!\equiv\ 9^{\:9^9\ mod\ 10}\ \equiv\ 9^{\:(-1)^9}\! \equiv\ 1/9\ \equiv\ {-99}/9\ \equiv\ {-}11\ \equiv\ 89\:.$

-
Nice, you went and applied BT to the original problem. It should be noted that you chose to look at $9^{10}$ because all but the first and second terms invariably vanish, but choosing an exponent of $10$ makes the second vanish as well. And $1/9\equiv-99/9$ was a fast way to compute a modular inverse. –  anon Sep 18 '11 at 7:39

By the binomial theorem, we have $$(-1+10)^9\equiv{9\choose0}(-1)^910^0+{9\choose1}(-1)^810^1+{9\choose2}(-1)^7{\color{Red}{10^2}}+\cdots$$ $$\equiv-1+90=89\pmod{10^2}.$$ (All summands with powers of $10$ greater than $1$, the first instance in red, can be ignored.)

-
Decent explanation +1; I am wondering how the OP is using Euler theorem for the reduction?, If am not wrong it gives $9^{40} \equiv 1 \pmod {100}$ ... –  Quixotic Nov 11 '11 at 6:15

Another method is to use an online calculator. wolframalpha.com input 9^(9^9) mod 100.