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

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

-
There are two problems with your post. First $(a^b)^c = a^{b \cdot c}$ rather than $a^{b^c}$, so that $(12^{12})^{12} = 12^{12 \cdot 12}$ rather than $12^{12^{12}}$. Secondly, $x \equiv y \pmod{n}$ does not imply that $a^x \equiv a^y \pmod{n}$, even when $\gcd(a,n) = 1$. For example, $2 \equiv 6 \pmod{4}$, but $3^2 \not\equiv 3^6 \pmod{4}$. The trouble is that the multiplicative subgroup of $\mathbb{Z}/n \mathbb{Z}$ is of order $\varphi(n)$, rather than of order $n$. Both of these lead to the incorrect conclusion that $12^{12^{12^{12}}} \equiv 96 \pmod{100}$. – JavaMan Mar 6 '12 at 4:34