Lots of Twos

Let $N=2^{2^{2^{2^2}}}$ . We need to find $N \bmod 1000$ . Since $\gcd(2,1000) \ne 1$ , we can not use Euler's theorem and we consider the factors of 1000, $2^3=8$ and $5^3=125$ using the Chinese remainder theorem as follows:

Consider factor 8: $N \equiv 0 \text{ (mod 8)}$

Consider factor 125: Since $\gcd(2,125) = 1$ , we can apply Euler's theorem as follows:

$\begin{aligned} N & \equiv 2^{2^{2^{2^2}} \bmod \color{#3D99F6} \phi(125)} \text{ (mod 125)} & \small \color{#3D99F6} \text{where }\phi (\cdot) \text{ denotes the Euler's totient function.} \\ & \equiv 2^{2^{2^{2^2}} \bmod \color{#3D99F6} 100} \text{ (mod 125)} & \small \color{#3D99F6} \text{Note that }\phi (125) = 125\times \frac 45 = 100 \\ & \equiv 2^{2^{16} \bmod 100} \text{ (mod 125)} \\ & \equiv 2^{(250+6)^2 \bmod 100} \text{ (mod 125)} \\ & \equiv 2^{36} \text{ (mod 125)} \\ & \equiv (250+6)^4 \cdot 2^4 \text{ (mod 125)} \\ & \equiv 6^4 \cdot 2^4 \text{ (mod 125)} \\ & \equiv 3^4 \cdot (256) \text{ (mod 125)} \\ & \equiv 81 \cdot 6 \text{ (mod 125)} \\ & \equiv 111 \text{ (mod 125)} \end{aligned}$

$\begin{aligned} \implies N & \equiv 125n + 111 & \small \color{#3D99F6} \text{where } n \in \mathbb N \\ \implies 125n + 111 & \equiv 0 \text{ (mod 8)} \\ 5n + 7 & \equiv 0 \text{ (mod 8)} \\ \implies n & \equiv 5 \end{aligned}$

$\begin{aligned} \implies N & \equiv 125\cdot 5 + 111 \text{ (mod 1000)} \\ & \equiv \boxed{736} \text{ (mod 1000)} \end{aligned}$