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

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?

share|cite|improve this question
You might be interested in: – 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
up vote 6 down vote accepted

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$.

However, remarkably there do exist polynomials in more than one variable all of whose positive values are prime.

share|cite|improve this answer
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 Picture prime generating Polynomail

share|cite|improve this answer
Consider your answer to format properly in math mode for better readability. Also please refrain from adding "Best regards" and your name (it is posted automatically) at the end. – pushpen.paul Aug 10 '14 at 12:07

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.