Determine the set of odd primes ## p ##?

[Math100]

Homework Statement

Determine the set of odd primes $p$ for which $23$ is a quadratic residue.

Relevant Equations

If $p$ and $q$ are distinct odd primes, then $(p|q)=(q|p)$, if either $p\equiv 1\pmod {4}$ or $q\equiv 1\pmod {4}$, and $-(q|p)$, if $p\equiv q\equiv 3\pmod {4}$.

Let $p$ be an odd prime.
Then $23$ is a quadratic residue modulo $p$ if $(23|p)=1$.
Applying the Quadratic Reciprocity Law produces:
$(23|p)=(p|23)$ if $p\equiv 1\pmod {4}$
$(23|p)=-(p|23)$ if $p\equiv 3\pmod {4}$.
Now we consider two cases.
Case #1: Suppose $p\equiv 1\pmod {4}$.
Then $(23|p)=(p|23)$.
Observe that $(23|p)=1$ if $p\equiv 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\pmod {23}$.
By considering the quadratic residues modulo $23$ and $p\equiv 1\pmod {4}$, we have $p\equiv 1\pmod {92}$.
Thus $p\equiv 1\pmod {92}\in\left \{ 1, 9, 13, 25, 29, 41, 49, 73, 77, 81, 85 \right \}$.
Case #2: Suppose $p\equiv 3\pmod {4}$.
Then $(23|p)=-(p|23)$.
Observe that $(23|p)=1$ if $p\equiv 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22\pmod {23}$.
As in case #1, we consider $p\equiv 1\pmod {92}$.
Thus $p\equiv 1\pmod {92}\in\left \{ 7, 11, 15, 19, 43, 51, 63, 67, 79, 83, 91 \right \}$.
Therefore, the set of odd primes $p$ for which $23$ is a quadratic residue is
$\left \{ 1, 7, 9, 11, 13, 15, 19, 25, 29, 41, 43, 49, 51, 63, 67, 73, 77, 79, 81, 83, 85, 91 \right \}$.

 

[fresh_42]

Homework Statement:: Determine the set of odd primes $p$ for which $23$ is a quadratic residue.
Relevant Equations:: If $p$ and $q$ are distinct odd primes, then $(p|q)=(q|p)$, if either $p\equiv 1\pmod {4}$ or $q\equiv 1\pmod {4}$, and $-(q|p)$, if $p\equiv q\equiv 3\pmod {4}$.

Let $p$ be an odd prime.
Then $23$ is a quadratic residue modulo $p$ if $(23|p)=1$.
Applying the Quadratic Reciprocity Law produces:
$(23|p)=(p|23)$ if $p\equiv 1\pmod {4}$
$(23|p)=-(p|23)$ if $p\equiv 3\pmod {4}$.
Now we consider two cases.
Case #1: Suppose $p\equiv 1\pmod {4}$.
Then $(23|p)=(p|23)$.

So far so good.

Observe that $(23|p)=1$ if $p\equiv 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\pmod {23}$.

Maybe, but why?

And what about $(23|p)=-1$? Case 1 only says they are equal, not equal to $1.$

By considering the quadratic residues modulo $23$ and $p\equiv 1\pmod {4}$, we have $p\equiv 1\pmod {92}$.

How? Why does $23|(p-1)$?

Thus $p\equiv 1\pmod {92}\in\left \{ 1, 9, 13, 25, 29, 41, 49, 73, 77, 81, 85 \right \}$.
Case #2: Suppose $p\equiv 3\pmod {4}$.
Then $(23|p)=-(p|23)$.
Observe that $(23|p)=1$ if $p\equiv 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22\pmod {23}$.
As in case #1, we consider $p\equiv 1\pmod {92}$.
Thus $p\equiv 1\pmod {92}\in\left \{ 7, 11, 15, 19, 43, 51, 63, 67, 79, 83, 91 \right \}$.
Therefore, the set of odd primes $p$ for which $23$ is a quadratic residue is
$\left \{ 1, 7, 9, 11, 13, 15, 19, 25, 29, 41, 43, 49, 51, 63, 67, 73, 77, 79, 81, 83, 85, 91 \right \}$.

 

[fresh_42]

Here are the formulas I used to check your calculations:
https://de.wikipedia.org/wiki/Legendre-Symbol
https://de.wikipedia.org/wiki/Quadratisches_Reziprozitätsgesetz

They do not show how $p\equiv 1\pmod{23}$ follows from $(23|p)=(p|23)=1.$
Maybe you used further formulas.

 

[Math100]

So far so good.

Maybe, but why?

And what about $(23|p)=-1$? Case 1 only says they are equal, not equal to $1.$

How? Why does $23|(p-1)$?

