$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.
 A: 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}
$$
A: 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?
