Find the set of primes $p$ which $6$ is a quadratic residue $\mod p$

Question

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.

Answer 1

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

Answer 2

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}$.