"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!
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,
<=> = 16k +1
<=> ≡ 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!
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?
Thanks for answering!