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*?