I'm trying to prove this as part of a step by step proof that there are infinitely many primes congruent to $1$ modulo $3$. It is clear that $p$ is incongruent to $0$ modulo $3$ but I am having trouble proving that $p$ must be incongruent to $2$ modulo $3$.
Any hints would be much appreciated.
On
Continuing on from my question and using the hint from lulu.
As $m^2+m+1 \equiv 0 \mod p $, we have that $m \equiv \frac{-1 \pm \sqrt{-3}}{2} \mod p $ and so $-3$ must be a quadratic residue modulo $p$. So $\left(\frac{-3}{p}\right)=+1$. Using the multiplicity of the Legendre symbol, $\left(\frac{3}{p}\right)\left(\frac{-1}{p}\right)=+1$, so either both Legendre symbols are $+1$ or both are $-1$. Suppose they are both $-1$. then $p\equiv3 \mod 4$, and so $\left(\frac{3}{p}\right)=-\left(\frac{p}{3}\right)=-1$. So $\left(\frac{p}{3}\right)=+1$, so $p$ is a quadratic residue modulo $3$, so $p$ is congruent to $1$ modulo $3$. Similarly, if both Legendre symbols are $+1$ we again find that $p$ must be a quadratic residue modulo $3$ and so is congruent to $1$ modulo $3$.
$f(X)=X^2+X+1$ is the third cyclotomic polynomial.
Let $p\ne3$ and $f(m)\equiv0\pmod 3$. Then $m^3\equiv1\pmod p$ but $m\not\equiv1\pmod p$. Thus $m$ has order $3$ in the multiplicative group modulo $p$. By Lagrange's theorem $3\mid p-1$.
Essentially the same argument shows that if $\Phi_n(m)\equiv0\pmod p$ where $p$ is a prime not dividing $n$, and $\Phi_n$ is the $n$-th cyclotomic polynomial, then $n\mid p-1$.