<s>[INST] Find the last two digits of $9^{{9}^{9}}$ I have to find the last two decimal digits of the number $9^{{9}^{9}}$.
That's what I did:
$$m=100 , \phi(m)=40, a=9$$
$$(100,9)=1, \text{ so from Euler's theorem,we have :} 9^{40} \equiv 1 \pmod{100}$$
$$9^{{9}^{9}} \equiv 9^{9^{2+2+2+2+1}} \equiv 9^{9^2 \cdot 9^2 \cdot 9^2 \cdot 9^2 \cdot 9} \equiv 9^{81 \cdot 81 \cdot 81 \cdot 81 \cdot 9} \equiv 9^{(40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot 9} \equiv (9^{(40+40+1)})^{(40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot 9} \equiv 9^9 \equiv 9^4 \cdot 9^4 \cdot 9 \equiv 6561 \cdot 6561 \cdot 9 \equiv 3721 \cdot 9 \\ \equiv 21 \cdot 9 \equiv 89 \pmod{100}$$
So,the last two digits are $8 \text{ and } 9$.
$$$$But,is there also an other way two calculate the last two digits of $9^{{9}^{9}}$ or is the above the only one?
 [/INST] A variant to minimise the computation time of the order of $9\bmod100$: by the Chinese remainder theorem,
$$\mathbf Z/100\mathbf Z\simeq\mathbf Z/4\mathbf Z\times \mathbf Z/25\mathbf Z. $$
Now $\varphi(25)=20$, and $9\equiv 1\mod4$. Hence $9^{20}\equiv 1\mod100$, so the order of $9$ is a divisor of 20.
Fast  exponentiation algorithm shows it has order $10$. Thus
$$9^{9^9}\equiv9^{9^9\bmod 10}\equiv 9^{(-1)^9\bmod 10}\equiv 9^{-1}\mod100. $$
Bézout's identity $\;100_11\cdot 9=1\;$ then shows $\; 9^{-1}\equiv -11\equiv 89\mod100$.
</s>