3
$\begingroup$

I've seen tons of examples of Fermat's little theorem and solved some it for smaller numbers, but I fail with this.

By Fermat's little theorem $7777^{190} \equiv 1\pmod{191}$

Then $7777^{5555} = 7777^{(190 \cdot 29)} \cdot 7777^{45} \equiv 1^{29} \cdot 7777^4\pmod{191}$

But after that I'm stuck.

$\endgroup$
  • 1
    $\begingroup$ Can you simplify $1^{29}$? $\endgroup$ – Chris Culter Jun 9 '17 at 5:58
  • $\begingroup$ @A.Pilk I got 185 $\endgroup$ – Michael Rozenberg Jun 9 '17 at 6:08
  • $\begingroup$ How? I'm not sure what to do with 7777^4 $\endgroup$ – A.Pilk Jun 9 '17 at 6:09
  • $\begingroup$ @A.Pilk It should by $7777^{45}$. We have $7777\equiv-54(\mod191)$ and $54^{45}\equiv6(\mod191)$ $\endgroup$ – Michael Rozenberg Jun 9 '17 at 6:10
  • $\begingroup$ Isn't 7777 ≡ 137 (mod 191)? And how did you get this 54^45 ≡ 6(mod 191)? Could you please explain it "for dummies"? :) $\endgroup$ – A.Pilk Jun 9 '17 at 6:28
3
$\begingroup$

When calculating $7777^{5555} \pmod{191}$, we first note that $gcd(7777,191)=1$ and $\phi(191)=190$. We can indeed use Euler's theorem: $$ 7777^{190}\equiv 1 \pmod{191} $$ and therefore $$ 777^{5555} = 7777^{190 \times 29} 7777^{45} \equiv 1^{29} \times 7777^{45} \pmod{191} = 7777^{45} \pmod{191} $$ Now that the exponent is much smaller, we can use repeated squaring. First we note that $45= 1 + 4 + 8 + 32$, and

  • $7777\equiv 137 \pmod{191}$
  • $7777^{2}\equiv 137^2 \equiv 51 \pmod{191}$
  • $7777^{4} \equiv 137^4 \equiv 51^2 \equiv 118 \pmod{191}$
  • $7777^{8} \equiv 118^2 \equiv 172 \pmod{191}$
  • $7777^{32} \equiv 118^8 \equiv 59 \pmod{191} $

and therefore $$ 7777^{45} \equiv 137\times 51 \times 118\times 172\times 59 \equiv 76 \pmod{191} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We can also look for short-cuts, such as $137\equiv -54 ,$ and computing $(-54)^{10}\equiv 54^8\cdot 54^2\equiv (-19)51$ (and reduce), in order to compute $(-54)^{11}\equiv (-54)54^{10}$ in order to compute $(-54)^{44}\equiv ((-54)^{11})^4$. $\endgroup$ – DanielWainfleet Jun 9 '17 at 8:02
  • 1
    $\begingroup$ As $7777\equiv-54\pmod{191}$ $7777^{45}\equiv(-54)^{45}\pmod{191}\equiv-54^{45}$ As $54=2\cdot3^3,54^{45}=(2\cdot3^3)^{45}=2^{45}\cdot3^{135}$ Now for $2^{45}=2^{32+8+4+1}\equiv-31\pmod{191}$ and so on $\endgroup$ – lab bhattacharjee Jun 9 '17 at 8:24
1
$\begingroup$

As you have reached this point, I will focus on simplifying $7777^{45} \pmod{191}$. If you are doing this by hand, using repeated squaring may involve a lot of arithmetic, so one alternative starts with the fact that $7777 = 11 \cdot 707$. The strategy becomes to solve for $11^{45} \pmod{191}$ and $707^{45} \pmod{191}$. I chose to use these two factors because $$\begin{align*} 11^3 = 1331 = 1200 + 131 & = 6(191 + 9) + 131 \\ & \equiv 54 + 131 \\ & \equiv -6 \pmod{191} \end{align*}$$ Also, since $707 \equiv 134 \pmod{191}$, $707^2 \equiv 134^2 \equiv 2 \pmod{191}$. Hence, the problem now becomes $$7777^{45} = 11^{45}707^{45} \equiv (-6)^{15}(2)^{22} \cdot 707 \equiv - 3^{15}2^{37} \cdot 134 \pmod{191}$$ Note that $2^6 \cdot 3 = 192 \equiv 1 \pmod{191}$, so we can simplify further to $7777^{45} \equiv -3^9 \cdot 2 \cdot 134 \pmod{191}$. This looks much more doable by hand; can you take it from here?

| cite | improve this answer | |
$\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.