1. Legendre Symbol (2/p)

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

Thanks for explaining!

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

Thanks for explaining!
because if $p=8k + a,$ then $\frac{p^2-1}{8}=\frac{64k^2+16ka+a^2-1}{8}=2b + \frac{a^2-1}{8},$ where $b=8k^2+2ka.$ so $(-1)^{\frac{p^2-1}{8}}=(-1)^{2b} \times (-1)^{\frac{a^2-1}{8}}=(-1)^{\frac{a^2-1}{8}}.$

3. Thank you!

To get the conrguence on the right hand side (i.e. precisely when (-1/p)=1), I will use the formula in the middle
(-1/p)=1 <=> (p-1)/2 is even <=> (p-1)/2 = 2k <=> p=1+4k <=> p≡1 (mod 4)

Following the same trick as above, to determine when (2/p)=1,
set $[(p^2 -1)/8]$ =2k
<=> $p^2$ = 16k +1
<=> $p^2$ ≡ 1 (mod 16)

<=> p ≡ ??? (mod 8) <-----I'm stuck on this step. Can someone explain how to go from the previous step to this step?

Thanks for any help!

4. Originally Posted by kingwinner
Thank you!

To get the conrguence on the right hand side (i.e. precisely when (-1/p)=1), I will use the formula in the middle
(-1/p)=1 <=> (p-1)/2 is even <=> (p-1)/2 = 2k <=> p=1+4k <=> p≡1 (mod 4)

Following the same trick as above, to determine when (2/p)=1,
set $[(p^2 -1)/8]$ =2k
<=> $p^2$ = 16k +1
<=> $p^2$ ≡ 1 (mod 16)

=> p ≡ ??? (mod 8) <-----I'm stuck on this step. Can someone explain how to go from the previous step to this step?

Thanks for any help!
use what i already showed: if $p=8k + a,$ then $(-1)^{\frac{p^2-1}{8}}=(-1)^{\frac{a^2-1}{8}}.$ now if $p$ is an odd prime, then what are the possible values of $a$ modulo 8? only 1, 3, 5 and 7.

a simple calcultaion shows that $\frac{a^2-1}{8}$ is odd for a = 3, 5 and it's even for a = 1, 7 and you're done.

5. Originally Posted by NonCommAlg
use what i already showed: if $p=8k + a,$ then $(-1)^{\frac{p^2-1}{8}}=(-1)^{\frac{a^2-1}{8}}.$ now if $p$ is an odd prime, then what are the possible values of $a$ modulo 8? only 1, 3, 5 and 7.

a simple calcultaion shows that $\frac{a^2-1}{8}$ is odd for a = 3, 5 and it's even for a = 1, 7 and you're done.
If we somehow already HAVE the answer on the right hand side, then it's easy to check that $\frac{a^2-1}{8}$ is odd for a = 3, 5 and it's even for a = 1, 7. But to do this, we actually need to know the correct answers in the first place.

But like in my textbook, it only proved the formula in the middle, without showing the conditions on the right, and I'm looking for a way to systematically derive the conditions on the right using the formula in the middle.

Also, why should the conditions be p≡ (mod 8)? Why not p≡ (mod 16)?? (as analogy, for (-1/p), the formula has 2 in the denominator of the exponent, and we get mod 4 on the right)
Having ONLY the formula in the middle, how to figure out what modulus to work with when we're trying to derive the conditions on the right?

6. Originally Posted by kingwinner
If we somehow already HAVE the answer on the right hand side, then it's easy to check that $\frac{a^2-1}{8}$ is odd for a = 3, 5 and it's even for a = 1, 7.

But like in my textbook, it only proved the formula in the middle, without showing the conditions on the right, and I'm looking for a way to systematically derive the conditions on the right using the formula in the middle.

Also, why should the conditions be p≡ (mod 8)? Why not p≡ (mod 16)?? (as analogy, for (-1/p), the formula has 2 in the denominator of the exponent, and we get mod 4 on the right)
Having only the formula in the middle, how to figure out what modulus to work with when we're trying to derive the conditions on the right?

well, you can consider p modulo 16 and the result would be the same but your job would be harder! the point here is that when you look at p modulo 8, say $p \equiv a \mod 8,$ then

$p^2 \equiv a^2 \mod 16$: if $p = 8k + a$, then $p^2=64k^2 + 16ka + a^2=16(4k^2+ka)+a^2.$ so modulo 8 just makes things easier.