Nombres premiers et progressions arithmétiques

Piste rouge 24 septembre 2011  - Ecrit par  Bruno Duchesne Voir les commentaires (7)

L’étude des nombres premiers est un domaine fascinant des mathématiques : c’est sûrement le seul dont les plus célèbres problèmes ont un énoncé relativement simple et qui pourtant se révèlent extrêmement difficiles à résoudre (certains n’étant même pas résolus).

Ces problèmes ne font appel qu’à l’addition et la multiplication mais des méthodes évoluées ont été utilisées pour les résoudre. Nous allons voir quelques résultats spectaculaires liant nombres premiers et progressions arithmétiques.

Les nombres premiers

Un nombre premier est un entier naturel admettant exactement deux diviseurs distincts, $1$ et lui-même. On a l’habitude de noter $p_n$ le $n$-ième nombre premier. Ainsi, $p_1=2,\ p_2=3,\ p_3=5,\ p_4=7,\ p_5=11\dots$ La première question sur les nombres premiers fut de savoir si cette suite s’arrête ou continue à l’infini, autrement dit, de savoir s’il existe une infinité de tels nombres. La réponse est positive et est un théorème d’Euclide. La démonstration, élégante, d’Euclide tient en trois lignes. Maintenant que l’on sait qu’ils sont en quantité infinie, on peut essayer d’en faire la liste même si on sait que l’on n’arrivera jamais au bout puisqu’elle est infinie ! Voici par exemple en rouge ceux plus petits que 3189. Cliquer sur l’image puis sur [zoom] pour voir la liste en détails.

PNG - 413.5 ko

On pourrait être tenté de trouver une formule qui donne le prochain nombre premier connaissant les précédents. Malheureusement (ou heureusement), il n’existe pas de telle formule (utilisable en pratique) et les nombres premiers semblent avoir un comportement complètement erratique ; à part ne pas être multiple d’un nombre plus petit, ils ne semblent respecter aucune autre règle. Par exemple, il arrive que deux nombres premiers soient séparés par un unique nombre entier (881 et 883) mais il existe aussi des “trous” aussi grands que l’on veut entre deux nombres premiers successifs. En effet, pour un entier $N$ aussi grand que l’on veut, il existe deux entiers premiers successifs $p_n$ et $p_{n+1}$ tels que $p_{n+1}>p_n+N$.

Preuve : Posons $M=(N+1)\times N\times (N-1)\times (N-2)\times\dots \times3\times2\times1$, le produit de tous les entiers plus petits que $N+1$. Alors $M+2$ est divisible par 2 (car $M$ est divisible par 2), $M+3$ est divisible par 3,... Et ainsi tous les nombres $M+2,\ M+3,\ M+4,\dots,\ M+N+1$ ne sont pas premiers, ce qui donne un trou de longueur au moins $N$.

Progressions arithmétiques

À l’opposé de la suite des nombres premiers, les progressions arithmétiques ont un comportement qui n’a rien d’erratique et qui, bien au contraire, est très ordonné. Elles sont la régularité même. Une progression ou suite arithmétique est une suite (finie ou infinie) de nombres entiers $a_1,a_2,a_3,a_4,\dots$ telle que la différence entre deux termes successifs est constante. C’est-à-dire qu’il existe un entier $r$ appelé raison tel que $a_{n+1}-a_n=r$ pour tout $n$. Voici un exemple. La suite
\[a_1=7,a_2=10,a_3=13,a_4=16,\dots,a_9=31,a_{10}=34\]
est une suite arithmétique à dix termes de raison 3 et de premier terme 7. Il existe une formule simple pour décrire le $n^{\mathrm{ieme}}$ terme d’une suite arithmétique : $a_n=a_1+(n-1)r$.

Si on s’intéresse aux suites arithmétiques infinies, il y en a des plus naturelles que d’autres car n’importe quelle suite arithmétique infinie est obtenue à partir d’une de celles-ci en “effaçant” des termes au début. Ces suites plus naturelles sont les suites arithmétiques de raison $r$ et de premier terme strictement plus petit que $r$. En effet si $(a_n)$ est une suite arithmétique de raison $r$ et si le premier terme, $a_1$, est plus grand que $r$, on rajoute un terme $a_1-r$ au début de la suite et ainsi de suite jusqu’à obtenir un premier terme compris entre 0 et $r-1$. La suite 7, 10, 13... ci-dessus est une sous-suite de la suite infinie 1,4,7,10,13,... Si $r$ vaut 5 voici ces 5 suites principales :

