If a prime $p$ divides $a^2\pm a+1$ for some $a\in\mathbb{N}$, why can't $p$ be congruent to $-1$ modulo $3$?

Question

My question is why the following holds:

$$ p\equiv-1\pmod{3}\Rightarrow p\nmid a^2\pm a+1,\forall a\in \mathbb{N} $$

Answer 1

For $p > 2$, $$a^2 \pm a + 1 = \frac{1}{4} (4a^2 \pm 4a + 4) = \frac{1}{4}(2a \pm 1)^2 + \frac{3}{4}$$ So it suffices to show that $-3$ is a quadratic nonresidue. This follows from quadratic reciprocity. For $p = 2$, $a^2 \pm a + 1$ is easily seen to be always odd.

Answer 2

Even simpler: $(a^2 \pm a + 1)|(a^6 - 1)$. Hence if $a^2 \pm a + 1$ has a root then $a^6 - 1$ has a root which is not $\pm 1$, implying modulo $p$ there is an element of order $3$ or $6$ implying $p \equiv 1 \pmod{3}$ (this fails for $p=3$, but that case we're already done!)