I want to calculate the residue of a power tower. How do I do that?

For example, I want to know the answer to this:

$$2 \uparrow\uparrow 10 \pmod{10^9}$$


When dealing with power towers with bases not relatively prime to the modulus, it's useful to employ the Chinese Remainder Theorem. And then repeatedly apply the Euler's Theorem.

$2 \uparrow \uparrow 10 \pmod {2^9} = 0$, so we only need to calculate $2 \uparrow \uparrow 10 \pmod{5^9}$.

By Euler's Theorem, we need to first study $2 \uparrow \uparrow 9 \pmod{\phi (5^9)} = 2 \uparrow \uparrow 9 \pmod{4 \cdot 5^8}$. So, as $2 \uparrow \uparrow 9 \equiv 0 \pmod{4}$, so by Chinese Remainder Theorem, we only need to settle the case when $2 \uparrow \uparrow 9 \pmod {5^8}$

Similarly proceeding at every step, we go a few more levels deeper, to get that we need to settle the congruence $2 \uparrow \uparrow 4 \pmod{4 \cdot 5^3}$. As $2 \uparrow \uparrow 4 = 2^{16} = 256^2 \equiv 6^2 \equiv 36 \pmod{125}$, so we get that $2 \uparrow \uparrow 4 \equiv 36 \pmod{4 \cdot 5^3}$, as $4| 36$.

Now, we unwrap the calculations. $2 \uparrow \uparrow 5 = 36^2 \equiv 1296 \pmod{5^4}$, hence $2 \uparrow \uparrow 5 \equiv 1296 \pmod{4 \cdot 5^4}$ as $4|1296$.

At this stage the calculations become too tedious to perform, but I hope you get the idea.


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.