Aucun polynôme ne fabrique que des nombres premiers

La stratégie. Un polynôme à coefficients entiers respecte les congruences : c'est le a), et c'est tout. Si $P(a)=p$ est premier, alors $P(a+kp)$ est un multiple de $p$ pour tout $k$ — et un multiple de $p$ qui est premier vaut $p$. Un polynôme non constant ne peut pas prendre la même valeur une infinité de fois.

a) Un polynôme respecte les congruences. Écrivons $P={\sum }_{i=0}^d{c}_i{X}^i$ avec $c_i\in \mathbb{Z}$. On a $a+km\equiv a[m]$ (car $m$ divise $(a+km)-a=km$). Les congruences sont compatibles avec les puissances : $(a+km{)}^i\equiv a^i[m]$ pour tout $i$ ; avec les produits par un entier : $c_i(a+km{)}^i\equiv c_i{a}^i[m]$ ; et avec les sommes : $\sum c_i(a+km{)}^i\equiv \sum c_i{a}^i[m]$. C'est exactement $P(a+km)\equiv P(a)[m]$.

b) L'impossibilité. Supposons, par l'absurde, que $P$ soit non constant à coefficients entiers et que $P(n)$ soit premier pour tout $n\in \mathbb{N}$. Posons $p=P(0)$, qui est premier, donc $p\ge 2$. Par le a) avec $a=0$ et $m=p$ : pour tout $k\in \mathbb{N}$, $P(kp)\equiv P(0)=p\equiv 0[p]$, donc $p$ divise $P(kp)$. Mais $P(kp)$ est premier par hypothèse, et un nombre premier divisible par $p\ge 2$ est égal à $p$ : $P(kp)=p$ pour tout $k\in \mathbb{N}$.

Le polynôme $P$ prend donc la valeur $p$ en tous les entiers $0,p,2p,3p,\dots$ Or un polynôme non constant à coefficients réels tend vers $+\infty$ ou vers $-\infty$ quand la variable tend vers $+\infty$ (son terme dominant l'emporte) ; en particulier $|P(x)|>p$ pour $x$ assez grand, ce qui contredit $P(kp)=p$ pour $k$ arbitrairement grand. Aucun polynôme non constant à coefficients entiers ne prend que des valeurs premières sur $\mathbb{N}$. (On peut aussi conclure par le chapitre sur les polynômes : $P-p$ aurait une infinité de racines, donc serait nul.)

Le point délicat. Le raisonnement n'utilise pas que $P(n)$ soit premier pour tout $n$ : il suffit qu'il le soit aux multiples d'un seul $p=P(a)$. Et il n'exclut pas qu'un polynôme produise beaucoup de nombres premiers — seulement qu'il n'en produise que.

c) Le polynôme d'Euler. Pour $P(n)=n^2+n+41$ : $P(0)=41$, $P(1)=43$, $P(2)=47$, $P(3)=53$, quatre nombres premiers, et de fait $P(n)$ est premier pour tout $n\le 39$ — quarante valeurs premières consécutives. Par le a) avec $a=0$ et $m=41$ : $P(41k)\equiv 41\equiv 0[41]$. Ainsi $P(41)=41^2+41+41=41\times 43=1763$ est composé. (La chute survient même un cran plus tôt : $P(40)=1600+40+41=1681=41^2$, car $40\equiv -1[41]$ et $P(-1)=41$.)

Ce que l'exercice installe. La compatibilité des congruences avec les opérations est une propriété des polynômes : $a\equiv b[m]$ entraîne $P(a)\equiv P(b)[m]$ dès que $P$ est à coefficients entiers. C'est ce qui permet de réduire modulo $m$ avant d'évaluer, et c'est le principe de tous les critères de divisibilité. Le chapitre sur les polynômes reprendra cette idée en réduisant les coefficients eux-mêmes.