For which prime numbers $p$ does the congruence $x^2 + x + 1 \equiv 0 \pmod{p}$ have solutions?

Question

For which prime numbers p does the congruence $x^2 + x + 1 \equiv 0 \pmod{p}$ have solutions?

We've recently learnt about quadratic reciprocity in class, however I am not sure how to tackle this problem. I have tried starting with the $b^2-4ac$ (discriminant) but that hasn't really helped.

Answer 1

Hint: Consider $4(x^2 +x+1) = (2x+1)^2 + 3$. Therefore, if it has a solution modulo $p$, $-3$ must be a quadratic residue. Use quadratic reciprocity.

Answer 2

Simpler than reciprocity: $\,x^2+x+1 \equiv 0 \,\overset{\large {\cdot\, (x-1)}}\Rightarrow\,x^3\equiv 1,\ $ so by basic results on cyclic groups $\ldots$