Quadratic Residues & Legendre symbol

**kingwinner** · February 28th 2010, 02:07 PM

Let p be an odd prime. Prove that x^2 ≡ 2 (mod p) has solutions if and only if p ≡ 1 or 7 (mod 8).

The related materials in the section are quadratic residues, and the Legendre symbol, but I can't figure out how to prove this.

Any help is appreciated!

[also under discussion in math links forum]

**Bruno J.** · February 28th 2010, 03:42 PM

Use Gauss's lemma! It's a direct application.

**kingwinner** · February 28th 2010, 08:48 PM

How?
But we are asked to do a PROOF in this problem...!?

**hatsoff** · March 1st 2010, 05:16 AM

Originally Posted by kingwinner

Let p be an odd prime. Prove that x^2 ≡ 2 (mod p) has solutions if and only if p ≡ 1 or 7 (mod 8).

The related materials in the section are quadratic residues, and the Legendre symbol, but I can't figure out how to prove this.

Any help is appreciated!

[also under discussion in math links forum]

How?
But we are asked to do a PROOF in this problem...!?

Sounds like you're using the Niven textbook. I did this exercise last fall, and it gave be some trouble too. It is indeed proved by Gauss's lemma.

Just do a case-by-case proof that $x^2\equiv 2\pmod{p}$ has a solution given that $p\equiv 1$ , then $p\equiv 3$ , then $p\equiv 5$ , and finally $p\equiv 7\pmod{8}$ . Since those are the only possibilities (even numbers won't work), the conclusion will follow.

Consider Gauss's lemma, and let $a=2$ , and observe that each $i\in\{2,4,6,\cdots,p-1\}$ is its own least positive residue modulo $p$ . Let $n$ denote the number of integers in the set

$\left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}$ .

Then by Gauss's lemma, $\left(\frac{2}{p}\right)=(-1)^n$ .

Now comes the tricky part: Let $m$ denote the number of even positive integers less than $p/2$ . Then $n=[(p-1)/2]-m$ . But what is $m$ ? Well, $m=(p-1)/4$ iff $(p-1)/4$ is an integer; overwise $m=(p-3)/4$ .

This is the framework that we use for each case. Let's try one in particular...

Suppose $p\equiv 3\pmod{8}$ . Then $\frac{p-1}{4}$ is not an integer, which means $m=\frac{p-3}{4}$ , and therefore

$n=\frac{p-1}{4}-m=\frac{p-1}{2}-\frac{p-3}{4}=\frac{p+1}{4}$ .

Since $p\equiv 3\pmod{8}$ , if follows that $n=\frac{p+1}{4}$ is odd, which means

$\left(\frac{2}{p}\right)=(-1)^n=-1$ .

Therefore $x^2\equiv 2\pmod{p}$ has no solution whenever $p\equiv 3\pmod{8}$ , and we move on to the next case.

**kingwinner** · March 1st 2010, 10:44 AM

It's such a tricky question...

So you showed that p≡ 3(mod 8) => no solution

How can we prove that THERE IS a solution when e.g. p ≡ 7 (mod 8)? What do we have to show?

Also, in this question, we are asked to prove IF AND ONLY IF, right? So how can we prove the "converse" direction?

Thanks for helping!

**hatsoff** · March 1st 2010, 01:02 PM

Originally Posted by kingwinner

It's such a tricky question...

So you showed that p≡ 3(mod 8) => no solution

How can we prove that THERE IS a solution when e.g. p ≡ 7 (mod 8)? What do we have to show?

Also, in this question, we are asked to prove IF AND ONLY IF, right? So how can we prove the "converse" direction?

Thanks for helping!

It's the same method, only with a different conclusion.

Suppose $p\equiv 1\pmod{8}$ . Then $\frac{p-1}{4}$ is an integer, which means

$n=\frac{p-1}{4}-m=\frac{p-1}{2}-\frac{p-1}{4}=\frac{p-1}{4}$ .

And since $\frac{p-1}{4}$ is even then $\left(\frac{2}{p}\right)=(-1)^n=1$ .

So $x^2\equiv 2\pmod{p}$ has a solution.

**kingwinner** · March 1st 2010, 04:16 PM

Originally Posted by hatsoff

It's the same method, only with a different conclusion.

Suppose $p\equiv 1\pmod{8}$ . Then $\frac{p-1}{4}$ is an integer, which means

$n=\frac{p-1}{4}-m=\frac{p-1}{2}-\frac{p-1}{4}=\frac{p-1}{4}$ .

And since $\frac{p-1}{4}$ is even then $\left(\frac{2}{p}\right)=(-1)^n=1$ .

So $x^2\equiv 2\pmod{p}$ has a solution.

OK. But for "if and only if" statements, I think we have to prove BOTH directions, right?

So far we've only showed one direction.
How can we prove (conversely) that
x^2 ≡ 2 (mod p) has solutions => p ≡ 1 or 7 (mod 8) ?

