Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 7 down vote accepted

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.

share|cite|improve this answer

This is not known.

Dirichlet proved it for the linear polynomials.

There is a related conjecture:

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.