<s>[INST] Last 3 digits of $3^{3^{3^3}}$ I am trying to find the last $3$ digits of $\,3^{\large 3^{3^3}}$, i.e. $\,3^{\large 3^{3^3}}\! \bmod 1000$. 
My idea is to apply Euler's totient function in some way, but I am unsure on how to proceed. Would someone be able to help me out? 
 [/INST] Hints:
First you should use the Chinese remainder theorem, i.e. determine the values $a$ and $b$ of $\;3^{3^{3^3}}$ modulo $8$ and $125$, then deduce its value modulo $1000$, with the formula deduced from a Bézout's identity between $8$ and  $125$: 
$$47\cdot 8-3\cdot 125=1$$
(found, e.g. by the extended Euclidean algorithm)
$$3^{3^{3^3}}\equiv b\cdot 47\cdot 8-a\cdot 3\cdot 125\mod 8\cdot125.$$
Now $a$ is easy to find since $3$ has order $2\bmod8$, so even powers of $3$ are congruent to $1$, odd powers congruent to $3$. Modulo $125$, it requires a little more work: as $\varphi(125)=100$, and $3$ is coprime to $125$, one has, by Euler's theorem,
$$3^{3^{3^3}}\equiv 3^{3^{3^3}\bmod100},$$
therefore we have  to compute the values of $\;3^{3^3}=3^{27}\bmod100$, which can be done by the fast exponentiation algorithm (‘square and divide’). Here is a layout. The last column contains the successive powers $P$ of $x$ (initially, $P=1$), until the exponent $n=27$ is attained
\begin{array}{rcll}
n&& \text{squaring}\;& P\\ \hline
27&& x & x \\
13 && x^2 & x^2\cdot x=x^3 \\ 
6 && x^4 & x^3 \\
3 && x^8 & x^8\cdot x^3 = x^{11} \\
1 && x^{16} & x^{16}\cdot x^{11}=x^{27}\\
\hline
\end{array}
You'll find $\;3^{3^3}\equiv 87\mod 100$. There remains to compute $\;3^{87}\bmod 125$, which can be done again with the fast exponentiation algorithm ($6$ squarings and $4$ multiplications mod. $125$).
It can be made a little faster using that $a^{87}\equiv a^{-13}=(a^{-1})^{13}\mod 125$. . As $3^{-1}\equiv 42\mod 125$, this amounts to $\;42^{13}\bmod 125$ ($3$ squarings, $2$ multiplications).
</s>