Let be a prime such that .
I want to understand how 2 is a square in .
I have already found this link to the proof: -1 and 2 as Quadratic Residues. But I'm having trouble understanding it.
I kinda need this for graph theory actually. I'm studying Paley graphs.
Thanks in advance!
The web page in your link, and the one it links to, are difficult for me to read. This is what I think they're trying to say:
Let's use p = 17 as was suggested by tonio. Then s = 8. The equations that we want to consider are
1 = (-1)(-1)^1
2 = (2)(-1)^2
3 = (-3)(-1)^3
4 = (4)(-1)^4
5 = (-5)(-1)^5
6 = (6)(-1)^6
7 = (-7)(-1)^7
8 = (8)(-1)^8
Now we multiply all eight equations together, yielding
8! = (-1)(2)(-3)(4)(-5)(6)(-7)(8)(-1)^(1+2+3+4+5+6+7+8)
or, since the last factor on the RHS of the equation equals +1,
8! = (-1)(2)(-3)(4)(-5)(6)(-7)(8)
Here's where it get confusing. It seems to me that the author wants to convert this last equation into a congruence mod p (or mod 17, in our example). So now we have
8! == (-1)(2)(-3)(4)(-5)(6)(-7)(8) (mod 17)
When the author says "Once we pass s, the right side still has the even numbers, but they are disguised as negative numbers.", I think he/she means to replace the negative factors -1, -3, -5 and -7 in this congruence with 17-1=16, 17-3=14, 17-5=12 and 17-7=10. So now we have
8! == (16)(2)(14)(4)(12)(6)(10)(8) (mod 17)
Each factor on the RHS of the congruence has a factor of 2, so we get a factor of 2^8. The remaining cofactors are just 1, 2, ..., 8, so we get
8! == (2^8)8! (mod 17)
or, dividing by 8!,
2^8 == 1 (mod 17)
On this page, the author states that "Therefore [a\p] is the same as a^(p-1)/2." Evidently, the author means
[a\p] == a^(p-1)/2 (mod p)
which is usually known as Euler's Criterion. Putting this together, we get
[2\17] == 2^8 == 1 (mod p)
which implies that [2\17] = 1, or 2 is a quadratic residue mod 17.
Perhaps you'd now like to modify this argument to apply to any odd prime p.
I'm trying to do the same for any prime .
In my analysis of the situation, multiplying equations 1 to s we'll have:
.
In the link (that contains the proof), the author said "Finally, the right side includes (-1)1+2+…+s. The exponent simplifies to s×(s+1)/2. This is even when s is 3 or 4 mod 4, which means 2 is a quadratic residue iff p = 1 or 7 mod 8. 2 is the square of 6 mod 17, but it isn't the square of anything mod 13."
It's not very clear how the author came to conclude that is even when s is 3 or 4 mod 4.
Could you shed a little light on that? Thanks.