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!


1 Answer 1


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?

  • $\begingroup$ @So we get $ p \equiv 1 mod 3$ and $p \equiv 1mod4$ or $p \equiv 0,2 mod3$ and $p \equiv 3mod4$? $\endgroup$
    – the man
    May 21, 2018 at 20:55
  • $\begingroup$ 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}.$ $\endgroup$
    – green frog
    May 21, 2018 at 21:01
  • $\begingroup$ @Ah yes my mistake. Thank you! $\endgroup$
    – the man
    May 21, 2018 at 21:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .