# Polynomial representing prime numbers

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?

-

## 1 Answer

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.

-
<a href="mathdl.maa.org/images/upload_library/22/Ford/…; 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 mathworld.wolfram.com/Prime-GeneratingPolynomial.html has references. –  Gjergji Zaimi Dec 27 '09 at 0:39
Thanks, wonderful references! @Bjorn, references in comments don't need any tag: mathdl.maa.org/images/upload_library/22/Ford/… –  Ilya Nikokoshev Dec 27 '09 at 0:45