# $7777^{5555}$ divided by $191$. Find the remainder.

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.

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

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

• 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$. – DanielWainfleet Jun 9 '17 at 8:02
• 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 – lab bhattacharjee Jun 9 '17 at 8:24

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?