Final numbers of $2003^{2003}$ and $2003^{2003^{2003}}$ What are the three final numbers of $2003^{2003}$ and $2003^{2003^{2003}}$? 
Do I use the Chinese Remainder Theorem here, and if so, how?
 A: To find the last three digits means to find the residue class $\pmod{1000}$.
Since $\varphi(1000)=400$, by Euler's theorem we have:
$$ 2003^{2003}\equiv 3^{3}\equiv 27\pmod{1000},$$
so the last three digits of $2003^{2003}$ are $\color{red}{027}$.
To do the same with $2003^{2003^{2003}}$, we have to understand what $2003^{2003}\pmod{400}$ is. Since:
$$ 2003^{2003}\equiv 3^{83}\equiv 27\pmod{400}, $$
because $3^{83}\equiv 3^3\equiv 2\pmod{25}$ and $3^{83}\equiv 11\pmod{16}$, we have:
$$ 2003^{2003^{2003}}\equiv 3^{27}\equiv 987\pmod{1000}$$
and the last three digits of $2003^{2003^{2003}}$ are $\color{red}{987}$.
A: Euler's theorem guarantees that, if $\gcd(a,1000)=1$ then
$$a^{400}\equiv 1\pmod {1000}$$
that is, the three last digits of $a^{400}$ will be $001$.
Then, since $2003\equiv 3\pmod {1000}$ and $2003\equiv 3\pmod{400}$, then
$$2003^{2003}\equiv 3^3\equiv 27\pmod {1000}$$
that is, the three last digits of $2003^{2003}$ are $027$.
Can you try the second one?
A: $\varphi(1000)=\left(2^3-2^2\right)\left(5^3-5^2\right)=400$, so by Euler's theorem (since $(3,1000)=1$):
$$2003^{2003}\equiv 3^{2003\pmod{\! 400}}\equiv 3^3\equiv 27\pmod{\! 1000}$$
You can shorten Jack's answer using Carmichael function (since $(3,400)=1$):
$$\lambda(400)=\lambda(2^4\cdot 5^2)=\text{lcm}\left(\lambda\left(2^4\right),\lambda(5^2)\right)=\text{lcm}\left(4,20\right)=20$$
$$2003^{2003^{2003}}\equiv 3^{3^{2003\pmod{\! 20}}\pmod{\! 400}}\equiv 3^{3^{3}}\equiv 987\pmod{\! 1000}$$
