Find all primes $p$ so that 3 is a quadratic nonresidue modulo $p$

Question

I know how to find the quadratic residues modulo a fixed $p$, but I'm not sure how to find all the primes such that an integer, such as 3, is a quadratic nonresidue modulo $p$.

Answer 1

For the moment, assume $p$ is not 2 or 3. We need to find primes $p$ such that $$\left(\frac3p\right)=-1$$ Using quadratic reciprocity: $$\left(\frac3p\right)\left(\frac p3\right)=(-1)^{(p-1)/2\cdot(3-1)/2}$$ $$=(-1)^{(p-1)/2}=\begin{cases} 1&p\equiv1\bmod4\\ -1&p\equiv3\bmod4 \end{cases}$$ We can reduce $\left(\frac p3\right)$ to either $\left(\frac13\right)=1$ if $p\equiv1\bmod3$, or $\left(\frac23\right)=-1$ if $p\equiv2\bmod3$. Then we have $\left(\frac3p\right)=-1$ if one of the following holds:

• $\left(\frac p3\right)=-1$ and $(-1)^{(p-1)/2}=1$: $p\equiv5\bmod12$
• $\left(\frac p3\right)=1$ and $(-1)^{(p-1)/2}=-1$: $p\equiv7\bmod12$

3 is a quadratic residue modulo 2 and 3, since $1^2\equiv3\bmod2$ and $0^2\equiv3\bmod3$. Therefore 3 is a quadratic nonresidue modulo $p$ if $p$ is 5 or 7 modulo 12.