Problem : Find all polynomials $f(x)\in \mathbb{Z}[x]$ such that there exists a natural $N$, such that for any prime $p>N$, $|f(p)|$ is also a prime.
What I found so far : It is obvious that $f(x)$ is irreducible. Few such polynomials are,
- $f(x)\equiv \pm p$ for some prime $p$.
- $f(x)=\pm x$
But after this I am unable to prove or disprove the existent of any other such polynomials.
Best Answer
All constant solutions are among your findings, obviously. So assume $f$ is not constant. If $f$ is a solution, then so is $-f$; hence let us assume $f(x)\to+\infty$ as $x\to+\infty$. We may make $N$ larger such that all (real) roots of $f(x)$ as well as $f'(x)$ are $<N$. Then $f$ is positive and injective on $[N,\infty)$.
If $f(p)=p$ for all primes $p>N$, we must have $f(x)=x$ (because $f(x)-x$ has infinitely many roots), which you already found. So let $p>N$ be a prime with $q=f(p)\ne p$. Note that $f(x)\bmod q$ depends only on $x\bmod q$. Hence for every prime $p'$ with $p'>N$ and $p'\equiv p\pmod q$, we have $q\mid f(p')$, but equality only for $p'=p$. By Dirichlet, infinitely many primes $p'\equiv p\pmod q$ exist (this is where we use $p\ne q$), and some of these infinitely many are $>N$, thus showing $f(p')$ is not prime and $f$ does not have the property.
We conclude that the solutions you found are all solutions.
Alternate, somewhat more direct approach:
Let $f$ and $N$ as in the problem statement. Consider a prime $p>N$ and let $q=|f(p)|$.
If $q\ne p$, they are co-prime and by Dirichlet, there exist infinitely many primes $p'\equiv p\pmod q$. For those (still infinitely many) such $p'$ that are $>N$, we conclude $f(p')\equiv f(p)\equiv 0\pmod q$ and hence $f(p')=\pm q$. Then one of the two polynomials $f(x)-q$, $f(x)+q$ has infinitely many roots, hence is identically $0$, and ultimately $$ f(x)=\pm q.$$ Remains the case that $|f(p)|=p$ for all primes $p>N$. Then one of the two polynomials $f(x)-x$, $f(x)+x$ has infinitely many roots, hence is identically $0$, and ultimately $$ f(x)=\pm x.$$