# Théorème de la progression arithmétique

En mathématiques, et plus précisément en théorie des nombres, le théorème de la progression arithmétique, s'énonce de la façon suivante :
   Pour tout entier n non nul et tout entier m premier avec n, il existe une infinité de nombres premiers congrus à m modulo n (c'est-à-dire de la forme m + an avec a entier).
Ce théorème est une généralisation du théorème d'Euclide sur les nombres premiers. Sa première démonstration, due au mathématicien allemand Gustav Lejeune Dirichlet en 1838, fait appel aux résultats de l'arithmétique modulaire et à ceux de la théorie analytique des nombres. La première démonstration « élémentaire » est due à Atle Selberg en 1949.

## Signification et prolongements du théorème

Ce théorème généralise celui d'Euclide, d'après lequel il existe une infinité de nombres premiers et qui correspond donc au cas où la raison n de la progression arithmétique est égale à 1. Il indique que si l'on construit un tableau comme le suivant (qui correspond au cas n = 9 : c'est le nombre qui figure dans la première ligne et deuxième colonne), alors :
* certaines lignes possèderont au plus un nombre premier (indiqué en rouge sur la figure) et il sera, s'il existe, toujours en première colonne. Cette configuration se présente ici pour les lignes commençant par 0, 3 et 6 ;
* les autres contiendront toujours une infinité de nombres premiers. Ces lignes sont celles qui commencent par un entier compris entre 0 et n – 1 et premier avec n (ici : 1, 2, 4, 5, 7 ou 8) ; il y en a donc φ(n), où φ est l'indicatrice d'Euler.
On peut aller plus loin. La répartition statistique est presque la même dans chaque ligne. Et plus la ligne est longue, plus les répartitions statistiques se ressemblent, pour devenir exactement les mêmes. Vu sous cet angle, les nombres premiers sont remarquablement bien ordonnés. Ce résultat est démontré par le théorème de densité de Chebotarev, une généralisation du travail de Dirichlet. Dans l'exemple cité, les lignes commençant avec un entier premier avec 9 en contiennent entre 7 et 5, soit une variation inférieure à 40 %. En revanche, si le tableau est prolongé jusqu'à la valeur 1 000, alors le nombre de nombres premiers dans les lignes en contenant une infinité ne varie plus que de 26 à 29, soit une variation de moins de 10 %.
Une autre analyse est réalisée sur l'apparition du premier nombre premier dans une ligne ; elle est l'objet du théorème de Linnik.
| 0 | 9 | 18 | 27 | 36 | 45 | 54 | 63 | 72 | 81 | 90 | 99 | 108 | 117 | 126 | 135 | 144 |
| 1 | 10 | 19 | 28 | 37 | 46 | 55 | 64 | 73 | 82 | 91 | 100 | 109 | 118 | 127 | 136 | 145 |
| 2 | 11 | 20 | 29 | 38 | 47 | 56 | 65 | 74 | 83 | 92 | 101 | 110 | 119 | 128 | 137 | 146 |
| 3 | 12 | 21 | 30 | 39 | 48 | 57 | 66 | 75 | 84 | 93 | 102 | 111 | 120 | 129 | 138 | 147 |
| 4 | 13 | 22 | 31 | 40 | 49 | 58 | 67 | 76 | 85 | 94 | 103 | 112 | 121 | 130 | 139 | 148 |
| 5 | 14 | 23 | 32 | 41 | 50 | 59 | 68 | 77 | 86 | 95 | 104 | 113 | 122 | 131 | 140 | 149 |
| 6 | 15 | 24 | 33 | 42 | 51 | 60 | 69 | 78 | 87 | 96 | 105 | 114 | 123 | 132 | 141 | 150 |
| 7 | 16 | 25 | 34 | 43 | 52 | 61 | 70 | 79 | 88 | 97 | 106 | 115 | 124 | 133 | 142 | 151 |
| 8 | 17 | 26 | 35 | 44 | 53 | 62 | 71 | 80 | 89 | 98 | 107 | 116 | 125 | 134 | 143 | 152 |

## Histoire
### De l'Antiquité au XVIIe siècle

