# Finding the last two digits of $9^{9^{9^{…{^9}}}}$ (nine 9s) [duplicate]

I'm continuing on my journey learning about modular arithmetic and got confused with this question:

Find the last two digits of $$9^{9^{9^{…{^9}}}}$$ (nine 9s). The phi function is supposed to be used in this problem and so far this is what I've got:

$$9^{9^{9^{…{^9}}}} ≡ x (\text{mod } 100)$$ Where $$0 ≤ x ≤ 100$$

$$9^{9^{9^{…{^9}}}} \text{ (nine 9s) }= 9^a$$ In order to know $$9^a (\text{mod } 100)$$, we need to know $$a (\text{mod } \phi(100))$$ As $$\phi(100)= 40$$, we get $$a = b (\text{mod } 40)$$

$$9^{9^{9^{…{^9}}}} \text{ (eight 9s) }= 9^b$$ In order to know $$9^b (\text{mod } 40)$$, we need to know $$b (\text{mod } \phi(40))$$ As $$\phi(40)= 16$$, we get $$b = c ( \text{mod }16)$$

$$9^{9^{9^{…{^9}}}}\text{ (seven 9s) }= 9^c$$ In order to know $$9^c (mod 16)$$, we need to know $$c (\text{mod } phi(16))$$ as $$\phi(16)= 8$$ we need to find $$c (\text{mod } 8)$$

As $$9 = 1 (\text{mod } 8)$$ $$c = 1 (\text{mod } 8)$$

I feel like I might have made a mistake somewhere along the way because I'm having a lot of trouble stitching it all back together in order to get a value for the last two digits. Could anyone please help me with this? Thank you!

Hint. Consider $$a_n=9^{9^{2n+1}}$$ and show by induction that $$a_n\equiv 89\pmod{100}$$ for $$n\in\mathbb{N}$$.
By the binomial theorem, we have that $$a_0=9^9=(10-1)^9\equiv 9\cdot 10^1 (-1)^8 +(-1)^9=90-1=89\pmod{100}.$$ Moreover, for $$n\geq 0$$, $$a_{n+1}=9^{81\cdot 9^{2n+1}}=a_n^{81}\equiv 89^{81}\equiv ?\pmod{100}$$ Can you take it from here? (you already noted that $$\varphi(100)=40$$).