If $x \not \equiv 1 \pmod 3$, when is $x^2 + x +1$ not a prime? If $x \not\equiv1 \pmod 3$, when is $x^2 + x + 1$ not a prime?
I am especially interested in an example that is not prime or even better, an explanation why the frequency of such primes goes down as $x$ gets larger.

Suppose $x^2 + x + 1$ is a prime $p$ other than $p = 3$. Then $4p - 3$ is a square; e.g., for $p = 31$, $4p - 3 = 124 - 3 = (11)(11)$. Conversely if  $4p - 3$ is a square for $p$ a prime, there is a divisor $x$ of $p - 1$ such that $p = x^2 + x + 1$. The complement of $x$, $\frac{p - 1}{x}$, is $x + 1$. With $p = 31$, $x = 5$ and $\frac{p - 1}{x} = 6$. Notice that since $x(x + 1) = p - 1$, $x$ cannot be congruent to 1 mod 3, unless $p = 3$. Thus, an answer is that $x^2 + x + 1$ is not a prime exactly when $4(x^2 + x + 1) - 3$ is not a square.
