Demonstrate that all integers of a certain form are divisible by primes of a certain other form I wish to demonstrate that for any $n\in\mathbb{N}$ all prime divisors of a number $n^2 + n + 1$ are either equal to $3$ or of the form $3k + 1$ with positive integer $k$.
Thus far, I have tried checking cases. If $n$ is of the form $3m+1$, we have that
$n^2+n+1=(3m+1)^2+(3m+1)+1=9m^2+9m+3=3(3m^2+3m+1)$, which is clearly divisible by 3.
If $n$ is of the form $3m$, we have
$n^2+n+1=(3m)^2+(3m)+1=9m^2+3m+1=3(3m^2+m)+1$
If $n$ is of the form $3m+2$, we have
$n^2+n+1=(3m+2)^2+(3m+2)+1=9m^2+15m+7=3(3m^2+5m+2)+1$
The only problem is that since $(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1$, the numbers being of the form $3k+1$ does not prove that their divisors must be of the form $3k+1$, so this does not really prove anything.
Any input is highly appreciated.

Disclaimer: The following answer is based on finite fields, where the polynomial $x^2+x+1$ should ring some bells. 
We have 
$$n^3-1 = (n-1)(n^2+n+1).$$
Now let $p$ be a prime of the form $p = 3k+2$ for some positive $k$ and assume that $p$ divides $n^2+n+1$ and thus also divides $n^3-1$. Then we have that
$$n^3 \equiv 1 \mod{p}.$$
Looking at the finite field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$, we thus get that either $$n \equiv 1 \mod{p}$$ or $n$ is an element of order three in the unit group of $\mathbb{F}_p$. But this unit group has order $3k+1$ and can thus not contain elements of order three.
Therefore, the second case is not possible and we conclude $n \equiv 1 \mod{p}$, meaning that $p$ divides $n-1$.
Now, all that is left is to compute $gcd(n-1,n^2+n+1)$ to get that $p$ does not divide $n^2+n+1$.
(Hint: That gcd will be either three or one, but never include $p > 3$.)