0, 5, 10, 15, 20, 25...
1, 6, 11, 16, 21, 26...
2, 7, 12, 17, 22, 27...
3, 8, 13, 18, 23, 28...
4, 9, 14, 19, 24, 29...

Diviser l’ensemble des nombres entiers en parts égales

Comme l’ensemble des nombres entiers est infini, l’expression “la moitié des entiers”, par exemple, demande quelques précisions. Pourtant, il est intuitivement clair que les nombres pairs représentent la moitié des nombres entiers. L’autre moitié étant, bien sûr, celle des nombres impairs. De manière plus savante, les entiers pairs forment la suite arithmétique infinie de raison 2 et de premier terme 0 alors que les entiers impairs forment la suite arithmétique infinie de raison 2 et de premier terme 1. Maintenant quelle est la part d’une suite arithmétique infinie quelconque parmi tous les entiers ?

Nous avons vu qu’il y avait exactement $r$ suites arithmétiques principales de raison $r$. Intuitivement ces $r$ suites n’occupent pas une plus grande part les unes que les autres, il semble intuitif de dire qu’une suite arithmétique principale représente une part égale à $1/r$ de l’ensemble des nombres entiers. Les suites arithmétiques non principales sont obtenues en retirant un nombre fini de termes au début d’une suite principale et comme un nombre fini est négligeable devant l’infini, dire qu’une suite arithmétique infinie de raison $r$ représente une part égale à $1/r$ semble naturel. Voici comment rendre rigoureux tout cela en appelant densité ce que nous appelions part.

Définition : Si $(a_n)$ est une suite infinie de nombres entiers, strictement croissante ($a_{n+1}>a_n$), on note $c_n$ le nombre d’éléments de la suite plus petits que $n$ et on appelle densité de cette suite la limite $\lim_{n\to\infty} c_n /n$ quand celle-ci existe [1].

Avec cette définition, $c_n/n$ est la proportion d’éléments de la suite parmi les entiers entre 1 et $n$. Cette définition rigoureuse donne densité $1/r$ à toute suite arithmétique infinie de raison $r$ et si on retire un nombre fini de termes d’une suite alors la suite obtenue a encore même densité. Avec cette définition, il est facile de voir que la suite des carrés ($a_n=n^2$) a une densité nulle et il est amusant (mais plus difficile) de voir que la suite des nombres qui ne sont pas divisibles par un carré a une densité égale à $\frac{6}{\pi^2}$.

Quand deux suites $(a_n)$ et $(b_n)$ sont telles que $(a_n)$ est obtenue en “effaçant” des termes à la suite $(b_n)$ on dit que $a_n$ est une sous-suite de $b_n$. Dans ce cas et si $b_n$ est croissante ($b_{n+1}\geq b_n$), on a toujours $a_n\geq b_n$ et ainsi la densité de $(a_n)$ est plus faible que celle de $(b_n)$ (on a retiré des termes à la suite $(b_n)$ donc il nous reste une part plus petite...).

Exemple : La suite des multiples de 4 est une sous-suite de la suite des entiers pairs. La suite des multiples de 4 est la moitié de celle des entiers pairs dans le sens où les densités respectives sont $\frac{1}{4}$ et $\frac{1}{2}$.
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,...

Quelle est la densité des nombres premiers ?

Le théorème des nombres premiers

Le théorème des nombres premiers ne donne pas de formule pour le $n^{\mathrm{ieme}}$ nombre premier mais donne son comportement « à l’infini ». On peut voir ce résultat comme un analogue du fait que l’on est incapable de prévoir le résultat d’un lancer de dé mais que l’on sait que lorsque le nombre de lancers augmente, la proportion de 5 obtenus tend vers $1/6$. Voici l’énoncé obtenu au même moment mais indépendamment par Jacques Hadamard et Charles-Jean de la Vallée-Poussin.

Théorème des nombres premiers, 1896 : Si $c_n$ le nombre de nombres premiers plus petits que $n$ alors \[\frac{c_n}{n/\log(n)}\] tend vers 1 quand $n$ tend vers $+\infty$.

Ce qui signifie que le comportement à l’infini de $c_n$ est du même type que celui de $\frac{n}{\log(n)}$. Ici $\log(n)$ désigne le logarithme népérien de $n$, voici le graphe de cette fonction :

Une propriété importante du logarithme est de tendre vers $+\infty$ quand $n$ tend vers $+\infty$. De cela, on déduit tout de suite le résultat suivant dû à A.-M. Legendre.

Théorème de la raréfaction des nombres premiers, 1808 : la densité des nombres premiers est nulle.

