"Let p be an odd prime, then we proved that the Legendre symbol
Note that this can be easily computed if p is reduced modulo 8.
For example, if p=59, then p≡3 (mod 8) and = ." (quote from my textbook)
Now I don't exactly see WHY p can be reduced modulo 8 without changing the answer.
Why can we be so sure that and will have the same parity? How can we prove this?
Thanks for explaining!