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?

  • 1
    $\begingroup$ No. There aren't. $\endgroup$ – Lucian Jan 5 '14 at 12:56
  • 1
    $\begingroup$ @Lucian And what's the proof? $\endgroup$ – Kunal Jan 5 '14 at 15:13
  • 3
    $\begingroup$ @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. $\endgroup$ – Kunal Jan 5 '14 at 15:41
  • 1
    $\begingroup$ 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 $\endgroup$ – camel Jan 5 '14 at 15:48
  • 1
    $\begingroup$ 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. $\endgroup$ – 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)

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

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.