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.
elementary-number-theory
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.
Best Answer
(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}. $$