L'intérêt pour les nombres premiers est ancien et omniprésent dans l'histoire des mathématiques. Euclide (vers -325-vers -265) y consacre le livre VII de ses Éléments. On peut aussi citer les travaux de Sun Zi, établissant vers l'an 300, dans son manuel Sunzi Suanjing, une première version du théorème des restes chinois et surtout Qin Jiushao qui, dans son Traité mathématique en neuf sections (1247), en développe une version suffisamment sophistiquée pour dépasser le niveau européen du XVIIIe siècle. George Sarton le considère comme l'un des plus grands mathématiciens de tous les temps.
Le XVIIe siècle est celui où les mathématiques européennes, et particulièrement françaises, se réapproprient le savoir de l'Antiquité et l'apport de la civilisation islamique. En 1621, Claude-Gaspard Bachet de Méziriac traduit en latin les Arithmétiques de Diophante d'Alexandrie (env. 200/214 - env. 284/298). Pierre de Fermat (1601-1665) l'annote.

### Vers une formalisation

Au XVIIIe siècle, Leonhard Euler résout plusieurs équations diophantiennes laissées ouvertes par le siècle précédent. On peut citer ses travaux sur le théorème des deux carrés de Fermat ou son attaque du « dernier théorème de Fermat » pour le cas n = 3. Dans ce domaine, il se montre particulièrement adroit en résolvant pour la première fois des problèmes ouverts depuis parfois plus d'un siècle.
En 1735, à la suite d'une étude pour la résolution du problème de Mengoli, Euler étudie des produits infinis. Deux ans plus tard, il utilise une étrange formule maintenant nommée produit eulérien. Son écriture en série est celle de la fonction ζ de Riemann. Elle offre la première information statistique sur la distribution des nombres premiers.
En 1775, Euler énonce le théorème pour une suite arithmétique de premier terme 1$^,$$^,$.
Dix ans plus tard, Adrien-Marie Legendre énonce le théorème de la progression arithmétique dans le cas général. Il croit le démontrer en 1808, via un lemme (faux)$^,$ qui affirmait qu'étant donnés deux entiers m et n premiers entre eux, et k nombres premiers impairs ne divisant pas n, il existe au moins un entier j compris (au sens large) entre 1 et p$_k$ (le k-ième nombre premier, à partir de p$_1$ = 2) tel que –m + jn ne soit divisible par aucun de ces k nombres premiers.
En 1801, Carl Friedrich Gauss publie ses célèbres Disquisitiones arithmeticae. Il offre les bases d'une théorie algébrique des nombres, que l'on appelle arithmétique modulaire. Son livre analyse les propriétés de ℤ/nℤ et, pour démontrer la loi de réciprocité quadratique, développe un cas particulier de caractère d'un groupe fini : le symbole de Legendre.

### Apports de Dirichlet

En 1837, Dirichlet démontre une première version de son théorème de la progression arithmétique, en supposant que n est premier. Il démontre l'année suivante le cas où n n'est pas premier et en 1841, généralise la démonstration aux entiers de Gauss.
La démonstration est d'un intérêt considérable en arithmétique. Elle relie la nouvelle théorie de Gauss aux idées, apparemment si éloignées, d'Euler. Il enrichit de plus chacune des deux branches.
L'apport algébrique pour la théorie des nombres consiste essentiellement dans le développement de l'analyse harmonique. Dirichlet a travaillé sur les découvertes de Joseph Fourier (1768-1830). Pour la démonstration de son théorème, il utilise les mêmes méthodes, cette fois pour un groupe abélien fini. Jacobi dit de lui : « En appliquant les séries de Fourier à la théorie des nombres, Dirichlet a récemment trouvé des résultats atteignant les sommets de la perspicacité humaine ». La théorie des caractères d'un groupe fini pour le cas abélien est pratiquement complète.
Son apport en analyse est non moins innovateur. À chaque caractère, il associe un produit infini analogue à celui d'Euler. Il montre l'équivalence de ces produits à des séries, maintenant nommé série L de Dirichlet dont un cas particulier est la fonction ζ de Riemann. L'essentiel de la démonstration consiste alors à déterminer si l'unité est oui ou non une racine de ces séries. On reconnait là, l'analogie profonde avec l'hypothèse de Riemann. Cet article marque la naissance d'une nouvelle branche des mathématiques : la théorie analytique des nombres avec ses outils fondamentaux : les produits eulériens, ou les séries L de Dirichlet et son intime relation avec l'arithmétique modulaire.

