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$
8
  • 1
    $\begingroup$ Can you simplify $1^{29}$? $\endgroup$ Jun 9, 2017 at 5:58
  • $\begingroup$ @A.Pilk I got 185 $\endgroup$ Jun 9, 2017 at 6:08
  • $\begingroup$ How? I'm not sure what to do with 7777^4 $\endgroup$
    – A.Pilk
    Jun 9, 2017 at 6:09
  • $\begingroup$ @A.Pilk It should by $7777^{45}$. We have $7777\equiv-54(\mod191)$ and $54^{45}\equiv6(\mod191)$ $\endgroup$ Jun 9, 2017 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, 2017 at 6:28

2 Answers 2

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

$\endgroup$
2
  • $\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$ Jun 9, 2017 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$ Jun 9, 2017 at 8:24
2
$\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?

$\endgroup$

You must log in to answer this question.

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