Quadratic Residue and Quadratic Reciprocity Law QRL

[Lexaila]

Homework Statement

Show that p-6 is a quadratic residue modulo p if p \equiv 1,5,7,11 (mod 24)

Relevant Equations

legendre

(p-6/p)=(-1/p)(2/p)(3/p)

Make a table, so at the head row you have p(mod24), (-1/p), (2/p), QRL+-, (p/3) and finally (p-6/p), with in the head column below p (mod 24): 1,5,7,11

 

[fresh_42]

What is your question?

 

[Lexaila]

How do we make the table to show that p-6 is a quadratic residue modulo p if p \equiv 1,5,7,11 (mod 24)?

 

[fresh_42]

I suggest using Euler's criterion to calculate the values of the Legendre symbols. So you get the following structure:

p mod 24:​	1​	5​	7​	11​
(-1/p):​	​	​	​	​
(2/p):​	​	​	​	​
(3/p):​	​	​	​	​

Then multiply the three values. This gives you $(-6/p).$ Why is that equal to $(p-6/p)$?

E.g., if $p\equiv 7 \pmod{24}$ then $\dfrac{p-1}{2}\equiv 3\pmod{24}$ and $(-1/p)=(-1)^3=-1.$

 

[Lexaila]

I suggest using Euler's criterion to calculate the values of the Legendre symbols. So you get the following structure:

p mod 24:​	1​	5​	7​	11​
(-1/p):​	​	​	​	​
(2/p):​	​	​	​	​
(3/p):​	​	​	​	​

Then multiply the three values. This gives you $(-6/p).$ Why is that equal to $(p-6/p)$?

E.g., if $p\equiv 7 \pmod{24}$ then $\dfrac{p-1}{2}\equiv 3\pmod{24}$ and $(-1/p)=(-1)^3=-1.$

Thank you for your reply!
In our table we must also use QRL+- in between (2/p) and (3/p). I understand how to fill the rest of the table with 1 and -1, but not this QRL+- column and how it determines the final result of (p-6/p).

p mod 24:​	(-1/p)​	(2/p)​	QRL+-​	(3/p)​	(p-6 / p)
1​	1​	1​	?​	1​
5​	1​	-1​	?​	-1​
7	-1	1	?	1
11​	-1​	-1	?​	-1​

 

[fresh_42]

I didn't quite understand this either since a) Euler's criterion is based on QRL (IIRC), b) we already used it in the equations $(p-6/p)=(-6/p)$ and $(a/p)\cdot (b/p) = (ab/p).$ Maybe they simply meant the resulting product of the other three.

Edit: Or you should actually solve $p-6=x^2 \pmod{p}$ for $x$ in that row.

 

[Lexaila]

I didn't quite understand this either since a) Euler's criterion is based on QRL (IIRC), b) we already used it in the equations $(p-6/p)=(-6/p)$ and $(a/p)\cdot (b/p) = (ab/p).$ Maybe they simply meant the resulting product of the other three.

Edit: Or you should actually solve $p-6=x^2 \pmod{p}$ for $x$ in that row.

I'm still a bit confused, could you please give me an example from the table?

 

[fresh_42]

I'm still a bit confused, could you please give me an example from the table?

E.g. I get for $p\equiv 5\pmod{24}$ with
$$
\left(\dfrac{p-6}{p}\right)\equiv \left(\dfrac{-6}{p}\right)=\left(\dfrac{-1}{p}\right)\left(\dfrac{2}{p}\right)\left(\dfrac{3}{p}\right)
$$
from your table, that $\left(\dfrac{p-6}{p}\right)=1.$ I would simply write a plus in the column QRL (and a minus in cases where the result is $-1.$

I thought we could determine a value for which $p-6\equiv x^2\pmod{p}$ but I confused $\pmod{p}$ with $\pmod{24}.$ For the example above we would get for $p=53$ that $p-6=47\equiv 10^2\pmod{53}$ and for $p=101$ that $p-6=95=14^2\pmod{101}.$ We have in both cases $x=2p-6$ and $p-6\equiv x^2\pmod{p}.$ I don't know if this is a pattern or just luck. My practice on QRL applications is a bit rusty. You are the one who has the book.

 

[martinbn]

Not sure what table they want, but you need to use the reciprocity law. It says that
$\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}2}$,
$\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}8}$,
$\left(\dfrac{3}{p}\right)=\left(\dfrac{p}{3}\right)(-1)^{\frac{p-1}2}(-1)^{\frac{3-1}2}$
then
$\left(\dfrac{-1}{p}\right)\left(\dfrac{2}{p}\right)\left(\dfrac{3}{p}\right)=(-1)^{\frac{p^2-1}8}\left(\dfrac{p}{3}\right)$.

 

[Lexaila]

Not sure what table they want, but you need to use the reciprocity law. It says that
$\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}2}$,
$\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}8}$,
$\left(\dfrac{3}{p}\right)=\left(\dfrac{p}{3}\right)(-1)^{\frac{p-1}2}(-1)^{\frac{3-1}2}$
then
$\left(\dfrac{-1}{p}\right)\left(\dfrac{2}{p}\right)\left(\dfrac{3}{p}\right)=(-1)^{\frac{p^2-1}8}\left(\dfrac{p}{3}\right)$.

Thank you, it solves that question!

But if I have a different example, such as ( (p+3)/2 /p) = (2/p)(3/p) and when I try to use
$\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}8}$,
$\left(\dfrac{3}{p}\right)=\left(\dfrac{p}{3}\right)(-1)^{\frac{p-1}2}(-1)^{\frac{3-1}2}$
for, for example, p (mod24) with p=23, I get $(-1)^{\frac{23^2-1}8}=1$ and $\left(\dfrac{23}{3}\right)(-1)^{\frac{23-1}2}(-1)^{\frac{3-1}2}=(-1)*(-1)*(-1)=-1$, so we get $1*-1=-1$, while it should be 1. Could you please tell me where I'm going wrong?

 

[martinbn]

Thank you, it solves that question!

But if I have a different example, such as ( (p+3)/2 /p) = (2/p)(3/p) and when I try to use
$\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}8}$,
$\left(\dfrac{3}{p}\right)=\left(\dfrac{p}{3}\right)(-1)^{\frac{p-1}2}(-1)^{\frac{3-1}2}$
for, for example, p (mod24) with p=23, I get $(-1)^{\frac{23^2-1}8}=1$ and $\left(\dfrac{23}{3}\right)(-1)^{\frac{23-1}2}(-1)^{\frac{3-1}2}=(-1)*(-1)*(-1)=-1$, so we get $1*-1=-1$, while it should be 1. Could you please tell me where I'm going wrong?

It seems you forgot the $(-1)^{\frac{p-1}2}=(-1)^{\frac{23-1}2}=-1$