Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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