Because $1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18$ are the quadratic residues modulo $23$.
And the quadratic non-residues modulo $23$ are $5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22$.
Lastly, $23\cdot 4=92$.

 

[Math100]

Here are the formulas I used to check your calculations:
https://de.wikipedia.org/wiki/Legendre-Symbol
https://de.wikipedia.org/wiki/Quadratisches_Reziprozitätsgesetz

They do not show how $p\equiv 1\pmod{23}$ follows from $(23|p)=(p|23)=1.$
Maybe you used further formulas.

I didn't use other formulas. The computation I got is from an example of a similar problem from a source which I couldn't find now.

 

[fresh_42]

Because $1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18$ are the quadratic residues modulo $23$.

... says who? How did you check that?

And the quadratic non-residues modulo $23$ are $5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22$.

... says who? How did you check that?

Lastly, $23\cdot 4=92$.

I know. What I do not know is why $23|(p-1).$

We are interested in primes $p$ such that $23$ is a quadratic residues modulo $p$. This means $(23|p)=1$ which by the way answers my first question why you didn't consider the other case $(23|p)=-1.$ But that only says that there is an integer $x\in \mathbb{Z}$ such that $23 \equiv x^2\pmod{p}.$ It does not say $x=1.$ How do we know that $23|(p-1)?$ And where would you need this? Your solutions for $p$ aren't congruent $1$ modulo $92.$

 

[Math100]

... says who? How did you check that?

... says who? How did you check that?

I know. What I do not know is why $23|(p-1).$

We are interested in primes $p$ such that $23$ is a quadratic residues modulo $p$. This means $(23|p)=1$ which by the way answers my first question why you didn't consider the other case $(23|p)=-1.$ But that only says that there is an integer $x\in \mathbb{Z}$ such that $23 \equiv x^2\pmod{p}.$ It does not say $x=1.$ How do we know that $23|(p-1)?$ And where would you need this? Your solutions for $p$ aren't congruent $1$ modulo $92.$

By the Quadratic residue formula, $x^2\equiv q\pmod {n}$. Since $n=23$ in this problem, the integer $q$ is the quadratic residue modulo $n$. And the left over integers are quadratic nonresidues modulo $n$.
\begin{align*}
&1^2\equiv 1\pmod {23}\\
&2^2\equiv 4\pmod {23}\\
&3^2\equiv 9\pmod {23}\\
&\vdots\\
\end{align*}

I think there's also a typo in my first post, where you said I didn't consider the other case $(23|p)=-1$.

 

[fresh_42]

Let me think aloud. We have $\left(\dfrac{23}{p}\right)=\left(\dfrac{p}{23}\right)=1$ in case $p\equiv 1\pmod{4}$ and $\left(\dfrac{23}{p}\right)=1\, , \,\left(\dfrac{p}{23}\right)=-1$ in case $p\equiv 3\pmod{4}.$ These cases come from the condition that $23$ is a quadratic residue modulo an odd prime $p.$

Let's begin with the first case. From $\left(\dfrac{p}{23}\right)=1$ we get that $p$ is a quadratic residue modulo $23.$ Thus $p\equiv x^2\pmod{23}.$ The squares are
\begin{align*}
x^2&\in\{0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484\}\\
&=\{0,1,4,9,16,2,13,3,18,12,8,6,\}=\{0,1,2,3,4,6,8,9,12,13,16,18\} \pmod{23}
\end{align*}
That leaves us with the prime $p=13=4\cdot 3+1$ and $13\equiv 6^2\pmod{23}.$ Finally $\left(\dfrac{13}{23}\right)=1$ since $23\equiv 6^2\pmod{13}.$

In the second case, we have $\left(\dfrac{p}{23}\right)=-1$ and $p=4n+3$ is a quadratic non-residue modulo $23.$ The complementary set to the first case is thus $S:=\{5,7,10,11,14,15,17,19,20,21,22\}.$
This means $p = 4n+3 \equiv s\pmod{23}$ for some $s\in S$ and prime. Therefore $p\in \{7,11,19\}=:S'.$ To check whether these three primes are actual solutions, we need to solve $23\equiv x^2\pmod{p}$ for all $p\in S'.$

The last step has to be done because we concluded from the premises that $p$ has to be in $\{7,11,13,19\}$, but not, that all of them actually solve our problem. (I checked.)

These are considerably fewer primes than you have, even if I delete all non-primes from your list. I took $p=67$ from your solution and found $23\equiv 31^2\pmod{67}.$ So I lost solutions somewhere.

Your list (only primes) is $\{7, 11, 13, 19, 29, 41, 43, 67, 73, 79, 83\}.$ I checked them and they are indeed solutions.

