Since $6$ is not prime (law of quadratic reciprocity could have been used), how does one find the set of primes $p$ for which $6$ is a quadratic residue $\pmod p$? I noticed that $6$ is a quadratic residue $\pmod p$ for the following $p$ up to $100: 2, 3, 5, 19, 23, 29, 43, 47, 53, 67, 71, 73, 97$. I don't recognize an immediate congruence. I know that every prime $p$ that $2$ is a quadratic residue is congruent to $1, 7 \pmod 8$, and every prime $p$ that $3$ is a quadratic residue is congruent to $1, 11 \pmod {12}$, yet I see primes congruent to $1, 3, 5, 7 \pmod 8$ and also primes congruent to $1, 5, 7, 11 \pmod {12}$. Any help appreciated.
2 Answers
Use the fact that Legendre symbol is completely multiplicative: $$1=\left(\frac{6}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{3}{p}\right)$$ which means either $$\left(\frac{2}{p}\right)=\left(\frac{3}{p}\right)=1$$ or $$\left(\frac{2}{p}\right)=\left(\frac{3}{p}\right)=-1$$ and (same link) $${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1&{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}.\end{cases}}}$$ $${\displaystyle \left({\frac {3}{p}}\right)=(-1)^{{\big \lfloor }{\frac {p+1}{6}}{\big \rfloor }}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}11{\pmod {12}}\\-1&{\mbox{ if }}p\equiv 5{\mbox{ or }}7{\pmod {12}}.\end{cases}}}$$
Now you have 8 cases to analyse.
- $p=8k+1=12t+1 \Rightarrow p=24m+1$
- $p=8k+1=12t+11$ has no integer solutions
- $p=8k+7=12t+1$ has no integer solutions
- $p=8k+7=12t+11 \Rightarrow p=24m+23$
- $p=8k+3=12t+5$ has no integer solutions
- $p=8k+3=12t+7 \Rightarrow p=24m+19$
- $p=8k+5=12t+5 \Rightarrow p=24m+5$
- $p=8k+5=12t+7$ has no integer solutions
-
$\begingroup$ If I understand correctly, let $6$ is a quadratic residue $\pmod p$. Then either $x^2=2 \pmod p$ and $x^2=3 \pmod p$ are both solvable, or they or both not solvable? $\endgroup$– J. LinneCommented Jun 29, 2018 at 19:39
-
$\begingroup$ Yes, from $1=\left(\frac{6}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{3}{p}\right)$ $\endgroup$– rtybaseCommented Jun 29, 2018 at 19:44
By quadratic reciprocity, if $a$ is a positive integer and $p\equiv q\pmod {4a}$ are primes, then $ \left(\frac ap\right)=\left(\frac aq\right)$. So to answer your question, you need only consider primes $\equiv1,5,7,11,13,17,19,23\pmod{24}$. All of these are prime, save $1$. But $6$ is a quadratic residue modulo $73$. From your calculations, $6$ is a quadratic residue modulo $p$ ($p>3$) iff $p\equiv1,5,19$ or $23\pmod{24}$.