I am suppossed 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.
I am suppossed 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=10+2 $$
$$ 12^{12}=(10+2)^{12}\equiv 10\cdot 12\cdot 2^{11}+2^{12}=120\cdot 2048+4096 \equiv 960+96\equiv 56 $$
Hence,
$$ 12^{12}\equiv 56 $$
Now, we look at $ 12^{{12}^{12}}\equiv 56^{12} $ ,
$56^{12}=(2^3\cdot 7)^12=(2^{6}\cdot7^{2})^6=(64\cdot 49)^6\equiv 36^6=6^4\cdot6^4\cdot6^4\equiv (-4)(-4)(96)=16\cdot 96\equiv 36$
Hence,
$$ 12^{{12}^{12}}\equiv 36 $$
Now, we look at $ 12^{{12}^{{12}^{12}}}\equiv 36^{12} $ ,
$36^{12}=(36^6)^2\equiv36^2\equiv 96$
And,
$$12^{{12}^{{12}^{12}}}\equiv 96\pmod {100} $$