a) Do you see where I lost the solutions $\{29, 41, 43, 67, 73, 79, 83 \}$?
b) How can we know that there aren't even more solutions greater than $92$?
c) What about $15^2=225=2\cdot 101 +23 \equiv 23\pmod{101}$ or $34^2=1156=11\cdot 103+23\equiv 23\pmod{103}$?

 

[Math100]

Let me think aloud. We have $\left(\dfrac{23}{p}\right)=\left(\dfrac{p}{23}\right)=1$ in case $p\equiv 1\pmod{4}$ and $\left(\dfrac{23}{p}\right)=1\, , \,\left(\dfrac{p}{23}\right)=-1$ in case $p\equiv 3\pmod{4}.$ These cases come from the condition that $23$ is a quadratic residue modulo an odd prime $p.$

Let's begin with the first case. From $\left(\dfrac{p}{23}\right)=1$ we get that $p$ is a quadratic residue modulo $23.$ Thus $p\equiv x^2\pmod{23}.$ The squares are
\begin{align*}
x^2&\in\{0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484\}\\
&=\{0,1,4,9,16,2,13,3,18,12,8,6,\}=\{0,1,2,3,4,6,8,9,12,13,16,18\} \pmod{23}
\end{align*}
That leaves us with the prime $p=13=4\cdot 3+1$ and $13\equiv 6^2\pmod{23}.$ Finally $\left(\dfrac{13}{23}\right)=1$ since $23\equiv 6^2\pmod{13}.$

In the second case, we have $\left(\dfrac{p}{23}\right)=-1$ and $p=4n+3$ is a quadratic non-residue modulo $23.$ The complementary set to the first case is thus $S:=\{5,7,10,11,14,15,17,19,20,21,22\}.$
This means $p = 4n+3 \equiv s\pmod{23}$ for some $s\in S$ and prime. Therefore $p\in \{7,11,19\}=:S'.$ To check whether these three primes are actual solutions, we need to solve $23\equiv x^2\pmod{p}$ for all $p\in S'.$

The last step has to be done because we concluded from the premises that $p$ has to be in $\{7,11,13,19\}$, but not, that all of them actually solve our problem. (I checked.)

These are considerably fewer primes than you have, even if I delete all non-primes from your list. I took $p=67$ from your solution and found $23\equiv 31^2\pmod{67}.$ So I lost solutions somewhere.

Your list (only primes) is $\{7, 11, 13, 19, 29, 41, 43, 67, 73, 79, 83\}.$ I checked them and they are indeed solutions.

a) Do you see where I lost the solutions $\{29, 41, 43, 67, 73, 79, 83 \}$?
b) How can we know that there aren't even more solutions greater than $92$?
c) What about $15^2=225=2\cdot 101 +23 \equiv 23\pmod{101}$ or $34^2=1156=11\cdot 103+23\equiv 23\pmod{103}$?

From the second case, I found out that $(7|23)=(11|23)=(19|23)=-1$ because $23\equiv 3^{2}\pmod {7}, 23\equiv 1^{2}\pmod {11}, 23\equiv 2^{2}\pmod {19}$ from solving $23\equiv x^2\pmod {p}$ for all $p\in\left \{ 7, 11, 19 \right \}$. But I do not see where you lost the solutions $\{29, 41, 43, 67, 73, 79, 83 \}$, I also realized that I made many mistakes in my first post and included many illogical assumptions such as $23\mid (p-1)$. Can you please tell me how to find those solutions that were lost? And the fact that there aren't more solutions greater than $92$?

 

[fresh_42]

We know from the quadratic residue law and our given conditions that for a prime $p$ to be a solution, there has to hold
$$
\left(\dfrac{p}{23}\right)=\underbrace{\left(\dfrac{23}{p}\right)}_{=1}\cdot \left(\dfrac{p}{23}\right)=(-1)^{\frac{11}{2}(p-1)}=
\begin{cases}
1&\text{ if } p\equiv 1\pmod{4}\\
-1&\text{ if } p\equiv 3\pmod{4}
\end{cases}
$$
This means that $p$ has to be a quadratic residue modulo $23$ in case $p\equiv 1\pmod{4}$ and a quadratic non-residue modulo $23$ in case $p\equiv 3\pmod{4}.$

As you correctly listed are all remainders $\{0,1,2,3,4,6,8,9,12,13,16,18\} \pmod{23}$ those from some squares, and all remainders $\{5,7,10,11,14,15,17,19,20,21,22\}\pmod{23}$ are not.

So $23$ is a quadratic residue modulo a prime $p \equiv 1\pmod{4}$ if $p\equiv r\pmod{23}$ for some $r\in \{0,1,2,3,4,6,8,9,12,13,16,18\}$ and a quadratic residue modulo a prime $p\equiv 3\pmod{4}$ if $p\equiv s\pmod{23}$ for some $s\in \{5,7,10,11,14,15,17,19,20,21,22\}.$

