# Is it possible for a polynomial to be integer-valued only for prime inputs?

Could one write a polynomial that produces an integer output only for prime number inputs?

I know that if a polynomial of degree $n$ takes integer values at $n+1$ consecutive integer arguments, then it takes integer values at all integer arguments. However, since the prime number inputs aren't consecutive, then how would one go about proving it would be possible to write?

• Assuming you mean “exactly” rather than “only”, one way to see this is impossible is to note that the set of values at which a (rational) polynomial produces integers is a finite union of infinite arithmetic progressions, but the primes don’t contain any infinite AP. One could use a polynomial with irrational coefficients to produce a finite number of prescribed integer outputs, but the primes are not finite either :). – Erick Wong Jan 2 '18 at 18:30
• I like this way of thinking about the polynomials, but what do you mean by "a finite union of infinite arithmetic progressions"? Could you clarify a bit more on what that constitutes? – Ali Jan 2 '18 at 19:12
• To be more specific, it will consist of a set of residue classes modulo a single integer $N$ which depends on the coefficients of the polynomial. In other words $f(n)$ is an integer iff $n$ is congruent to $a_1, a_2, \ldots, a_k$ modulo $N$. Simple example: $(n-1)/2$ is an integer exactly when $n$ is odd. – Erick Wong Jan 2 '18 at 20:01
• This is not an answer to what you asked, but you might be interested in polynomials whose positive values on nonnegative integers are precisely the primes, as discussed at primes.utm.edu/glossary/xpage/MatijasevicPoly.html – Mark S. Jan 3 '18 at 0:22

## 2 Answers

No. Suppose there is such a polynomial $f(x)$ of degree $k$, say. First off, this polynomial has to have rational coefficients (by Lagrange interpolation, say). Let $N$ be the least common denominator of the coefficients. Then $g(x)=Nf(x)$ is a polynomial with integer coefficients and $g(2)$ is divisible by $N$. But $g(2-N)\equiv g(2)\equiv 0\pmod N$, so $g(2-N)$ is divisible by $N$, hence $f(2-N)$ is an integer. But clearly $2-N$ is not a prime, so we get a contradiction.

Edit: for the sake of clarifying, here is how I have interpreted the question: is there a polynomial $f$ such that, for $n\in\mathbb Z$, $f(n)$ is an integer iff $n$ is prime? I show that there is no such polynomial.

Edit 2: (in reply to Yves Daoust) Suppose that $f$ is a polynomial of degree $k$ which takes integer value at every prime. Pick any primes $p_1,\dots,p_{k+1}$. Consider polynomial $L(x)$ defined here for $x_i=p_i,y_i=f(p_i)$. Since every $\ell_i$ is a polynomial with rational coefficients of degree at most $k$, the same holds for $L$.

Now note $f-L$ is a polynomial of degree at most $k$ which is zero at at least $k+1$ points $p_1,\dots,p_{k+1}$, hence it must be a zero polynomial. Thus $f=L$ has rational coefficients.

• How do you justify "this polynomial has to have rational coefficients" ? – Yves Daoust Jan 3 '18 at 2:02
• How do you justify 'clearly $2-N$ is not a prime'? – Steven Stadnicki Jan 3 '18 at 3:26
• @StevenStadnicki This follows from the little-known fact that $2$ is the least prime, together with $N>0$. – Wojowu Jan 3 '18 at 10:06
• @YvesDaoust I admit right here a more detailed explanation could be helpful. The idea here is, interpreting the question as asking for the polynomial to be integer at all primes, doing Lagrange interpolation through the points $(p_1,f(p_1)),\dots,(p_{k+1},f(p_{k+1}))$ gives a rational polynomial which agrees with $f$ at $k+1$ points, so they must be equal. – Wojowu Jan 3 '18 at 10:12
• Even if you allow for negative numbers to be prime, you could just take $2 + 2N$ instead of $2 - N$. – Alex Zorn Jan 3 '18 at 21:02

Yes.

All polynomials of the form

$$Q(x)+\sqrt2\prod_{k=1}^n(x-p_k)$$ where $Q$ is a polynomial of integer coefficients, are integer only at the primes $p_k$.

Addendum:

The interpretation of the question as "the only integer values of the polynomial over $\mathbb R$ occur at primes" wouldn't make sense as for sufficiently large $n$, the slope of any polynomial exceeds $1$ and the integer values occur at arguments closer than $1$.

• Interesting, I think these two answers (“No” and “Yes”) point to an ambiguity in the question, which is that when it says “integer output only for prime number inputs”, it's not clear whether the question means (only) that "whenever $p(x)$ is an integer, $x$ is prime” (the “yes” above), or whether it also additionally means “whenever $x$ is a prime, $p(x)$ is an integer”. (I think the question intended the latter and that is also the first comment on the question: Assuming you mean “exactly” rather than “only”…. So this answers the question literally asked, but not the one likely intended.) – ShreevatsaR Jan 2 '18 at 20:17
• @ShreevatsaR Without that restriction, the question becomes trivial. p(x) = pi satisfies the condition "whenever p(x) is an integer, x is prime” – Acccumulation Jan 2 '18 at 20:47
• I think this answer isn't even correct. E.g. consider $Q(x) = 0$ and $p_1 = 2$ (and no other primes). Then this answer suggests the polynomial $f(x) = \sqrt{2}(x-2)$, which should produce integer values only for $x = 2$. But that's not true: this polynomial also produces integer values for say $x = 2 + \sqrt{2}$. But then that raises the question of whether the question meant to consider only integer $x$… – ShreevatsaR Jan 2 '18 at 22:54
• @ShreevatsaR Clearly any non-constant polynomial will assume infinitely many integer values (an unbounded continuous real function) if the "input" is allowed to be any kind of real number. Those values include all integers (prime and composite) above (or below) a certain threshold. – Jeppe Stig Nielsen Jan 2 '18 at 23:45