En effet, $\lim\frac{n/\log(n)}{n}=0$. Les nombres premiers sont donc de plus en plus rares ! Cette densité nulle [2] a, par exemple, la conséquence suivante : il n’existe aucune suite arithmétique infinie constituée uniquement de nombres premiers [3]. En effet, dans le cas contraire, la densité des nombres premiers serait plus grande que celle de cette suite arithmétique, qui est de densité strictement positive.

Équirépartition

Nous avons vu qu’il y a un moyen simple de couper l’ensemble des nombres entiers en $r$ parts égales, chacune de ces parts étant une des suites arithmétiques principales de raison $r$. Si on pense que les nombres premiers ont un comportement vraiment aléatoire alors on se dit que les nombres premiers vont se répartir de manière uniforme parmi ces parts. On peut voir cela comme un analogue aux lancers de dé, qui se répartissent uniformément entre 1 et 6. Cette équirépartition (ou répartition uniforme) des nombres premiers est presque vraie à l’objection suivante, près. Si $(a_n)$ est une suite arithmétique de raison $r$ et de premier terme $a_0$ telle que $r$ et $a_0$ possèdent un diviseur commun $d$, alors tous les entiers $a_n$ sont aussi divisibles par $d$. Cette suite contient donc au plus un nombre premier (qui serait alors $a_0$).

Comme précédemment, pour définir rigoureusement l’idée de proportion parmi les nombres on utilise des limites. Fixons les entiers $ r $ et $ 0 \leq q < r $. On peut alors définir la proportion (parmi les nombres premiers) de nombres premiers qui sont dans la suite arithmétique de raison $r$ et de premier terme $q$. Appelons $P_q^r$ cette proportion.

Définition précise de $P_q^r$

\[P_q^r=\lim_{n\to\infty} \frac{\left|\left\{p_i,\ p_i \equiv q\ [r]\right\}_{i\leq n}\right|}{n}.\]

Les notations utilisées pour le numérateur sont à comprendre dans le sens suivant : Considérons les $n$ premiers nombres premiers et parmi ceux-là comptons uniquement ceux dont le reste dans la division euclidienne par $q$ est $r$. Le résultat de ce comptage est égal au numérateur de la fraction ci-dessus.

Voici le célèbre résultat dû à J. Lejeune Dirichlet.

Théorème de la progression arithmétique, 1838 : Si $r$ et $q$ n’ont pas de diviseur commun alors $P_q^r=\frac{1}{\varphi(r)}$.

Ici, $\varphi(r)$, connu sous le nom d’indicatrice d’Euler de $r$, est le nombre d’entiers positifs $0 < m < r$ tels que $r$ et $m$ n’ont pas de diviseur commun. Par exemple, si $r=10=2\times5$ alors les entiers positifs plus petits que 10 et sans diviseur commun avec 10 sont 1, 3, 7 et 9 donc $\varphi(10)=4$. Sur la figure ci-dessous, sont représentés les nombres entiers inférieurs à 1099 et on trouve en rouge ceux qui sont premiers. À part les nombres 2 et 5, les nombres premiers se trouvent uniquement sur les colonnes des nombres qui terminent par 1,3,7 ou 9.

PNG

Le théorème affirme que les suites arithmétiques de raison $r$ et de premier terme $q$ qui n’a pas de diviseur commun avec $r$ contiennent toutes la même proportion de nombres premiers, qui est $1/\varphi(r)$. On l’illustre ci-dessous avec en rouge les nombres premiers terminant par 1, en bleu ceux terminant par 3, en vert ceux terminant par 7 et en jaune ceux terminant par 9. Le théorème donne donc autant de chaque couleur à l’infini.

PNG

Le théorème de Szemerédi

Si une suite contient une suite arithmétique infinie alors elle est de densité positive. La réciproque est-elle vraie ? Toute suite de densité positive contient-elle une sous-suite infinie qui soit arithmétique ?

En fait, il n’est pas très difficile de construire un exemple de suite de densité 1 et ne contenant aucune suite arithmétique infinie.

Exemple : On part de la suite de tous les nombres entiers et on retire les entiers $2^n+1,2^n+2,\dots,2^n+n$ pour tout entier $n$. C’est à dire que l’on va de puissance de 2 en puissance de 2 en faisant à chaque fois un trou de longueur l’exposant de cette puissance. Par exemple, pour $n=1$, on retire $3$ ; pour $n=2$, on retire $5,6$ ; pour $n=3$, on retire $9,10,11$ et ainsi de suite. Comme les trous sont de plus en grands, il ne peut y avoir de sous-suite arithmétique infinie. De plus, on peut montrer que la densité de cette suite est 1.

