4
$\begingroup$

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?

  • 0
    You might be interested in: http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html2012-09-10
  • 2
    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).2012-09-11
  • 0
    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{}$2014-08-09
  • 0
    Related: https://math.stackexchange.com/questions/59846/proof-of-no-prime-representing-polynomial-in-2-variables2016-10-24

2 Answers 2

6

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.

  • 0
    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.2012-09-11
  • 1
    @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$.2012-09-11
-3

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

  • 0
    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.2014-08-10