Prove that $-3$ is a quadratic residue mod an odd prime $>3$ if and only if $p$ is of the form of $6n+1$

Question

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.

Answer 1

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

Answer 2

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