<s>[INST] Calculating the residue of power towers 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}$$
 [/INST] 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.
</s>