I am afraid it is simple as that. You only have to put the arguments in order. You should check whether your list of primes fulfills these conditions, and also check $\{17,97,101,103,113\}$ for which we already know whether they are a solution or not. ($17,97,113$ are no solutions, $101,103$ are solutions.) You should also check whether you have all primes less than $100$ that are a solution in your list.

 

[Math100]

We know from the quadratic residue law and our given conditions that for a prime $p$ to be a solution, there has to hold
$$
\left(\dfrac{p}{23}\right)=\underbrace{\left(\dfrac{23}{p}\right)}_{=1}\cdot \left(\dfrac{p}{23}\right)=(-1)^{\frac{11}{2}(p-1)}=
\begin{cases}
1&\text{ if } p\equiv 1\pmod{4}\\
-1&\text{ if } p\equiv 3\pmod{4}
\end{cases}
$$
This means that $p$ has to be a quadratic residue modulo $23$ in case $p\equiv 1\pmod{4}$ and a quadratic non-residue modulo $23$ in case $p\equiv 3\pmod{4}.$

As you correctly listed are all remainders $\{0,1,2,3,4,6,8,9,12,13,16,18\} \pmod{23}$ those from some squares, and all remainders $\{5,7,10,11,14,15,17,19,20,21,22\}\pmod{23}$ are not.

So $23$ is a quadratic residue modulo a prime $p \equiv 1\pmod{4}$ if $p\equiv r\pmod{23}$ for some $r\in \{0,1,2,3,4,6,8,9,12,13,16,18\}$ and a quadratic residue modulo a prime $p\equiv 3\pmod{4}$ if $p\equiv s\pmod{23}$ for some $s\in \{5,7,10,11,14,15,17,19,20,21,22\}.$

I am afraid it is simple as that. You only have to put the arguments in order. You should check whether your list of primes fulfills these conditions, and also check $\{17,97,101,103,113\}$ for which we already know whether they are a solution or not. ($17,97,113$ are no solutions, $101,103$ are solutions.) You should also check whether you have all primes less than $100$ that are a solution in your list.

That's what I was thinking earlier too. Sorry for the late response. I see it now.

 

[Math100]

And I have another question, since you said that $92$ is therefore not an upper bound for possible values $p$, shouldn't the answer be infinitely many primes $p$? Don't we have infinitely many prime numbers?

 

[fresh_42]

--

And I have another question, since you said that $92$ is therefore not an upper bound for possible values $p$, shouldn't the answer be infinitely many primes $p$? Don't we have infinitely many prime numbers?

Probably, but not necessarily. One would have to prove it. Theoretically, it could be the case that there is a number $N\in \mathbb{N}$ such that:
\begin{align*}
\forall \,p>N \, &: \,p\text{ prime and } p\equiv 1\pmod{4} \Rightarrow p\equiv \{5,7,10,11,14,15,17,19,20,21,22\}\pmod{23}\\
\forall \,p>N \, &: \,p\text{ prime and } p\equiv 3\pmod{4} \Rightarrow p\equiv \{0,1,2,3,4,6,8,9,12,13,16,18\}\pmod{23}
\end{align*}
This is not very likely, however, neither is it obvious. I haven't looked into it, but maybe the theorems of Green-Tao and/or Szemerédi can help.

 

[fresh_42]

$23\equiv x^2\pmod{1009}$ has no solution since $1009\equiv 20\pmod{23}\wedge 1009\equiv 1\pmod{4}.$
$23\equiv x^2\pmod{1019}$ has a solution since $1019\equiv 7\pmod{23}\wedge 1019\equiv 3\pmod{4}.$
It is $23\equiv 467^2\pmod{1019}.$

So whatever $N$ would be, and I doubt it exists, we already know that $N\ge 1019.$

In case you cannot sleep:
https://de.wikibooks.org/wiki/Primzahlen:_Tabelle_der_Primzahlen_(2_-_100.000)

 

[Math100]

$23\equiv x^2\pmod{1009}$ has no solution since $1009\equiv 20\pmod{23}\wedge 1009\equiv 1\pmod{4}.$
$23\equiv x^2\pmod{1019}$ has a solution since $1019\equiv 7\pmod{23}\wedge 1019\equiv 3\pmod{4}.$
It is $23\equiv 467^2\pmod{1019}.$

So whatever $N$ would be, and I doubt it exists, we already know that $N\ge 1019.$

In case you cannot sleep:
https://de.wikibooks.org/wiki/Primzahlen:_Tabelle_der_Primzahlen_(2_-_100.000)

Thank you for this!