11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Probably obvious, but you mean $7^{(7^7)}$ etc., right, not $(7^7)^7$? $\endgroup$ – Andreas Caranti Jun 27 '13 at 8:35
  • $\begingroup$ @AndreasCaranti Yep $\endgroup$ – Herp Derpington Jun 27 '13 at 8:36
  • $\begingroup$ wolframalpha.com/input/… $\endgroup$ – vonjd Jun 27 '13 at 8:46
  • $\begingroup$ @ZevChonoles I purposely did not TeXify the title, because it takes a lot of space on the main page that way. $\endgroup$ – Lord_Farin Jun 27 '13 at 8:57
  • $\begingroup$ @Lord_Farin: I realize that, but I think there are occasions when it is better to have a properly formatted title, even if it does take up more space. Of course it's not that important, I won't argue this case. $\endgroup$ – Zev Chonoles Jun 27 '13 at 9:02
18
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ An easy way to see that $7^4=49^2\equiv1\pmod{100}$ is to note that $49=50-1$ and thus $49^2=50^2-2\cdot50+1\equiv0-0+1=1\pmod{100}$. The same trick also helps with $7^3=49\cdot7=(50-1)7=50\cdot7-7\equiv50-7=43\pmod{100}$. $\endgroup$ – Ilmari Karonen Jun 27 '13 at 9:31
9
$\begingroup$

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

$\endgroup$

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.