Thread: Quadratic Residues & Legendre symbol

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]

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

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

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 $\displaystyle x^2\equiv 2\pmod{p}$ has a solution given that $\displaystyle p\equiv 1$, then $\displaystyle p\equiv 3$, then $\displaystyle p\equiv 5$, and finally $\displaystyle 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 $\displaystyle a=2$, and observe that each $\displaystyle i\in\{2,4,6,\cdots,p-1\}$ is its own least positive residue modulo $\displaystyle p$. Let $\displaystyle n$ denote the number of integers in the set

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

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

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

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

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

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

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

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

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

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!

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 $\displaystyle p\equiv 1\pmod{8}$. Then $\displaystyle \frac{p-1}{4}$ is an integer, which means

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

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

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

Originally Posted by hatsoff

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

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

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

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

So $\displaystyle 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.

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 $\displaystyle p\equiv 3,5\pmod{8}$, then it follows that there may only be solutions if $\displaystyle p\equiv 1,7\pmod{8}$ (because $\displaystyle p$ is odd).

Originally Posted by hatsoff

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

Oh, yes, that's proof by contrapositive.

Thank you!

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 $\displaystyle x^2\equiv 2\pmod{p}$ has a solution given that $\displaystyle p\equiv 1$, then $\displaystyle p\equiv 3$, then $\displaystyle p\equiv 5$, and finally $\displaystyle 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 $\displaystyle a=2$, and observe that each $\displaystyle i\in\{2,4,6,\cdots,p-1\}$ is its own least positive residue modulo $\displaystyle p$. Let $\displaystyle n$ denote the number of integers in the set

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

Then by Gauss's lemma, $\displaystyle \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 $\displaystyle \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!

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 $\displaystyle \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 $\displaystyle n$ denote the number of even integers" in that set. Sorry for the confusion.

Originally Posted by hatsoff

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

Sorry, one more question...

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

Thanks a lot!

Originally Posted by kingwinner

Sorry, one more question...

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

Thanks a lot!

Let me put it this way:

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

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

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

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

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

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