# How often must an irreducible polynomial take a prime value?

Suppose $f(x)$ is an irreducible polynomial over $\mathbb Z$ of degree $n$. Is it always the case that there exist distinct $x_1,\ldots,x_{2n+1}\in \mathbb Z$ such that $f(x_1),\ldots,f(x_{2n+1})$ are all prime?

So far I've tested a few irreducible polynomials using mathematica, and this has held. The motivation is to use this as a test for irreducibility, as if $f(x)$ is not irreducible then it takes on at most $2n$ prime values, as either factor takes on $1$ or $-1$ at most $2n$ times. (I'd also be interested in learning if this bound can be improved).

This could potentially be expended to other rings of integers, i.e. $\mathbb Z[i]$, but in that case the minimal number of primes needed to certify that $f(x)$ is irreducible would increase as more units appear.

-
There is a divisibility condition you need to rule out, as Hurkyl's answer shows. Other than that, whether there are infinitely many $x_i$ is not known for any $f$ with $n \ge 2$, and actually I think the easier question of whether there is at least one $x_i$ is probably also not known in general. – Qiaochu Yuan Mar 22 '13 at 4:52

The values of the polynomial

$$x^2 + x + 4 = \left(x + \frac{1}{2} \right)^2 + \frac{15}{4}$$

are always divisible by $2$ and always greater than $2$, and thus are never prime.

-

This is not known.

Dirichlet proved it for the linear polynomials.

There is a related conjecture: http://en.wikipedia.org/wiki/Schinzel%27s_hypothesis_H

-

Also $x^4+1 = (x^2+\sqrt{2}x+1)(x^2-\sqrt{2}x+1)$. For every prime, one of $-1 , \pm 2$ must be a quadratic residue.

-