# Thread: When is 2 a quadratic residue?

1. ## When is 2 a quadratic residue?

Let $p$ be a prime such that $p \equiv 1\bmod 4$.
I want to understand how 2 is a square in ${\mathbb{Z}_p}$.

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.

2. Originally Posted by guildmage
Let $p$ be a prime such that $p \equiv 1\bmod 4$.
I want to understand how 2 is a square in ${\mathbb{Z}_p}$.

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.

What is it EXACTLY that you don't understand? I think it is pretty clear...

Tonio

3. I hope you don't mind me going through it piece by piece.

What does the author mean when he/she said that "Once we pass $s$, the right side still has the even numbers,..."

It is also not clear to me how the right side of the equation come to contain $\left( {s!} \right)\left( {{2^s}} \right)$.

4. Originally Posted by guildmage
I hope you don't mind me going through it piece by piece.

What does the author mean when he/she said that "Once we pass $s$, the right side still has the even numbers,..."

It is also not clear to me how the right side of the equation come to contain $\left( {s!} \right)\left( {{2^s}} \right)$.
Do an example, say with $p=17\Longrightarrow s:=\frac{p-1}{2}=8$ . Once we pass s means here "once we pass 8", so we'd get:

$9\times (-1)^9=-9=8\!\!\pmod{17}\,,\,\,10\times (-1)^{10}=10\,,\,\,11\times (-1)^{11}=-11=6\!\!\pmod{17}$ , and etc.

So we get even numbers in "disguise" of negative ones...

Tonio

5. Originally Posted by guildmage
I hope you don't mind me going through it piece by piece.

What does the author mean when he/she said that "Once we pass $s$, the right side still has the even numbers,..."

It is also not clear to me how the right side of the equation come to contain $\left( {s!} \right)\left( {{2^s}} \right)$.
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.

6. I'm trying to do the same for any prime $p \equiv 1 \bmod 4$.

In my analysis of the situation, multiplying equations 1 to s we'll have:

$s! = (-1)(2)(-3)...(s)(-1)^{1+2+3+...+s}$.

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 $\frac{s(s+1)}{2}$ is even when s is 3 or 4 mod 4.

Could you shed a little light on that? Thanks.

7. Originally Posted by guildmage
I'm trying to do the same for any prime $p \equiv 1 \bmod 4$.

In my analysis of the situation, multiplying equations 1 to s we'll have:

$s! = (-1)(2)(-3)...(s)(-1)^{1+2+3+...+s}$.

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 $\frac{s(s+1)}{2}$ is even when s is 3 or 4 mod 4.

Could you shed a little light on that? Thanks.

If $s=4=0\!\!\pmod 4$ then it is obvious that $\displaystyle{\frac{s(s+1)}{2}}$ is even, and if

$s=3k+4=3\!\!\pmod 4$ , then $s+1=0\!\!\pmod 4$ and we're back in the first case above.

Tonio

8. Ah... I see. The proof on the link is making much more sense now. Thanks to your replies.

9. Originally Posted by guildmage
Let $p$ be a prime such that $p \equiv 1\bmod 4$.
I want to understand how 2 is a square in ${\mathbb{Z}_p}$.

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.