Suppose that $f$ is a polynomial with integer coefficients with the property that for any prime $p$, $f(p)$ is a prime. Is there any such polynomial $f$ other than $f(x)=x$ of course?

My approach was that if the leading coefficient $a_{0}$ of $f$ is $0$, then $f(p)=p$ for any prime $p$, so $f(x)-x$ has infinite roots $\implies f(x)=x$. If $\deg{f}=n$ and if $a_{0}$ has $\gt n$ prime factors, then also, the same argument works - but I couldn't complete my argument.

Any help will be greatly appreciated!

  • $\begingroup$ Your approach does not work, because $f(p)$ may be some prime other than $p$. $\endgroup$ – Alex Becker Jun 12 '12 at 16:02

The constant functions $f(x)=p$, where $p$ is prime, have the desired property, as does the function $f(x)=x$. To show there are no others, suppose that $f$ has positive degree. Suppose also that for some prime $p$, we have $f(p)=q$, where $q$ is a prime different from $p$. (If $f(p)=p$ for all primes $p$, then $f(x)=x$, since a non-zero polynomial of degree $m$ cannot have more than $m$ zeros.)

Then $f(p+nq)\equiv 0 \pmod{q}$ for every integer $n$. But by Dirichlet's Theorem, there are infinitely many primes in the arithmetic progression $p, p+q, p+2q, \dots$. If $p^\ast$ is a large enough such prime, then $f(p^\ast)$ is larger than $q$, but divisible by $q$, and therefore not prime.

  • $\begingroup$ Thanks Andre Nicolas. And as for Alex' comment, if the leading coefficient is 0, then f(p) is divisible by p and is a prime, so f(p)=p. Anyway, is there a simpler solution that does not use the Dirichlet theorem? $\endgroup$ – Somabha Mukherjee Jun 12 '12 at 16:36
  • $\begingroup$ @SomabhaMukherjee: Your argument works nicely for polynomials with no constant term. I do not have an elementary argument in general. $\endgroup$ – André Nicolas Jun 12 '12 at 16:40
  • $\begingroup$ @AndréNicolas : +1, really an elegant answer I ever saw. $\endgroup$ – IDOK Jun 14 '12 at 17:34

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.