### Version quantitative

La Vallée Poussin a démontré la version quantitative suivante du théorème, conjecturée par Dirichlet et Legendre. Il s'agit de l'équirépartition, évoquée plus haut, des nombres premiers dans les classes [m] modulo n, pour n non nul et m premiers entre eux :
   Le nombre de nombres premiers inférieurs ou égaux à x, dans la suite m + an, est équivalent à Li(x)/φ(n).
Ce théorème généralise le théorème des nombres premiers (qui correspond au cas n = 1 et m = 0) de la même façon que le théorème de la progression généralise le théorème d'Euclide sur les nombres premiers. En 1949, Atle Selberg a donné simultanément une « preuve élémentaire » (c'est-à-dire n'utilisant pas les méthodes de la théorie analytique des nombres) du théorème de la progression arithmétique et de celui des nombres premiers. En 1998, Ivan Soprunov a redémontré la version quantitative du théorème de la progression arithmétique, en utilisant les idées introduites en 1980 par Donald J. Newman dans sa preuve remarquablement simple du théorème des nombres premiers.
En dépit de ce résultat, on constate (c'est le biais de Tchebychev) que pour les valeurs de m qui ne sont pas des carrés modulo n, ce nombre, souvent noté π(x; n, m), est presque toujours supérieur aux π(x; n, p) où p est un carré modulo n ; ce résultat n'est actuellement démontré que si l'on suppose vraie l'hypothèse de Riemann généralisée.

### Problème connexe

Si on note $P(X)=m+nX$ où m et n sont comme dans l'énoncé, le théorème de la progression arithmétique dit qu'il y a une infinité de nombres premiers dans la suite $P(k)$ lorsque k varie dans $\mathbb {N}$. En particulier, il existe une infinité de nombres premiers p tels que $P(k)$ soit multiple de p pour un certain k, une propriété vraie en général pour tout polynôme non constant à coefficients dans $\mathbb {Z}$, et beaucoup plus simple à démontrer que le théorème de Dirichlet.
On se pose alors la question inverse: un polynôme non constant P à coefficients dans $\mathbb {Z}$ étant donné, est-il possible qu'il existe seulement un nombre fini de nombres premiers p, pour lesquels $P(k)$ ne soit pas multiple de p quel que soit k ?
Il est d'abord évident que si P est de degré 1, c'est-à-dire de la forme $m+nX$ la réponse est affirmative puisque n est inversible modulo p pour tout nombre premier ne divisant pas n.
Par ailleurs, en utilisant la loi de réciprocité quadratique, on peut exhiber certains polynômes de degrés > 1 et réductibles sur $\mathbb {Z} [X]$, tels que pour tout nombre premier p, $P(k)$ soit multiple de p pour un certain k : tel est par exemple le polynôme $(X^{2}-13)(X^{2}-17)(X^{2}-121)$.
La question se pose alors pour les polynômes irréductibles sur $\mathbb {Z} [X]$ et de degrés strictement supérieurs à 1. La réponse négative est fournie par le théorème de densité de Frobenius : Si P est irréductible sur $\mathbb {Z} [X]$ et de degré strictement supérieur à 1, alors il existe une infinité de nombres premiers p pour lesquels $P(k)$ n'a aucune racine modulo p.

## Démonstration

Ici, n désigne un entier strictement positif et m une classe du groupe des unités, noté U, de l'anneau ℤ/nℤ. L'objectif est de montrer que m contient une infinité de nombres premiers. ${\mathcal {P}}$ désigne l'ensemble des nombres premiers et S le demi-plan des complexes de partie réelle strictement supérieure à 1. Si c désigne un nombre complexe, c désigne son conjugué.
Un caractère de Dirichlet est noté par le symbole χ et le groupe des caractères par Û.

### La fonction ω (s, u)

L'objectif est de définir sur S × U une fonction ω dont le comportement garantira que la classe m contient une infinité de nombres premiers.
   * Pour tout u ∈ U et tout s ∈ S, la série ω(s, u) définie par la formule suivante est absolument convergente.$\omega (s,u)=\sum _{p\in {\mathcal {P}}}\quad \sum _{k\in \mathbb {N} ^{*}{\text{ et }}p^{k}\in u}{\frac {1}{kp^{ks}}}$.
   * Si m ne contient qu'un nombre fini de nombres premiers alors la fonction S → ℂ, s ↦ ω(s, m) possède une limite en 1.
Une fois cette proposition établie, il suffira, par contraposée, de montrer que la fonction diverge en 1 pour démontrer le théorème.

#### La série qui définit ω(s, u) est absolument convergente

    Cette proposition est démontrée dans le paragraphe « Produit eulérien » de l'article détaillé.

#### Si m ne contient qu'un nombre fini de nombres premiers alors s ↦ ω(s, m) possède une limite en 1

    Pour $u\in U$ fixé, $\omega (s,u)=\psi _{1}(s)+\psi _{2}(s)$ avec$\psi _{1}(s):=\sum _{p\in {\mathcal {P}}\cap u}{\frac {1}{p^{s}}}\quad \quad {\text{et}}\quad \psi _{2}(s):=\sum _{p\in {\mathcal {P}}}\quad \sum _{k\geq 2{\text{ et }}p^{k}\in u}{\frac {1}{kp^{ks}}}.$Une majoration grossière par une série de Riemann convergente montre que la série ψ$_2$ est normalement convergente sur le demi-plan fermé Re(s) ≥ 1 :$\mathrm {Re} (s)\geq 1\Rightarrow {\frac {1}{\left|kp^{ks}\right|}}\leq {\frac {1}{\left|p^{ks}\right|}}\leq {\frac {1}{p^{k}}}\quad {\text{et}}\quad \sum _{p\in {\mathcal {P}}}\quad \sum _{k\geq 2}{\frac {1}{p^{k}}}=\sum _{p\in {\mathcal {P}}}{\frac {1}{p(p-1)}}<\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}<+\infty .$Si ${\mathcal {P}}\cap u$ est fini, ψ$_1$ est une simple fonction entière, définie sur le plan complexe tout entier.

