Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
