<s>[INST] Number Theory : What are the last three digits of $9^{9^{9^9}}?$ I was doing some basic Number Theory problems and came across this problem and was all thumbs :

Find the last three digits of $9^{9^{9^9}}$

How would I go about solving this problem? I am a newbie.
 [/INST] In order to compute $9^{9^{9^9}}\pmod{1000}$ we just need to compute $9^{9^9}\pmod{400}$, since $\phi(1000)=400$. So we just need to compute $9^9\pmod{160}$, since $\phi(400)=160$. Luckily,
$$ 9^8\equiv 1\pmod{160} $$
by the Chinese remainder theorem $\!\!\pmod{32}$ and $\!\!\pmod{5}$, so we just need to compute $9^9\pmod{400}$. Since $9^9\equiv 14\pmod{25}$ and $9^9\equiv 9\pmod{16}$, we have:
$$ 9^{9^9}\equiv 9^9 \equiv 89\pmod{400} $$
and the problems boils down to finding:
$$ 9^{89}\pmod{5^3},\qquad 9^{89}\pmod{8}.$$ 
The second one is easy: $9^{89}\equiv 1\pmod{8}$. The first one can be deduced from:
$$\begin{eqnarray*} 9^{89}=(10-1)^{89}&\equiv& (-1)^{89}+\binom{89}{1}10(-1)^{88}+\binom{89}{2}10^2(-1)^{87}\\&\equiv&-1+890-8900\cdot44\\&\equiv&-1+15-15\cdot440\\&\equiv&-1-15\cdot 64\equiv -86\equiv 39\pmod{125}\end{eqnarray*}$$
and the Chinese theorem gives:
$$9^{9^{9^9}}\equiv 9^{89} \equiv\color{red}{289}\pmod{1000}.$$
</s>