# 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?

• Unless I made an error, the cycle is: 1, 9, 81, 29, 61, 49, 41, 69, 21, 89 Which is 10 numbers, so now you need to find 9^9 mod 10, 9^9 = (10-1)^9 and you see that it will be (-1)^9 mod 10. – mathreadler Feb 27 '15 at 18:17
• – punctured dusk Aug 20 '15 at 11:45

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 M Sep 18 '11 at 7:16

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

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

So $$\rm \bmod 100\!:\, \ 9^{\large 9^{\LARGE 9}}\!\!\equiv\ 9^{\large 9^{\LARGE 9}\, mod\ \color{#c00}{10}} \equiv\ 9^{\large (-1)^{\LARGE 9}}\!\! \equiv 9^{\large -1}\!\equiv \dfrac{1}9 \equiv \dfrac{-99}9 \equiv {-}11 \equiv 89$$

Remark  Above we used the useful fact that if the powers of $$\,a=9\,$$ repeat with period length $$\color{#c00}{10}\,$$ then all exponents on $$\,a\,$$ can be taken modulo $$\,\color{#c00}{10}.\,$$ Said more precisely we used the following

$$\ \ \color{#c00}{a^{\color{#c00}{\large 10}}\equiv 1}\!\!\pmod{\!m},\,\ J\equiv K\!\!\!\pmod{\!\color{#c00}{10}}\ \,\Rightarrow\,\ a^{\large J}\equiv a^{\large K}\!\!\!\!\pmod{\!m}$$

for the specific values $$\ a=9,\,$$ and $$\,J = 9^{\large 9},\,$$ and $$\,K = (9^{\large 9}\,{\rm mod}\ 10).\,$$ A proof is easy:

$$J = K\! +\! 10N\,\Rightarrow\, a^{\large J}\! = a^{\large K+10N}\! = a^{\large K} (\color{#c00}{\large a^{10}})^{\large N}\!\equiv a^{\large K} \color{#c00}1^{\large N}\!\equiv a^{\large K}\!\!\!\!\pmod{\!m}\qquad$$

where we have employed the  Congruence Product and Power Rules. For further discussion see modular order reduction.

Beware  Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

• 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