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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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$.
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)