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$
5
  • 1
    $\begingroup$ Probably obvious, but you mean $7^{(7^7)}$ etc., right, not $(7^7)^7$? $\endgroup$ Jun 27 '13 at 8:35
  • $\begingroup$ @AndreasCaranti Yep $\endgroup$
    – dpington
    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$ 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$
2
  • $\begingroup$ why did you switch to mod 4? You were calculating in mod 100 and then you switch to mod 4. How come you can do that? $\endgroup$
    – kiwani
    Apr 11 at 19:28
  • $\begingroup$ @kiwani We want to find $7^a \pmod{100}$. In the first equation I showed that $7^4\equiv 1\pmod{100}$. It means that the powers of 7 mod 100 follows a cycle of length 4 (the cycle is 7, 49, 43, 1). So in order to find the solution, it suffices to find at which element in this cycle we will end up. Cycle is of length 4, so I evaluate the exponent of the original statement mod 4. BTW that's why original statement has 7 sevens, and the $\pmod4$ statement has only 6. $\endgroup$
    – Adam
    Apr 11 at 22:02
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$
1
  • $\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$ 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$
1

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.