Polynomial is prime when evaluated at prime numbers 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?
 A: 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$.
A: 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)
