MathOverflow is a question and answer site for professional mathematicians. 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

Along the lines of Polynomial representing all nonnegative integers, but likely well-known question:

is there a polynomial $f \in \mathbb Q[x_1, \dots, x_n]$ such that $f(\mathbb Z\times\mathbb Z\times\dots\times\mathbb Z) = P$, the set of primes?

share|cite|improve this question
up vote 18 down vote accepted

No. Any such polynomial would have the property that any of its restrictions $f(x)$ to one variable consist only of primes, but this is easily seen to be impossible, since if $p(a)$ is prime then $p(k p(a) + a)$ is divisible by $p(a)$. (Even accounting for the coefficients in $\mathbb{Q}$ is straightforward by multiplying by the common denominator and using CRT; in fact, we can show that given an integer polynomial $q(x)$ and a positive integer $n$ there exists $x_n$ such that $q(x_n)$ is divisible by $n$ distinct primes.)

However, there do exist multivariate polynomials with the property that their positive integer outputs consist of the set of primes. See the Wikipedia article.

share|cite|improve this answer
<a href="…; is a reference. It is a consequence of the work of Davis, Putnam, Robinson, and Matiyasevich on Hilbert's 10th problem that the statement about positive integer outputs holds not only for the set of prime numbers, but also for any set of positive integers that can be the output of a computer program. – Bjorn Poonen Dec 27 '09 at 0:38
I believe has references. – Gjergji Zaimi Dec 27 '09 at 0:39
Thanks, wonderful references! @Bjorn, references in comments don't need any tag:… – Ilya Nikokoshev Dec 27 '09 at 0:45

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.