### Délocalisation des nombres premiers

La difficulté réside dans le fait que la sommation dans ω(s, m), contrairement à celle dans ζ(s), n'est réalisée que sur les nombres premiers appartenant à m.
Cependant, la fonction ω dépend d'un paramètre u élément d'un groupe abélien fini. Or un tel groupe possède une analyse harmonique très simple. Les fonctions trigonométriques sont remplacées par les caractères et l'on dispose d'une transformée de Fourier et du théorème de Plancherel ; il permet de « délocaliser » l'ensemble des nombres premiers :
   La fonction ω est égale à l'expression suivante sur son domaine de définition :
   $\forall s\in S,\quad \forall u\in U,\quad \omega (s,u)={\frac {1}{\varphi (n)}}\sum _{\chi \in {\widehat {U}}}{\overline {\chi (u)}}\;\log \left(L(s,\chi )\right),\quad {\text{avec}}\quad L(s,\chi )=\sum _{k=1}^{\infty }{\frac {\chi (k)}{k^{s}}}$
Une démonstration est donnée dans le paragraphe « Application » de l'article détaillé.

### Série L de Dirichlet

Si χ n'est pas le caractère principal, sa série L de Dirichlet est définie et continue en 1 avec une valeur non nulle (une démonstration est donnée dans le paragraphe « Comportement au point un » de l'article détaillé). En revanche, si χ est le caractère principal, sa série L (dont le log est affecté, dans le développement de ω(s, m), du coefficient χ(m) = 1) est égale à $\zeta (s)\times \prod _{p{\text{ premier}}\mid n}\left(1-p^{-s}\right)$, où $\zeta$ est la fonction zêta de Riemann, qui diverge au point 1. Ceci permet d'énoncer la proposition suivante, qui termine la démonstration comme annoncé ci-dessus :
   Pour toute classe m dans U, la fonction ω(s, m) diverge quand s tend vers 1.