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

share|improve this question

1 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.

share|improve this answer

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.