Le théorème de Szemerédi (dejà évoqué dans ce billet) dit cependant que c’est presque vrai.

Théorème de Szemerédi, 1975 : Toute suite de densité strictement positive contient des suites arithmétiques de longueur finie aussi grande que voulue.

Qu’en est-il pour la suite des nombres premiers ?

Le théorème de Green et Tao

Puisque la suite des nombres premiers est de densité nulle, le théorème de Szemerédi ne peut pas s’appliquer. Pourtant Ben Green et Terence Tao ont réussi le tour de force de montrer que la conclusion est quand même vraie. Et cela, en réutilisant le théorème de Szemerédi de manière indirecte ! Ce théorème a contribué à l’obtention de la médaille Fields par Terence Tao en 2006.

Ben Green et Terence Tao

Théorème de Green et Tao, 2004 : La suite des nombres premiers contient des suites arithmétiques de longueur finie arbitraire.

Le théorème ne dit, par contre, rien sur la raison des ces suites de longueur arbitraire.

Conclusion

Les liens entre nombres premiers et suites arithmétiques laissent encore des mystères à percer pour les mathématiciens. Le mystère le plus célèbre est certainement celui des nombres premiers jumeaux. On dit que deux nombres premiers sont jumeaux si leur différence est exactement 2 (c’est-à-dire une suite arithmétique de raison 2 et de longueur 2). Par exemple 3 et 5, 17 et 19, 857 et 859... On connaît des nombres premiers jumeaux dont l’écriture demande plus de 58 000 chiffres ! Mais en existe-t-il pour autant une infinité ? C’est l’énoncé de la conjecture des nombres jumeaux, qui est pour l’instant toujours non démontrée (et non infirmée).

Conjecture des nombres jumeaux : Il existe une infinité de paires de nombres premiers jumeaux.

Les nombres premiers sont connus depuis des millénaires mais n’ont pas encore révélé tous leurs secrets...

Post-scriptum :

Il existe aussi une preuve de l’infinitude de l’ensemble des nombres premiers à l’aide de suites arithmétiques ! Cette preuve due à H. Furstenberg est courte et nécessite la notion de topologie.

On trouvera sur le site d’autres articles et billets traitant des nombres premiers : Histoire des nombres premiers, Une formule pour les nombres premiers et Nombres premiers, encore et toujours.

L’auteur remercie Marie, A. Conway, E. Ghys, Caocoa, bedaride nicolas, bayéma et Alan Picol pour leurs relecture et commentaires.

Notes

