Can a divisor of $n^2 +n+1$ be $2\operatorname{mod} 3$?

Question

Let $n$ be a natural number. It seems that a divisor of $n^2+n+1$ cannot be $2 \operatorname{mod} 3$.

Couldn't $n^2+n+1$ have an even number of divisors which are $2 \operatorname{mod} 3$?

Answer 1

Hint $\bmod p\!:\ n\not\equiv 1,\, n^{\large 3}\equiv 1 \equiv n^{\large p-1}\,\Rightarrow\, {\rm ord}\,n = 3\mid p-1$

Answer 2

Theorem: if $q \equiv 2 \pmod 3$ is a prime and $$ x^2 + xy + y^2 \equiv 0 \pmod q \; , \; $$ then $q$ divides both $x$ and $y$

In particular, under these circumstances, you cannot have $y=1$

Proof: Legendre symbol $$ (-3|q) = (q|3) $$ using quadratic reciprocity, two cases ($q$ is either $1$ or $3$ $\pmod 4$ )

Also $$ 4( x^2 + xy + y^2) \equiv (2x+y)^2 + 3 y^2 \equiv 0 \pmod q \; , \; $$

Answer 3

Let $p$ be a prime $\equiv 2\bmod 3$. Suppose $p|(n^2+n+1)$. Then also $p|(n^3-1)$ since $n^3-1=(n-1)(n^2+n+1)$.

So $n^{p-1}\equiv 1\bmod p$ from Fermat's Little Theorem and also $n^3\equiv 1\bmod p$ from above. Since $p$ is taken to be $\equiv 2\bmod 3$, the latter implies $n^{p+1}\equiv 1\bmod p$. Then

$n^{3+(p-1)-(p+1)}=n\equiv 1\bmod p$

which is contradictory because $1^2+1+1\equiv 3\not\equiv 0\bmod p$.