7
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.