Is $n^2 + n + 1$ prime for all n? 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?

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!
