Is $n^2 + n + 1$ prime for all n?

Question

I recently stumbled across this question in a test.

Paul says that "$n^2+n+1$ is prime $\forall\:n\in \mathbb{N}$".

• Paul is correct, because...
• Paul is wrong, because...

The answers sheet says that "all answers providing a valid counterexample, e.g. $n=4$, are valid; however, I'm interested in understanding why - is there some sort of theorem which can predict whether a polynomial is prime or not?

What I tried was:

$n^2+n+1$ can be factorized as $(n+\frac{1+\sqrt{3}i}{2})(n+\frac{1-\sqrt{3}i}{2})$. Neither of these factors is a suitable factor (i.e. is natural, different from $1$, and different from $n^2+n+1$) for any $n\in\mathbb{N}$, therefore $n^2+n+1$ must be prime $\forall\:n\in\mathbb{N}$.
Instead, $n^2-1$ can be factorized as $(n+1)(n-1)$. The factor $(n+1)$ is a suitable factor (i.e. natural, different from $1$, and different from $n^2-1$) for $n>2$; therefore, $n^2-1$ is not prime for $n>2$.

However, the above reasoning is clearly wrong, because "$n^2+n+1$ is prime $\forall\:n\in\mathbb{N}$" doesn't hold for the case $n=4$.
What is wrong in the reasoning? Can one tell whether a polynomial $p(n)$ is prime for all $n$ a priori?

Answer 1

Hint $\ \ f(1)=3\,\Rightarrow\, 3\mid f(1\!+\!3n),\ $ e.g. $\,3\mid f(4)=21$

Remark $\ $ Above we used the Polynomial Congruence Theorem

$\ {\rm mod}\ 3\!:\ \color{}{1\!+\!3n\equiv 1}\,\Rightarrow\, f(\color{}{1\!+\!3n})\equiv f(\color{}1)\equiv 0,\ $ for all $\,f\in\Bbb Z[x]$

Alternatively $\,\ 3n\mid f(1\!+\!3n)-f(1)\ $ by the Factor Theorem $\,x-y\mid f(x)-f(y)$

The idea generalizes to a proof that any nonconstant polynomial $\in\Bbb Z[x]\,$ has a non-prime value.

Answer 2

Just because a polynomial $f$ doesn't factor doesn't mean that the number $f(m)$ you get when evaluating $f$ at a number $m$ doesn't factor. The simplest example is something like $f(x) = x+1$. This polynomial is irreducible, hence doesn't factor, but $f(3) = 4$ is clearly composite.

Here is a link showing that no polynomial with integer coefficients can evaluate to primes for all integers.

Answer 3

You want to disprove a statement of the form $\forall n\colon f(n)\text{ is prime}$, that is you want to prove $\neg\forall n\colon f(n)\text{ is prime}$, which is equivalent to $\exists n\colon \neg(f(n)\text{ is prime})$. Therefore, a counterexample is often the easiest and most straightforward way to disprove a general statement. In fact, any proof that merely shows that a $\forall$ statement is wrong without constructing a counterexample (or essentially doing so, but leaving out the details) is frowned upon by some mathematicians as being non-constructive. That being said, maybe you'd like a proof that there is no polynomial $f$ such that $f(n)$ is prime for all $n\in \mathbb N$ (except constant polynomials):

Let $$f(n)=a_dx^d+a_{d-1}x^{d-1}+\ldots+a_1x+a_0$$ be a polynomial of degree $d\ge 1$ with coefficients $a_i\in\mathbb C$, $0\le i\le d$, and $a_d\ne 0$. First we observe tat in fact $a_i\in \mathbb Q$ for all $i$: By plugging in $x=1, 2, \ldots, d+1$, we obtain $d+1$ rational equations in the unknowns $a_i$. Since the powers of $x$ are linearly independant (or look up Vandermonde matrix), there exists a unique solution, which must be rational. Then there exists $M\in\mathbb N$ sich that $a_iM\in\mathbb Z$ for all $i$. By assumption, $Mf(n)$ is $M$ times a prime for all $n\in\mathbb N$. For each prime $p$, there are at most $d$ values of $n$ such that $f(n)=p$. Since $M$ has only finitely many prime factors, $f(n)\mid M$ for only finitely many $n$. Therefore there exists $n$ such that $p:=f(n)\not\mid M$. By reducing $Mf(X)$ modulo $p$, we see that $Mf(n+kp)\equiv 0\pmod p$ for all $k\in\mathbb Z$. This implies that the prime $f(n+kp)$ is $p$ for all $k$. Especially, there are more than $d$ values of $n$ for which $f(n)=p$, contradiction. $_\square$

---

Trivia remark: On the other hand, there exists a polynomial in several variables with the property that its values are either negative or prime, and all primes occur!

Answer 4

No. For $n=43$, $n^2+n+1=1893$ which is divisible by $3$.

Answer 5

Modulo 3, that polynomial is equivalent to some well known polynomial $(n-1)^2$ $$(n-1)^2=n^2-2n+1\equiv n^2+n+1 [3]$$

Hence if $n=1+3k$ for any $k$ (so each time $n-1\equiv 0[3]$) then $n^2+n+1$ will have 3 as a divisor.