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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.