6
$\begingroup$

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!

  • 0
    Your approach does not work, because $f(p)$ may be some prime other than $p$.2012-06-12

1 Answers 1

12

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.

  • 0
    @AndréNicolas : +1, really an elegant answer I ever saw.2012-06-14