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.
[Math] Find the set of primes $p$ which $6$ is a quadratic residue $\mod p$
elementary-number-theoryquadratic-formsquadratic-reciprocityquadratic-residues
Best Answer
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.