# Find the last two digits of $12^{12^{12^{12}}}$ using Euler's theorem

I am supposed to find the last two digits of $$12^{12^{12^{12}}}$$ using Euler's theorem.
I've figured out that it would go as $$12^{12^{12^{12}}} \mod{100}$$.

But I really don't know how to progress from there. Any hints would be greatly appreciated.

(Thanks to anon for pointing out an error in an earlier post).

Hint: To solve $x \equiv 12^{12^{12^{12}}} \pmod{100}$, we should solve the equations $$x \equiv 12^{12^{12^{12}}} \pmod{4} \tag{1}$$ $$x \equiv 12^{12^{12^{12}}} \pmod{25},\tag{2}$$ and then apply the Chinese Remainder Theorem.

Solving equation (1) is easy. $12 \equiv 0 \pmod{4} \implies 12^k \equiv 0 \pmod{4}$ for all integers $k$. Equation (2) can be solved using Euler's Theorem:

$$x \equiv y \pmod{\varphi(n)} \implies a^x \equiv a^y \pmod{n},$$

so long as $\gcd(a,n) = 1$. Stitch all these things together to find your solution.

Alternative (and potentially better) Hint:

Note that $12^{12^{12^{12}}} = 3^{{12^{12^{12}}}} \cdot 4^{{12^{12^{12}}}}$. Therefore:

$$12^{12^{12^{12}}} \pmod{100} = 3^{{12^{12^{12}}}} \cdot 4^{12^{12^{12}}} \pmod{100}.$$

$$12^{\large 12^{\Large 4N}}\!\!\!\bmod 100 = 4\left[\dfrac{12^{\large\color{#c00} {12^{\Large 4N}}}}4\!\!\bmod 25\right]= 4\left[\dfrac{\color{#0a0}{12}^{\large\color{#c00}{16}}}4\!\!\bmod 25\right] =\,4\left[\dfrac{\color{#f76}{2^{\large 4}}}4\right] = 16,\,$$ by

$$\ \ \ \ \color{#c00}{12^{\large 4N}}\!\!\bmod\!\!\!\overbrace{20}^{\large \phi(25)}\!\!\! = 4\left[\dfrac{12^{\large 4N}}4\!\!\bmod 5\right] = 4=\color{#c00}{16},\$$ by $$\,\dfrac{2^{\large 4\:\!N}}4\equiv \dfrac{1^{\large N}}{-1}\equiv 4\pmod{\!5}$$

$$\ \ \ \ \ \ \ \ \ \ \ \ \bmod 25\!:\,\ \underbrace{2^{\large 20}\!\equiv 1_{\!\!\!\!\!\!\phantom{1}}}_{\large \rm Euler\ \phi}\,\$$ & $$\,\ 12\equiv \dfrac{-1}2\,\Rightarrow\, \color{#0a0}{12}^{\large\color{#c00}{ 16}}\equiv \dfrac{1}{2^{\large 16}}\equiv \dfrac{2^{\large 20}}{2^{\large 16}}\equiv \color{#f76}{2^{\large 4}}$$