EulerFermatTheorem Difficult

Problem - 4162

Compute $\underbrace{3^{3^{3^{\cdots^{3}}}}}_{2012\ times}\pmod{100}$.


Answer     87

By Euler's theorem, we have $3^{40}\equiv 1\pmod{100}$ because $\varphi(100)=40$. Let's compute $\underbrace{3^{3^{3^{\cdots^{3}}}}}_{2011\ times}\pmod{40}$. Recursively, we need to compute $\underbrace{3^{3^{3^{\cdots^{3}}}}}_{2010\ times}\pmod{16}$, $\underbrace{3^{3^{3^{\cdots^{3}}}}}_{2009\ times}\pmod{8}$, $\underbrace{3^{3^{3^{\cdots^{3}}}}}_{2008\ times}\pmod{4}$, and $\underbrace{3^{3^{3^{\cdots^{3}}}}}_{2007\ times}\pmod{2}$. The last expression obviously equals $1$. Therefore,

$$\begin{array}{rll} &\underbrace{3^{3^{3^{\cdots^{3}}}}}_{2008\ times}\equiv 3 & \pmod{4} \\ \implies & \underbrace{3^{3^{3^{\cdots^{3}}}}}_{2009\ times}\equiv 3^3 \equiv 3 & \pmod{8} \\ \implies & \underbrace{3^{3^{3^{\cdots^{3}}}}}_{2010\ times}\equiv 3^3 \equiv 11 & \pmod{16} \\ \implies & \underbrace{3^{3^{3^{\cdots^{3}}}}}_{2011\ times}\equiv 3^{11}\equiv \left(3^4\right)^2\times 3^3 \equiv 27  &\pmod{40} \\ \implies & \underbrace{3^{3^{3^{\cdots^{3}}}}}_{2012\ times} \equiv 3^{27} \equiv \boxed{87} &\pmod{100} \end{array}$$

The last step can utilize "the quick way to find the tens digit" technique to complete.

report an error