"Let p be an odd prime, then we proved that the Legendre symbol

Note that this can be easily computedif 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!