Calculating 7^7^7^7^7^7^7 mod 100

What is

$$\large 7^{7^{7^{7^{7^{7^7}}}}} \pmod{100}$$

I'm not much of a number theorist and I saw this mentioned on the internet somewhere. Should be doable by hand.

Solution 1:

$7^4 = 2401 \equiv 1 \pmod{100}$, so you only need to calculate $7^{7^{7^{7^{7^7}}}} \pmod{4}$. We know that $7 \equiv -1 \pmod 4$ and $7^{7^{7^{7^7}}}$ is odd, so $7^{7^{7^{7^{7^7}}}} \equiv -1 \equiv 3 \pmod 4$, and then $$7^{7^{7^{7^{7^{7^7}}}}} \equiv 7^3 \equiv 43 \pmod {100}$$

Solution 2:

A quick hand calculation gives $$\begin{align} 7^1 &\equiv 7 \pmod{100} \\ 7^2 &\equiv 49 \pmod{100} \\ 7^3 &\equiv 43 \pmod{100} \\ 7^4 &\equiv 1 \pmod{100} \end{align}$$ So it reduces to the problem of calculating the value of $7^{7^{7^{7^{7^7}}}} \pmod 4$. And $7^2 \equiv 1 \pmod 4$, so it reduces to the problem of calculating $7^{7^{7^{7^7}}} \pmod 2$... and this is easy, it's odd, so it's congruent to $1$ modulo $2$.

Working backwards:

$$7^{7^{7^{7^{7^7}}}} \equiv 7^1 \equiv 3 \pmod{4}\quad \Rightarrow\quad 7^{7^{7^{7^{7^{7^7}}}}} \equiv 7^3 \equiv 43 \pmod{100}$$

Solution 3:

Reading the other answers, I realize this is a longer way than necessary, but it gives a more general approach for when things are not as convenient as $7^4\equiv 1\bmod 100$.

Note that, for any integer $a$ that is relatively prime to $100$, we have $$a^{40}\equiv 1\bmod 100$$ because $\varphi(100)=40$, and consequently $$a^m\equiv a^n\bmod 100$$ whenever $m\equiv n\bmod 40$. Thus, we need to find $7^{7^{7^{7^{7^{7}}}}}$ modulo $40$. By the Chinese remainder theorem, it is equivalent to know what it is modulo $8$ and modulo $5$.

Modulo $8$, we have $7\equiv -1\bmod 8$, and $-1$ to an odd power is going to be $-1$, so we see that $$7^{7^{7^{7^{7^{7}}}}}\equiv (-1)^{7^{7^{7^{7^{7}}}}} \equiv -1\equiv 7\bmod 8.$$ Modulo $5$, we have $7^4\equiv 1\bmod 5$ (again by Euler's theorem), so we need to know $7^{7^{7^{7^{7}}}}\bmod 4$. But $7\equiv -1\bmod 4$, and $7^{7^{7^{7}}}$ is odd, so that $7^{7^{7^{7^{7}}}}\equiv -1\equiv 3\bmod 4$, so that $$7^{7^{7^{7^{7^{7}}}}}\equiv 7^3\equiv 343\equiv 3\bmod 5.$$ Applying the Chinese remainder theorem, we conclude that $$7^{7^{7^{7^{7^{7}}}}}\equiv 23\bmod 40,$$ and hence $$7^{7^{7^{7^{7^{7^{7}}}}}}\equiv 7^{23}\bmod 100.$$ This is tractable by again using the Chinese remainder theorem to find $7^{23}\bmod 4$ and $7^{23}\bmod 25$.