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

(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}. $$

Using $\, ab\bmod ac = a(b\bmod c) = $ mod Distributive Law twice, and Euler $\phi,\,$ we have

$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[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}}$

We used $\!\bmod 25\!:\ 12^{\color{#c00}K}\!\equiv 12^{K\bmod 20}$ by mod order reduction, by $12^{20}\equiv 1\,$ by Euler $\phi(25)\!=\!20$