# How to demonstrate that there is no all-prime generating polynomial with rational cofficents?

It seems like there is no polynomial with finite variables known, which could generate all prime numbers, by integer assignments. Is there a proof that such polynomial can not exist and does anyone have one in his/her stack?

• You might be interested in: mathworld.wolfram.com/Prime-GeneratingPolynomial.html – Amzoti Sep 10 '12 at 22:28
• It is confusing to ask one question in the title and a different question in the body (in the body you don't specify what the coefficients should be). The body of the question should be self-contained (I usually don't go back up to the title to see if there's any extra information there and I'm sure I'm not the only one). – Qiaochu Yuan Sep 11 '12 at 3:34
• There is a polynomial $f(p,x_1,\ldots,x_n)$ with coefficients in $\mathbb Z$ such that $p$ is a positive prime number if an only if $\exists x_1\in\mathbb Z\ \cdots\ \exists x_n\in\mathbb Z\ f(p,x_1,\ldots,x_n)=0$. If I recall correctly it can be done with $\deg f=4$ and $n=14$. ${}\qquad{}$ – Michael Hardy Aug 9 '14 at 12:44
• – Watson Oct 24 '16 at 7:45

In fact there does not even exist a non-constant polynomial $f$ (I assume you want integer coefficients) which only takes prime values with integer inputs. It suffices to prove this for polynomials in one variable. By the hypothesis that $f$ is non-constant, it takes arbitrarily large values, so without loss of generality $|f(0)| > 1$; in particular, $f(0)$ is divisible by some prime $p$. Then $f(kp)$ is always divisible by $p$, hence cannot be prime for sufficiently large $k$.
• The question asked for rational coefficients, and the argument fails in this case. For example, $f(x)=(x^2+x+4)/2$ is integer-valued with rational coefficients, and $f(0)=2$ is divisible by the prime, 2, but $f(2)=5$ is not divisible by 2. – Gerry Myerson Sep 11 '12 at 3:16
• @Gerry: oh, I see; rational is specified in the title. That's confusing. In any case, rational coefficients is not a problem: just ensure in addition that $k$ is divisible by the least common denominator of the coefficients. In your example, $f(4)$ is divisible by $2$. – Qiaochu Yuan Sep 11 '12 at 3:33
An all prime-generating polynomial with rational coefficients can be built. The point the degree will be infinity, because each time we add a prime we increase the degree. In the picture there are some examples for x>1 