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?

  • $\begingroup$ You might be interested in: mathworld.wolfram.com/Prime-GeneratingPolynomial.html $\endgroup$ – Amzoti Sep 10 '12 at 22:28
  • 2
    $\begingroup$ 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). $\endgroup$ – Qiaochu Yuan Sep 11 '12 at 3:34
  • $\begingroup$ 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{}$ $\endgroup$ – Michael Hardy Aug 9 '14 at 12:44
  • $\begingroup$ Related: math.stackexchange.com/questions/59846/… $\endgroup$ – 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$.

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

  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Sep 11 '12 at 3:16
  • 1
    $\begingroup$ @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$. $\endgroup$ – 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

  • $\begingroup$ 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. $\endgroup$ – pushpen.paul Aug 10 '14 at 12:07

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.