Solving a congruence with high numbers and computing the Legendre symbol I am asked to compute $\left(\frac{77}{257}\right)$ specifically using Euler's criterion. I have manged to get the following: $$\left(\frac{77}{257}\right)\equiv77^{256/2} \bmod257$$ $$\equiv77^{128}\bmod257$$ I don't know where to go from here as I don't know the trick to simplify congruences that are big like this without typing it in on an online calculator. I believe it may be to do with pulling out factors to reduce the size of $77^{128}$ but am not sure. Can anyone help me?

$77^{128}\pmod{257}$ is simple to compute through repeat-squaring:

1. $77^{2}\equiv 18\pmod{257}$
2. $77^{2^2}\equiv 18^2 \equiv 67\pmod{257}$
3. $77^{2^3}\equiv 67^2\equiv 120\pmod{257}$
4. $77^{2^4}\equiv 120^2\equiv 8\pmod{257}$
5. $77^{2^5}\equiv 8^2 \equiv 64\pmod{257}$
6. $77^{2^6}\equiv 64^2\equiv 241\pmod{257}$
7. $77^{2^7}\equiv 241^2\equiv\color{red}{-1}\pmod{257}$



hence $77$ **is not** a quadratic residue $\\!\\!\pmod{257}$.

* * *

Quadratic reciprocity is way more efficient: $$\left(\frac{77}{257}\right)=\left(\frac{-180}{257}\right)=\left(\frac{5}{257}\right)=\left(\frac{2}{5}\right)=\color{red}{-1}.$$