How would I prove that $-3$ is a quadratic residue mod an odd prime larger than $3$ if and only if $p$ is of the form of $6n+1$?

The last thing we covered in class last night was Euler criterion where it has a quadratic residue if $a^{(p-1)/2}\equiv -1\pmod p$.

I think he might have been thinking he was getting farther than he did? I just don't know where to go from this.


Remember the formula for the Legendre symbol: $$\left(\frac{a}{p}\right) = a^{\frac{p - 1}{2}} \pmod p.$$

If $p = 6n + 1$, then $$\alpha = \frac{6n + 1 - 1}{2} = 3n$$ and $(-3)^\alpha = 1 \pmod p$.

However, if $p = 6n - 1$, then $$\alpha = \frac{6n - 1 - 1}{2} = 3n - 1$$ and consequently $(-3)^\alpha = -1 \pmod p$.


Let $g$ be a primitive root modulo $p$. If $p=6n+1$, consider $a\equiv g^{2n}$. Prove that (i) $a\not\equiv 1\pmod p$, (ii) $a^3\equiv1\pmod p$, (iii) $a+a^2\equiv-1\pmod p$, (iv) $(a-a^2)^2\equiv -3\pmod p$.

On the other hand, if $b^2\equiv-3\pmod p$, show (i) that $2c\equiv-1+b\pmod p$ has a solution, (ii) $c\not\equiv1\pmod p$, (iii) $c^3\equiv1\pmod p$ and (iv) deduce that $3\mid(p-1)$.

  • $\begingroup$ More simply, $(2a+1)^2\equiv -3\pmod{p}$. $\endgroup$ – user236182 Aug 1 '17 at 16:22

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.