thanks.

**hatsoff** · March 1st 2010, 06:18 PM

Originally Posted by kingwinner

OK. But for "if and only if" statements, I think we have to prove BOTH directions, right?

So far we've only showed one direction.
How can we prove (conversely) that
x^2 ≡ 2 (mod p) has solutions => p ≡ 1 or 7 (mod 8) ?

thanks.

If we prove there are no solutions for $p\equiv 3,5\pmod{8}$ , then it follows that there may only be solutions if $p\equiv 1,7\pmod{8}$ (because $p$ is odd).

**kingwinner** · March 1st 2010, 06:33 PM

Originally Posted by hatsoff

If we prove there are no solutions for $p\equiv 3,5\pmod{8}$ , then it follows that there may only be solutions if $p\equiv 1,7\pmod{8}$ (because $p$ is odd).

Oh, yes, that's proof by contrapositive.

Thank you!

**kingwinner** · March 3rd 2010, 01:15 AM

Originally Posted by hatsoff

Sounds like you're using the Niven textbook. I did this exercise last fall, and it gave be some trouble too. It is indeed proved by Gauss's lemma.

Just do a case-by-case proof that $x^2\equiv 2\pmod{p}$ has a solution given that $p\equiv 1$ , then $p\equiv 3$ , then $p\equiv 5$ , and finally $p\equiv 7\pmod{8}$ . Since those are the only possibilities (even numbers won't work), the conclusion will follow.

Consider Gauss's lemma, and let $a=2$ , and observe that each $i\in\{2,4,6,\cdots,p-1\}$ is its own least positive residue modulo $p$ . Let $n$ denote the number of integers in the set

$\left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}$ .

Then by Gauss's lemma, $\left(\frac{2}{p}\right)=(-1)^n$ .

Now I've acutally read this and Gauss' lemma more carefully, and I have a question.

In our problem, the list of the residues are {2,4,6,...,p-1}, note that they are all even, but then Gauss' lemma says: let n be the number of these residues that are greater than p/2.

However, in your proof, you said that n is the number of integers in $\left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}$ . But how do you know that (p+1)/2 is even? and why is (p+3)/2 even?

Thanks for clarifying!

**hatsoff** · March 3rd 2010, 08:25 AM

Originally Posted by kingwinner

Now I've acutally read this and Gauss' lemma more carefully, and I have a question.

In our problem, the list of the residues are {2,4,6,...,p-1}, note that they are all even, but then Gauss' lemma says: let n be the number of these residues that are greater than p/2.

However, in your proof, you said that n is the number of integers in $\left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}$ . But how do you know that (p+1)/2 is even? and why is (p+3)/2 even?

Thanks for clarifying!

Oops.... Yes, I meant to write "let $n$ denote the number of even integers" in that set. Sorry for the confusion.

**kingwinner** · March 3rd 2010, 01:24 PM

Originally Posted by hatsoff

Now comes the tricky part: Let $m$ denote the number of even positive integers less than $p/2$ . Then $n=[(p-1)/2]-m$ . But what is $m$ ? Well, $m=(p-1)/4$ iff $(p-1)/4$ is an integer; overwise $m=(p-3)/4$ .

Sorry, one more question...

Can you explain in more detail why $m=(p-1)/4$ iff $(p-1)/4$ is an integer; otherwise $m=(p-3)/4$ ? I don't understand this part.

Thanks a lot!

**hatsoff** · March 3rd 2010, 02:33 PM

Originally Posted by kingwinner

Sorry, one more question...

Can you explain in more detail why $m=(p-1)/4$ iff $(p-1)/4$ is an integer; otherwise $m=(p-3)/4$ ? I don't understand this part.

Thanks a lot!

Let me put it this way:

$m=$ the number of even positive integers $<p/2$ ;

$(p-1)/2=$ the number of even positive integers $<p$ ;

$n=$ the number of even positive integers between $p/2$ and $p$ .

Therefore $\frac{p-1}{2}=m+n$ , or, $n=\frac{p-1}{2}-m$ .

Now, if $\frac{p-1}{2}$ is odd, then how many even positive integers are $<p/2$ ? How about if $\frac{p-1}{2}$ is even?

The answer, of course, is that if $\frac{p-1}{2}$ is odd, then there are $\frac{p-3}{4}$ positive even integers $<p/2$ . But if $\frac{p-1}{2}$ is even, then there are $\frac{p-1}{4}$ positive even integers $<p/2$ .

Thread: Quadratic Residues & Legendre symbol

LinkBack

Thread Tools

Display

Quadratic Residues & Legendre symbol

Similar Math Help Forum Discussions

Quadratic Residue/Legendre Symbol

[SOLVED] Legendre Symbol

Legendre symbol

Legendre Symbol and Quadratic Reciprocity

Legendre Symbol (5/p)

Search Tags