Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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
and therefore $$ 7777^{45} \equiv 137\times 51 \times 118\times 172\times 59 \equiv 76 \pmod{191} $$
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?
