Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Your approach does not work, because $f(p)$ may be some prime other than $p$. –  Alex Becker Jun 12 '12 at 16:02
add comment

1 Answer

up vote 11 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.