# A “prime-mapping” polynomial

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!

-
Your approach does not work, because $f(p)$ may be some prime other than $p$. –  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.

-
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? –  Somabha Mukherjee Jun 12 '12 at 16:36
@SomabhaMukherjee: Your argument works nicely for polynomials with no constant term. I do not have an elementary argument in general. –  André Nicolas Jun 12 '12 at 16:40
@AndréNicolas : +1, really an elegant answer I ever saw. –  Iyengar Jun 14 '12 at 17:34