1
$\begingroup$

I need help with this problem please

Find the remainder when $7^{7^{7}}$ is divided by $1000$

My try follow

$1000=8×125$ , now

$7 \equiv -1 \;\bmod\; (8)$ $\to$ $7^{7^{7}} \equiv -1 \;\bmod\; (8)$ and

$7^{100}\equiv 1 \;\bmod\; (125)$

Any help to complete this solution?

$\endgroup$
1

3 Answers 3

3
$\begingroup$

Since $7^4=2\,401\equiv1\pmod{400}$ and since $7^3=343$, $7^7\equiv343\pmod{400}$. So, by Fermat-Euler, $7^{7^7}\equiv7^{343}\pmod{1\,000}$.

Since $7^4\equiv401\pmod{1\,000}$, $7^{20}=(7^4)^5\equiv1\pmod{1\,000}$. Therefore$$7^{343}=7^{340+3}\equiv7^3=343\pmod{1\,000}.$$

$\endgroup$
6
  • $\begingroup$ How are you able to switch from mod 400 to mod 1000. What makes this possible? $\endgroup$
    – kiwani
    Commented Apr 11, 2021 at 19:50
  • $\begingroup$ I used the fact that $\varphi(1000)=400$. It follows from this and from the Fermat-Euler theorem that, if $b\equiv c\pmod{400}$, and if $a$ and $1000$ are coprime, then $a^b\equiv a^c\pmod{1000}$. $\endgroup$ Commented Apr 11, 2021 at 20:07
  • $\begingroup$ oh, thank you. I have never heard of Fermat-Euler theorem. Do you know where I can learn more about it (link)? And what is the symbol phi? $\endgroup$
    – kiwani
    Commented Apr 11, 2021 at 20:08
  • 1
    $\begingroup$ I've added a link to my previous comment. $\endgroup$ Commented Apr 11, 2021 at 20:09
  • $\begingroup$ This question appears on Purplecomet 2017 middle school division Problem 15 (purplecomet.org/contestApi/downloadpracticecontests/…) . Is it expected that a middle schooler competing for this contest will know this way of doing the problem? How could a middle school student do this problem with the tools they have? $\endgroup$
    – kiwani
    Commented Apr 11, 2021 at 21:47
1
$\begingroup$

$(7^{100} \mod 125)= 1$ so $7^{7^7} = 7^{(7^7 \bmod 100)} \mod 125 = 7^{43} \mod 125 = 93$

Now you can use Chinese remainder theorem with $x = 93 \pmod {125}$ and $x = -1 \pmod 8$, fastest way by hand is to check the $8$ values of $125 + 93k$ in the range of $0$ to $1000$ to see which one is $-1$ of $\pmod 8$.


Alternatively

$$\begin{align} % 7 \text{^} (7 \text{^} 7) \mod 1000 & = % 7 \text{^} (7 \text{^} 7 \mod \Phi 1000) \mod 1000 \\ % &= 7 \text{^} (7 \text{^} 7 \mod 400) \mod 1000 \\ % &= 7 \text{^} 343 \mod 1000 \\ % &= 343 \\ % \end{align}$$

Just calculating $7 \text{^} 823543 \pmod {1000}$ is trivial with modular exponentiation as well.

$\endgroup$
2
  • $\begingroup$ thank you for your help, can you elaborate this step please $7^{43} \mod 125 = 93$ $\endgroup$
    – user373141
    Commented Jul 10, 2017 at 10:34
  • $\begingroup$ Just modular exponentiation. Eventually you do have to do some arithmetic. I suspect there is some trick to this problem in $7^{7^3} \equiv 7^3 \pmod {1000}$ that creates a shortcut. Dunno off the top of my head though. The numbers are so small that any tricks are really a waste of time. $\endgroup$
    – DanielV
    Commented Jul 10, 2017 at 10:40
1
$\begingroup$

As $7^4=2400+1$ and $7\equiv-1\pmod4\implies 7^7\equiv-1\equiv3\pmod4$

We can write $7^7=4m+3$ where integer $m\ge0$

$$7^{4m+3}=7^3(1+2400)^m$$

Now $(1+2400)^m\equiv1+\binom m12400\pmod{1000}$

$7^8=(1+2400)^2\equiv1\pmod{40}\implies7^7\equiv7^{-1}\equiv23$

We can choose $7^7=40n+23=4(10n+5)+3$

$\implies m\equiv5\pmod{10}, m=10r+5$(say)

$1+2400m\equiv1+2400(10r+5)\equiv1\pmod{1000}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .