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


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.