[1On peut chercher des exemples où cette limite n’existe pas.

[2Cette densité nulle découle aussi plus élémentairement d’une majoration due à Tchebychev. On remarquera d’ailleurs, que le théorème de la raréfaction des nombres premiers apparaît bien avant le théorème des nombres premiers.

[3L’argument montrant l’existence de trous aussi grands que l’on veut, permet déjà de le voir.

Partager cet article

Pour citer cet article :

Bruno Duchesne — «Nombres premiers et progressions arithmétiques» — Images des Mathématiques, CNRS, 2011

Crédits image :

Ben Green et Terence Tao - Sites personnels de Ben Green et Terence Tao

Commentaire sur l'article

  • Nombres premiers et progressions arithmétiques

    le 24 septembre 2011 à 13:21, par Michèle Audin

    On trouvera sur le site d’autres articles et billets traitant des nombres premiers

    Je me permets de signaler aussi cet article, dans lequel sont présentées, de façon assez simples (piste bleue), le théorème de la progression arithmétique de Dirichlet et la répartition des nombres premiers.

    Répondre à ce message
  • Nombres premiers et progressions arithmétiques

    le 26 septembre 2011 à 13:35, par Jérôme Buzzi

    Il n’est peut-être pas inutile de rappeler l’ouvrage « Les nombres premiers, entre l’ordre et le chaos » de G. Tenenbaum, M. Mendès-France (Que sais-je ? (2000) et Dunod (2011)).

    Répondre à ce message
    • Nombres premiers et progressions arithmétiques

      le 26 septembre 2011 à 14:25, par Bruno Duchesne

      En effet, ce petit livre est sûrement une très bonne référence. Je ne sais pas si les deux éditions sont identiques (en tous cas, le titre 2011 est plus accrocheur que celui du ``que sais-je") mais l’édition de 2000 a été une référence importante pour rédiger ce petit article.

      Une petite bibliographie serait peut-être utile mais devant la quantité de références sur ce sujet, il est difficile d’être impartial et impossible d’être exhaustif. Je citerais seulement le cours d’arithmétique de Jean-Pierre Serre pour une preuve du théorème de la progression arithmétique (avec une notion de densité un peu différente). Si on souhaite en savoir plus sur les deux derniers théorèmes, il faudra consulter des articles de recherche. Pour une preuve du théorème de Szemeredi, on pourra consulter (entre autres) la preuve ergodique de Furstenberg en 1982 au Bulletin de l’AMS et pour le théorème de Green et Tao, on pourra consulter leur article original.

      Bruno (un étudiant en stage pour un mois en 2005 à Palaiseau).

      Répondre à ce message
      • Nombres premiers et progressions arithmétiques

        le 26 septembre 2011 à 21:38, par François Brunault

        Merci pour cet article qui montre bien que sur un sujet aussi ancien que les nombres premiers, on découvre encore aujourd’hui de nouvelles choses.

        Juste un petit rectificatif par rapport au message précédent, l’article original de Ben Green et Terence Tao se trouve à l’adresse suivante : http://arxiv.org/abs/math/0404188

        On trouve également sur la page web de Terence Tao des articles plus introductifs à ce théorème : voir le début de la page http://www.math.ucla.edu/ tao/preprints/acnt.html

        Répondre à ce message
        • Nombres premiers et progressions arithmétiques

          le 26 septembre 2011 à 21:45, par Bruno Duchesne

          Merci pour la correction et le lien !

          Répondre à ce message
  • Nombres premiers et progressions arithmétiques

    le 21 février 2012 à 12:08, par seguin

    Merci pour cet article qui nous éclaire sur un domaine interessant ; je veux juste faire une remarque sur le passage :« il est amusant (mais plus difficile) de voir que la suite des nombres qui ne sont pas divisibles par un carré a une densité égale à 6/π2. »
    ce qui permet de dire que la part de ces nombres dans l’ensemble des nombres entiers est supérieure à 3/5
    amusant certes, étonnant,surprenant même si l’on songe qu’à chacun de ces nombres on peut associer une boite qui contient tous les nombres entiers qui ont exactement
    les mêmes diviseurs premiers
    chaque boite contient une infinité d’entiers dont un seul sans diviseur carre, les boites sont constituée d’ensembles s disjoints

    Répondre à ce message
  • Nombres premiers et progressions arithmétiques

    le 29 janvier 2013 à 10:45, par Georges Peyrichou

    En tant que béotien je ferai quelques remarques. L’article dit :
    « Pourtant, ces nombres restent insaisissables dans le sens où il est très difficile de prédire le prochain nombre premier, ou même de déterminer, dans la pratique, les facteurs premiers d’un très grand entier. »
    Je suis d’accord quand il s’agit de nombres premiers inembrassables, c’est-à-dire « l’infinité moins quelques milliers » mais pour ces milliers, un crible triangulaire basé sur la suite des carrés et des impairs vous donne par comparaison tous les premiers à la suite. Le problème des premiers est donc concrètement pratique. En paraphrasant un illustre on peut dire « donner moi le Calculateur et je vous donnerai la liste des premiers ». La limite étant l’infinitude. L’existence d’un nombre premier commence quand la mise en parallèle de tous les multiples de ses prédécesseurs laisse des « trous non nommés » dans la suite des entiers naturels. Ce nombre premier « suivant », étant donc induit par la divisibilité, ne peut en aucun cas être le résultat d’une opération dans l’ensemble des premiers.

    L’article dit, « Les nombres premiers sont donc de plus en plus rares ! »
    Si les premiers sont de plus en plus rares ils nous mettent en face d’une réalité de « point de vue ». Si l’on considère les écarts entre les carrés des nombres entiers, le nombre des premiers compris dans ces écarts semble augmenter régulièrement… à l’infini selon une courbe bornée (à définir). Ce qui est normal.

    Pour les premiers jumeaux, ils sont « nécessaires » à la décomposition de nombres en somme de nombres premiers qui ne se répètent pas telles ces suites symétriques croissantes :

    129=0+2+3+5+7+11+13+19+23+29

    058=0+2+3+5+7+11+13+17

    028=0+2+3+5+7+11

    010=0+2+3+5

    005=2+3+5

    002=0+2

    000=1+2+3+5+7+11+13+17+19+23+29

    004=1+0+3

    007=0+2+0+5

    012=0+2+3+0+7

    030=0+2+3+5+7+00+13

    060=0+2+3+5+7+11+13+00+19

    131=0+2+3+5+7+11+13+17+19+23+00+31

    Pour finir j’aimerais avoir une idée du début de la courbe résultant des « sinusoïdes » des premiers.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM