# Polynomial is prime when evaluated at prime numbers

Let $P(x)$ be a polynomial with integer coefficients such that $P(p)$ is prime for all prime $p$. What are all possible polynomials $P(x)$?

Certainly $P(x)=x$ and $P(x)=p$ with $p$ prime satisfy that condition. Are there others?

• No. There aren't. – Lucian Jan 5 '14 at 12:56
• @Lucian And what's the proof? – Kunal Jan 5 '14 at 15:13
• @Lucian But my question asks for a polynomial which is prime when evaluated at all primes, not when evaluated at all integers. It's significantly different than a prime-generating function. – Kunal Jan 5 '14 at 15:41
• But, kunal, you'd end up with a prime generating function, because repeatedly evaluating the same function on it's resulting value would generate a new prime – camel Jan 5 '14 at 15:48
• No, Kunal, it isn't. Think about it. If such a polynomial were to exist, then, when calculated in a prime, it would return a prime as result, so all we would have to do is to put it on loop, and presto, we have our own little prime-number-machine. – Lucian Jan 5 '14 at 15:53

We will prove that only these 2 cases are possible as you mentioned above.
First of all, if $f(x)$ is a constant polynomial with the above property,then obviously
$f(x)=p$ with $p$ being prime and we are ok.

Suppose now that $a_n\neq 0$ and $f(x)=a_nx^n+\cdots +a_0$ be such a polynomial you are asking.
We have two cases:

1) There is a prime $p$ which is a prime divisor of the polynomial at some value, and $p$ is not a divisor of $a_0$.

Suppose that $f(k)\equiv0$ $\ (modp)$ for a proper integer $k$.

$p$ does not divide $a_0$, so we can easily see that $\gcd(p,k)=1$.
From Dirichlet's theorem we know that exist infinitely many primes of the form $q=k+n\cdot p$.
So,$f(q)=f(k+n\cdot p)\equiv0$$(modp)$ which means that $f(q)=p$ because as you want $f(q)$ must be prime.
But there are infinitely many primes $q$ of the above form ,so $f(x)$ must take the value $p$ infinitelly often which means that $f(x)=p$ for all $x$, which is a contradiction
(because as we assumed $f(x)$ is not constant)

2) Every prime divisor of $f(x)$ is a divisor of $a_0$

We know that every polynomial which is not constant has infinitely many prime divisors,so $a_0$ has infinitely many prime divisors so $a_0=0$.
This means that $x$ is a divisor of $f(x)$ always,which shows us that $f(x)/x$ is an integer and because we want $f(q)=q'$ for primes $q,q'$ then $q=q'$ whenever this happens.
This proves that $f(x)=x$ for every $x$.

If $P$ has integer coefficients with rational roots then it can be written in factored form $P(x)=(k_1 x-\xi_1)\dots(k_n x-\xi_n)$

How do you propose this gives prime numbers for all prime $x$? Given $k_i x-\xi_i$ is always an integer we know that all but one $k_i x-\xi_i$ must be $\pm1$. Is this possible to enforce for all primes $x$ for $n>1$? (it's not -- now show why)

• How would you express $x^2+1$ in this form? – Peter Košinár Jan 5 '14 at 10:23
• @Peter that's a good point :-p – obataku Jan 5 '14 at 10:31
• Also,the question didn't say that the polynomial had rational roots. – Geoff Robinson Jan 5 '14 at 11:41
• @Geoff obviously. If you haven't caught on yet, this is solving a subproblem. I made the additional assumptions I've made very clear – obataku Jan 5 '14 at 16:41