# When is 2 a quadratic residue?

Printable View

• Feb 6th 2011, 06:55 AM
guildmage
When is 2 a quadratic residue?
Let $\displaystyle p$ be a prime such that $\displaystyle p \equiv 1\bmod 4$.
I want to understand how 2 is a square in $\displaystyle {\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.

Thanks in advance!
• Feb 6th 2011, 07:09 AM
tonio
Quote:

Originally Posted by guildmage
Let $\displaystyle p$ be a prime such that $\displaystyle p \equiv 1\bmod 4$.
I want to understand how 2 is a square in $\displaystyle {\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.

Thanks in advance!

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

Tonio
• Feb 6th 2011, 07:22 AM
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 $\displaystyle 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 $\displaystyle \left( {s!} \right)\left( {{2^s}} \right)$.
• Feb 6th 2011, 08:38 AM
tonio
Quote:

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 $\displaystyle 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 $\displaystyle \left( {s!} \right)\left( {{2^s}} \right)$.

Do an example, say with $\displaystyle p=17\Longrightarrow s:=\frac{p-1}{2}=8$ . Once we pass s means here "once we pass 8", so we'd get:

$\displaystyle 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
• Feb 6th 2011, 01:09 PM
Petek
Quote:

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 $\displaystyle 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 $\displaystyle \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.
• Feb 6th 2011, 07:13 PM
guildmage
I'm trying to do the same for any prime $\displaystyle p \equiv 1 \bmod 4$.

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

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

Could you shed a little light on that? Thanks.
• Feb 7th 2011, 02:07 AM
tonio
Quote:

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

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

$\displaystyle 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 $\displaystyle \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 $\displaystyle s=4=0\!\!\pmod 4$ then it is obvious that $\displaystyle \displaystyle{\frac{s(s+1)}{2}}$ is even, and if

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

Tonio
• Feb 8th 2011, 04:56 PM
guildmage
Ah... I see. The proof on the link is making much more sense now. Thanks to your replies.
• Feb 8th 2011, 05:49 PM
Chris11
Quote:

Originally Posted by guildmage
Let $\displaystyle p$ be a prime such that $\displaystyle p \equiv 1\bmod 4$.
I want to understand how 2 is a square in $\displaystyle {\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.

Thanks in advance!

Check out the law of quadratic reciprocity.