For which prime numbers $p$ does the congruence $x^2+x+1\equiv0\pmod p$ have solutions?

For $p\ne2$ we have $$x^2+x+1\equiv0\pmod p\quad\Leftrightarrow\quad (2x+1)^2\equiv-3\pmod p\ .$$

Does this mean the above congruence has a solution$\pmod p$ for any $p>2$ such that the quadratic residue modulo $p$ is 1?

• Feb 4, 2015 at 11:32

Yes, the congruence $x^2+x+1\equiv 0\pmod{p}$ has a solution for the prime $p\gt 2$ if and only if $-3$ is a quadratic residue of $p$. For by your argument, if there is a solution of $x^2+x+1\equiv 0\pmod{p}$, then $(2x+1)^2\equiv -3\pmod{p}$. In the other direction, if $w^2\equiv -3\pmod{p}$, then we can solve the original congruence by solving $2x++1\equiv w\pmod{p}$, which is always possible.
Now to finish characterizing the primes such that $x^2+x+1\equiv 0\pmod{p}$ is solvable, note that either
(i) $p$ is of the form $4k+1$, and $3$ is a quadratic residue of $p$ or
(ii) $p$ is of the form $4k+3$, and $3$ is a non-residue of $p$.
To compute the Legendre symbol $(p/3)$ in cases (i) and (ii), use Quadratic Reciprocity. It is easy to describe the odd $p$ such that $(3/p)=1$.