To calculate modulo of power towers

Question

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

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

$ 2 \uparrow\uparrow 10 \mod 10^9 $

Answer 1

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.