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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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