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? 
 A: The prior $2$ answers omit hard calculations (too difficult mentally). Below is an easy way to do it purely mentally. Nothing is omitted. We use only $\rm B :=$ Binomial theorem and modular arithmetic.
$\!\!\bmod 200\!:\ \ \ \color{#c00}{3^{\large 20}}\equiv\, 1\,\ $ by $\,\ 9^{\large 10}\equiv\, (-1 + 10)^{\large 10}\overset{\rm B}\equiv  1 - {10}\cdot 10 + 5\cdot 9\cdot 10^{\large 2} \equiv 4401\equiv 1,\,$  so
$\!\! \bmod 1000\!:\ 3^{\large 100}\!\equiv 1\, $ by $\, ( \color{#c00}{3^{\large 20}})^{\large 5}\equiv (1\!+\!200k)^{\large 5}\overset{\rm B}\equiv 1 + 5\cdot 200k\equiv 1,\,$ therefore
$ 3^{\large 3^{\large 3^{\Large 3}}}\!\!\!\equiv 3^{\large \color{#0a0}{3^{\large 3^{\Large 3}}}\!\bmod{{100}}}\!\equiv 3^{\large\color{#0a0}{87}}\!\equiv 3(\color{#e94}{3^{\large 86}})\equiv  3(129)\equiv 387\ $ by  below: 
$\ \ \ \bmod 100\!:\ \ \smash[t]{\color{#0a0}{3^{\large 3^{\LARGE 3}}}}\!\equiv\, \color{#0a0}{87}\,$ by $\, \color{#c00}{3^{\large 27}}\!\equiv 3^{\large 7}\!\equiv 3^{\large 3} 3^{\large 4}\equiv 27(1\!-\!20)\equiv 27\!-\!40,\ $ and
$\ \bmod 1000\!:\ \color{#e94}{3^{\large 86}}\!\equiv 129\,$ by $\, 9^{\large 43}\!\equiv (-1\!+\!10)^{\large 43}\overset{\rm B}\equiv -1\! +\! 43(10)\!-\!\underbrace{43(21)}_{\large \color{#d4f}3+10j}10^{\large 2}\!\equiv -1\!+\!430\!-\! \color{#d4f}300$
A: 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).
