If $x \not \equiv 1 \pmod 3$, when is $x^2 + x +1$ not a prime?

Question

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.

Answer 1

Let $f(x)=x^2+x+1$.

• You see that $f(2)=7$. This implies that $f(n)$ is divisible by $7$ whenever $n\equiv2\pmod7$. This is basic congruence algebra - leaving the proof as an exercise. Anyway, we know that $f(9)=91$ and $f(16)=273$ et cetera cannot be primes, because they are divisible by seven.
• Similarly $f(3)=13$ implies that $f(n)$ is divisible by $13$ whenever $n\equiv3\pmod{13}$, and $f(n)$ is divisible by $31$ whenever $n\equiv5\pmod{31}$.

We can continue the above list. It is just showcasing the mechanism that prevents any polynomial with integer coefficients from producing only primes as its values.

---

A different way of looking at this is via quadratic reciprocity. The discriminant of $f(x)$ is $D=-3$. The law of quadratic reciprocity reveals that $-3$ is a quadratic residue modulo a prime $p>3$, iff $p\equiv1\pmod3$. So we can find an integer $n$ in the range $0<n<p$ such that $f(n)$ is a multiple of $p$ (possibly equal to $p$). Then $f(n+kp)$ will be a bigger multiple of $p$ for any $k>0$, and hence not a prime.

Answer 2

As you pass the prime squares as in the result values, more and more primes can be involved in any possible composite result.

The first two composite values of $91 = 7 \cdot 13$ and $133 = 7 \cdot 19$ show that when $x \equiv \{2, 4 \} \bmod 7$ you will get a result divisible by $7$.

Answer 3

if $$x\equiv 0\mod 3$$ we can set $$x=3m$$ plugging this in your term we get $$9m^2+3m+1$$ and this is not a prime for $$m=6$$, we get $$343=7^3$$ if $$x\equiv 2\mod 3$$ we can set $$x=3m+2$$ and our term is $$9m^2+15m+7$$ and this is surely not prime if $$m=7$$

Answer 4

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.