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?

  • $\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 '18 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$ – 伽罗瓦 May 21 '18 at 21:01
  • $\begingroup$ @Ah yes my mistake. Thank you! $\endgroup$ – the man May 21 '18 at 21:03

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.