Mock AIME 4 2006-2007 Problems/Problem 7

Problem

Find the remainder when $3^{3^{3^3}}$ is divided by 1000.

Euler's Totient Theorem comes in handy here:

$3^{400}\equiv 1 \pmod {1000}$

So we are looking for $3^{27} \pmod {400}$

$3^{27}=(3^9)^3=(27^3)^3$

We brute force it:

$27^3=729*27=19683$

$19683 \equiv 83 \pmod {400}$

$83^2=6889$

$83^3 \equiv 187 \pmod {400}$

$3^{27} \equiv 187 \pmod {400}$

$3^{3^{3^3}} \equiv 3^{187} \pmod {1000}$

This problem needs a solution. If you have a solution for it, please help us out by adding it.