# Let $p > 3$ be a prime number. Show that $x^2 \equiv −3\mod p$ is solvable iff $p\equiv 1\mod 6$.

Let $p > 3$ be a prime number. Show that $x^2 \equiv −3\mod p$ is solvable iff $p\equiv 1\mod 6$.

My try is

let $a$ be a solution of $x^2 \equiv -3 \mod p$. so $a^{p-1} \equiv 1\mod p$. This implies

$$(-1)^{\frac{p-1}2}≡(a^2)^\frac{p-1}2 \mod p.$$

since $p$ is odd, $\frac{p-1}2$ must be even, so $4|(p-1)$. conversely, assume that $p\equiv 1\mod 6...$

• Something strange happening on your line three (the first line of my try). How does $a^2\equiv -3$ imply $a^{p-1}\equiv3$? By Little Fermat we have $a^{p-1}\equiv 1$, so this is fishy. Also "$p$ is odd" does not imply "$(p-1)/2$ is even" as you are claiming on your last line. – Jyrki Lahtonen Jul 29 '14 at 8:58
• – lab bhattacharjee Jul 29 '14 at 9:02
• Also what do you know about Legendre symbols, in particular $\left(\dfrac{-1}p\right)$ and $\left(\dfrac{p}3\right)$, and the law of quadratic reciprocity? – Jyrki Lahtonen Jul 29 '14 at 9:03
• It might help to note that prime $P > 3 \implies P\equiv+1\pmod6 \vee P\equiv-1\pmod6$. – barak manos Jul 29 '14 at 9:46
• Have a look at math.stackexchange.com/questions/685958/… – Jack D'Aurizio Jul 29 '14 at 9:56

If $p \equiv 1 \pmod 6$ then $6 \mid |\mathbb{F}_p^{\ast}|$ so there exists a primitive sixth root of unity $\alpha \in \mathbb{F}_p$ which therefore satisfies $\alpha^2-\alpha+1 = 0$. Then $(2\alpha - 1)^2 = -3$. Conversely, if $p \not \in \{2,3\}$ and $x^2 = -3$ for some $x\in \mathbb{F}_p$ then $\alpha = 2^{-1}(x + 1)$ is a sixth root of unity (check that $\alpha, \alpha^2, \alpha^3$ are not equal to $1$ and $\alpha^6=1$) and therefore $6 \mid p-1$.
$x^2\equiv-3\pmod p$ is solvable iff $(-3|p)=(-1|p)(3|p)=1$. ($(\,\cdot\,|\,\cdot\,)$ is the Legendre symbol.)
We already have: \begin{align} (-1|p)&=\begin{cases} 1 &\text{if}\ p\equiv1\pmod4 \\ -1 &\text{if}\ p\equiv-1\pmod4 \end{cases},\\ (3|p)&=\begin{cases} 1 &\text{if}\ p\equiv\pm1\pmod{12} \\ -1 &\text{if}\ p\equiv\pm5\pmod{12} \end{cases}. \end{align} (you can easily prove these by quadratic reciprocity, with seperating cases.)
So we have: $$(-3|p)=\begin{cases} 1 &\text{if}\ p\equiv1\pmod6 \\ -1 &\text{if}\ p\equiv-1\pmod6 \end{cases},$$ and that is the result.