For what prime numbers $p$ is $x^2+x+1$ irreducible in $\mathbb{F}_p[X]$ I think it's enough to search for the prime numbers where $x^2+x+1=0$ is not solvable, but I am not sure where to start. Thank you
 A: $ax^2+bx+c$ is reducible precisely if $b^2-4ac$ has a square root (PS in response to comments: EXCEPT when the characteristic of the field is $2$.  The usual formula for solving quadratic equations cannot apply in that case since dividing by $2a$ would be dividing by $0$.).  In the case of $x^2+x+1$, we have $b^2-4ac=-3$.  So the question is, for which primes $p$ does $-3$ have a square root modulo $p$?
PS: What happens if you try to complete the square in $x^2+\dfrac b a x$ in a field of characteristic $2$?  Usually we're told to find half of $b/a$. In a field of characteristic $2$, you can't take half of anything except $0$.
A: Hint: If $x^{2} + x + 1$ has a non-trivial factor in $\mathbb{F}_{p}[x]$ (and $p \neq 3$), then $x^{3} - 1 = (x-1)(x^{2}+x+1)$ has a root other than $1$ in $\mathbb{F}_{p}$.
A: In order that $x^2+x+1$ splits over $\mathbb{F}_p$ (with $p>3$), the discriminant of $x^2+x+1$, i.e. $-3$, must be a quadratic residue $\!\pmod{p}$. That happens iff $p\equiv 1\pmod{3}$: for a proof, see this other question.
