Consider a non constant polynomial $P\in\mathbb{Z}[X]$ sending prime numbers to prime numbers. I encountered on the web two different proofs that $P$ is the identity polynomial, one on mathoverflow here and another one (somehow stated in more elementary words) there. The point is : both proof use the Dirichlet progression Theorem and I am wondering if there is any way to prove this fact without the use of such a deep result. As a matter a fact, it seems that the second proof only uses that

There exists only a finite number of pair of distinct primes $(p,q)$ such that $p +\mathbb{N} q$ contains a finite number of primes.

Using the Dirichlet progression Theorem, the finite number of the previous statement is zero, of course. But is there any (if possible elementary) argument to prove the above result ?

Thanks for any help.

Edit : I did not manage to find any more elementary proof to characterize those integers polynomials sending primes to primes. However (for what it worth) I give below an elementary proof of a different (related) result. It is possible that a simpler proof exists, would be happy to read it. Denote by $\mathscr{P}$ the set of all prime numbers.

If $P\in\mathbb{Z}[X]$ satisfies $P(\mathscr{P}) = \mathscr{P}$, then $P(X)=\pm X$.

The case $\deg(P)=1$ is easily handled, so that we just have to prove that $\deg(P)>1$ is impossible. Note that if $P(\mathscr{P}) = \mathscr{P}$, then for all $n\in\mathbb{N}^*$ we have also $P_n(\mathscr{P}) = \mathscr{P}$, where $P_n = P\circ \cdots \circ P$ is the $n$-th iterate of $P$. In particular, for al $(p,n)\in\mathscr{P}\times\mathbb{N}$ there exists $q_n\in\mathscr{P}$ such that $P_n(q_n) = p$. Since $\deg(P_n)>\deg(P)>1$ the (discrete) sequence $(q_n)_n$ is bounded, thus taking a certain value $q_p\in\mathscr{P}$ infinitely many times, *i.e.* the equation $P_n(q_p)=p$ holds for an infinity of natural integers. If $(p_k)_k$ is an enumeration of $\mathscr{P}$, one can thus produce a diagonal extraction $\varphi:\mathbb{N}\rightarrow \mathbb{N}$ such that $P_{\varphi(n)}(q_p)=p$ holds for all $(p,n)\in\mathscr{P}\times\mathbb{N}$. But this means that $P_{\varphi(n)}$ and $P_{\varphi(n+1)}$ take the same value on an infinite set (since $p\mapsto q_p$ is obviously injective) : the sequence $P_{\varphi(n)}$ is constant. This contradicts $\deg(P)>1\Rightarrow\deg(P_{n+1})>\deg(P_n)$.

As for the general result, this means that we "just" need to prove that such polynomials are onto ... I also tried to used the iterated polynomials but did not succeed.

dohave an elementary proof: Given $n \in \mathbf N^+$, the infinitude of the primes of the form $nk+1$ is a rather straightforward consequence of Zsigmondy's theorem on primitive divisors (en.wikipedia.org/wiki/Zsigmondy%27s_theorem), while the infinitude of the primes of the form $nk-1$ is a (more complicate) consequence of certain properties of Chebyshev polynomials, though I couldn't trace back a reference for this result (can anyone?). $\endgroup$ – Salvo Tringali Apr 27 '17 at 9:03Infinitely Many Primes in Arithmetic Progressions: The Cyclotomic Polynomial Method[Math. Gaz.86(Mar., 2002), No. 505, 110-114], which is entirely devoted, as the title suggests, to the cyclotomic method. $\endgroup$ – Salvo Tringali Apr 27 '17 at 9:12