"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 $\displaystyle (-1)^{(p^2-1)/8}$ = $\displaystyle (-1)^{(3^2-1)/8}$." (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 $\displaystyle (59^2-1)/8$ and $\displaystyle (3^2-1)/8$ will have the same parity? How can we prove this?

Thanks for explaining!