<s>[INST] Find the set of primes $p$ which $6$ is a quadratic residue $\mod p$ 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.
 [/INST] 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

</s>