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##