# Proof of no prime-representing polynomial in 2 variables

In "The New Book of Prime Number Records", Ribenboim reviews the known results on the degree and number of variables of prime-representing polynomials (those are polynomials such that the set of positive values they obtain for nonnegative integral values of the variables coincides with the set of primes). For example, it is known that there is such a polynomial with 42 variables and degree 5, as well as one with 10 variables and astronomical degree.

Ribenboim mentions that it's an open problem to determine the least number of variables possible for such a polynomial, and remarks "it cannot be 2". It's a fairly simple exercise to show that it cannot be 1, but why can't it be 2?

EDIT: here's the relevant excerpt from Ribenboim's book. Given that nobody seems to be familiar with such a proof, I'm inclined to assume that this is a typo and he just meant "it cannot be 1".

• You mean "the set of positive values that they obtain for non-negative values of the inputs coincides with the set of prime numbers". Otherwise I can suggest $-1$, $2 - 3x^2$ and so on. Aug 26, 2011 at 10:02
• There actually is a polynomial $f(p,x_1,\ldots,x_n)$ with integer coefficients such that $p$ is a positive prime if and only if $\exists x_1,\ldots,x_n\in \mathbb{Z}\ f(p,x_1,\ldots,x_n) = 0$. I think it's a 4th-degree polynomial in 14 variables or something like that. (But ignore this comment, unless you don't ignore it.) Aug 26, 2011 at 18:17