Find last 3 digits of $ 2032^{2031^{2030^{\dots^{2^{1}}}}}$ Find the last 3 digits of this number
$$
2032^{2031^{2030^{\dots^{2^{1}}}}}
$$
So obviously we are looking for $x$ so that
$$
2032^{2031^{2030^{\dots^{2^{1}}}}} \equiv x \quad \text{mod}\hspace{0.1cm} 1000
$$ 
I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $\varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?
 A: It's a lot simpler than it looks.  I shall call the number $N$.
You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.
$N$ is obviously a multiple of $8$, thus $N\equiv 0\bmod 8$.  Which leaves $\bmod 125$.
The base $2032\equiv 32$.  When this is raised to a power, the residue of this power depends only on the residue of the exponent $\bmod 100$ where $100$ is the Euler totient of $125$.  But the exponent on $2032$ has the form
$2031^{10k}=(2030+1)^{10k}=(\text{binomial expansion})=100m+1$
So $N\equiv 32^1\equiv 32\bmod 125$.  The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $N\equiv 32\bmod 1000$.  Meaning the last three digits were there all along, the $\color{blue}{032}$ in the base $2032$!
A: Don't be scared.  If it turns into a monster and eats you, run away after you throw stones at it.  Don't run away before throwing stones just because it looks like a monster.
$2032^{monster}$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.
$2032^{monster} = 0 \pmod 8$ and so we just need to solve $2032^{monster} \pmod {125}$ and for that we can use Euler Theorem.  
$\phi(125=5^3) = (5-1)*5^{3-1} = 100$.  
So $2032^{monster} \equiv 32^{monster \% 100}$.
And $monster = 2031^{littlemonster}\equiv 31^{littlemonster}\pmod {100}$
$31$ and $100$ are relatively prime and $\phi(100)= 40$ so
$31^{littlemonster} \equiv 31^{littlemonster \% 40} \pmod {100}$.
$littlemonster = 2030^{smallmonster}$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^{smallmonster}$ and $2^{smallmonster}|2030^{smallmonster}$.
So $littlemonster \equiv 0 \pmod {40}$.
$2031^{littlemonster} \equiv 31^0 \equiv 1 \pmod {100}$
So $2032^{monster} \equiv 32 \pmod {125}$
So $2032^{monster} \equiv 0 \pmod 8$ and $2032^{monster} \equiv 32 \pmod {125}$.
As $8|32$ we are done.  $2032^{monster} \equiv 32 \pmod {1000}$.
and the last three digits are $032$.
A: By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$\mod 8$ and$\mod 125$. Obviously
$$z_0:=2032^{2031^{2030^{\dots^{2^{1}}}}} \equiv 0 \pmod 8$$
What remains to be found is $x_0 \in [0,124]$ in
$$z_0 \equiv x_0 \pmod {125}.$$
As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With
$$z_1:=2031^{2030^{\dots^{2^{1}}}}$$
and 
$$\phi(125)=100$$ the new problem becomes to find $x_1 \in [0,99]$ in
$$z_1 \equiv x_1 \pmod {100}$$
and then use
$$32^{x_1} \equiv x_0 \pmod {125}$$
to find $x_0$.
So this reduced the original problem$\mod 1000$ to a smaller problem$\mod 100$.
Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $\mod 2$). 
Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_{i-1}$, just as outlined for $x_1,x_0$ above.
