# $3$ is a quadratic residue $\bmod p$ iff $p \equiv \pm 1 \bmod12$

Could anyone give me any hints as to how to prove this?

I've tried using Euler's formula $3^\frac{p-1}{2} \equiv \left(\frac{3}{p}\right)\bmod p$, and quadratic reciprocity but I'm not getting anywhere!

I've tried messing around with the Legendre symbol, and I've looked at the proofs which show for what primes $p$, $-1$ and $2$ are quadratic residues, but I'm stuck on this one!

You're close: $\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)(-1)^{\frac{p-1}{2}}$ by reciprocity. So, either $\left(\frac{p}{3}\right)=1$ and $p=1 \bmod{4}$ or $\left(\frac{p}{3}\right)=-1$ and $p=3 \bmod{4}$. Can you finish it off yourself from here?
• @So we get $p \equiv 1 mod 3$ and $p \equiv 1mod4$ or $p \equiv 0,2 mod3$ and $p \equiv 3mod4$? Commented May 21, 2018 at 20:55
• It's weird to say $p \equiv 0 \pmod{3}.$ But if $p \equiv 1 \pmod{3}$ and $p \equiv 1 \pmod{4}$ then $p = 1 + 3k$ and $3k \equiv 0 \pmod{4}$ which tells you $k \equiv 0 \pmod{4}.$ Commented May 21, 2018 at 21:01