How do I solve $5^{288} \bmod 577$?

Question

I worked here down from $$125^{288} \bmod 577$$ but I don’t know how to proceed. I only know Fermat's Little Theorem and Euler’s formula and unfortunately I don’t see a way to use them. The result is $-1=576$.

Thanks for any help! :)

Edit: Solving $$5^{288} \bmod 577$$ Solved, thanks everyone:)!

Answer 1

This is actually the Legendre symbole and you can use the quadratic reciprocity: $$5^{288}=5^{\frac{577-1}{2}}=\left( \frac{5}{577}\right)$$

and by the quadratic reciprocity: $$\left( \frac{577}{5}\right) \left( \frac{5}{577}\right)=(-1)^{\frac{(577-1)(5-1)}{2 \cdot 2}}=(-1)^{576}=1$$

So it is sufficient to compute:

$$\left( \frac{577}{5}\right)= 577^\frac{5-1}{2}=577^2 \bmod 5$$ But: $$577=2 \bmod 5$$ so: $$577^2=2^2=4=-1 \bmod 5$$ thus: $$\left( \frac{5}{577}\right) \cdot (-1)=1$$ i.e: $$\left( \frac{5}{577}\right)=-1$$

Answer 2

• HINT: $ 5^{288} \equiv x \mod 577 \Rightarrow x^2 \equiv 1 \mod 577$ And then try to understand why one answer does not fit

Answer 3

Hint: $25^{288} \equiv 1 \pmod{577}$, and $(-1)^2=1$.