06/12/2010
L'Algorithme de Génération des Premiers
Version [pdf ] (1.07 Mo, 12 pages) L'Algorithme de Génération des Premiers (AGP)
Article déposé le 19 avril 2010. Toute reproduction pour publication ou à des fins commerciales, de la totalité ou d'une partie de l'article, devra impérativement faire l'objet d'un accord préalable avec l'éditeur (ENS Ulm). Toute reproduction à des fins privées, ou strictement pédagogiques dans le cadre limité d'une formation, de la totalité ou d'une partie de l'article, est autorisée sous réserve de la mention explicite des références éditoriales de l'article.
Une version courte de cet article a été publiée par la Revue Tangente (n°108, 2006). CultureMATH remercie la Revue Tangente d'avoir autorisé la publication de cette version complétée.
|
SOMMAIRE Avant propos 1. Du crible d'Eratosthène à l'AGP 2. Les lois mathématiques de l’AGP Théorème de "stabilisation" Conclusion : l’ordre plutôt que le chaos Bibliographie
Tableau : Algorithme de Génération de Premiers
Version courte de l'article en anglais - The Prime-Generating Algorithm |
1. Du crible d'Eratosthène à l'AGP
Le fameux crible d’Eratosthène vieux de plus de 2000 ans sera néanmoins un excellent moyen de comparaison pour introduire l’AGP. Rappelons son principe. Il est basé sur le fait qu’un nombre entier est premier s’il n’est pas divisible par tous les nombres qui lui sont strictement inférieurs à l’exclusion de 1. Si on cherche par exemple les nombres premiers inférieurs à cent, on opère ainsi : on place les nombres de 2 à 100 dans un tableau. On entoure le nombre 2 qui est premier, puis on barre les multiples stricts de 2 du tableau. On entoure le plus petit nombre non barré qui est 3. 3 est premier puisqu’il n’est pas divisible par les nombres qui lui sont inférieurs et qui se résument à 2. On entoure le nombre 3 et on barre tous les multiples stricts de 3. Le plus petit nombre non barré est 5 qui est premier car il n’est divisible ni par 2 ni par 3, ni par 4, et ainsi de suite. On obtient par ce procédé tous les nombres premiers inférieurs à cent. Le crible nous fait toucher du doigt qu’un nombre est premier en fonction de ceux qui l’ont précédé. Ainsi 5 est premier en fonction de la non divisibilité par 2 ou par 3. Ce qui explique d’ailleurs le mal que l’on a pour trouver les grands nombres premiers. A titre de comparaison élémentaire, si un nombre est pair cela ne dépend pas des nombres pairs qui l’ont précédé. Pour autant, si le crible permet de trouver les nombres premiers, il n’a pas la vocation d’expliquer leur répartition. Tout au contraire, il met en évidence que les nombres premiers apparaissent dans le tableau dans une succession qui ne laisse deviner aucun ordre et aucune loi, et c’est bien ce problème qui a tant intrigué, voire fasciné, les mathématiciens depuis plus de 2000 ans.
Dans le remarquable livre de Gilles Godefroy L’aventure des nombres, nous avons eu l’attention attiré par un chapitre intitulé : Connaître un ensemble par son complémentaire. Gilles Godefroy exprime d’abord l’idée qu’il est difficile d’exhiber des nombres premiers arbitrairement grands alors qu’on peut obtenir sans peine des nombres composés aussi grands soient - ils. Gilles Godefroy poursuit « Nous voyons ici poindre une idée, implicite chez Euclide comme chez Cantor : on peut étudier un ensemble au moyen de son complémentaire, montrer l’existence d’objets qui jouissent de certaines propriétés en étudiant les objets qui n’ont pas ces propriétés. Le crible d’Eratosthène, qui exhibe les nombres premiers comme étant ceux qui ne sont pas composés reflète d’ailleurs cette dissymétrie. » [1]
En effet, le crible se contente d’éliminer les composés pour faire apparaître les premiers. Avant de présenter notre algorithme (AGP) qui se propose plus précisément d’étudier les propriétés des nombres composés pour connaître leur complémentaire, les premiers, passons une dernière fois "au crible" le fameux crible! Quand on barre les multiples de trois on constate que des nombres ont déjà été barrés. Ce sont bien entendu les multiples communs à deux et à trois. Cette simple remarque met en évidence ceci : en prenant successivement tous les multiples des nombres premiers on décrit N tout entier, mais on ne réalise pas une partition de l'ensemble des entiers naturels N. Ce sera l’une des différences essentielles entre le crible et l’AGP. L’AGP réalise, lui, une partition de N ce qui offre un avantage considérable pour les problèmes de dénombrements. L’autre différence que nous allons bientôt constater est que dans le crible tous les nombres non premiers sont impitoyablement barrés. Dans l’AGP, au contraire les nombres non premiers sont tous écrits et jouent tous leur rôle dans la constitution de l’algorithme. Mais il est temps à présent de décrire l’AGP.
La première caractéristique de cet algorithme est d’abord d’utiliser le théorème fondamental de l’arithmétique qui dit que tout nombre entier s’écrit de manière unique comme produit de nombres premiers. Aucun résultat important sur les nombres premiers ne peut se dispenser de cette propriété essentielle. Ainsi le succès de la fonction zêta de Riemann dans l’étude de la répartition des nombres premiers, vient du fait qu’elle rend compte, dans sa définition même, de la décomposition des entiers en facteurs premiers.
La longueur d’un entier est le nombre de premiers qui entrent dans la décomposition de cet entier en produit de facteurs premiers. Exemples : la décomposition de 12 contient trois facteurs premiers (12= 2x2x3). Ainsi la longueur de 12 est 3. De même la longueur de 5 est 1.
Il est très facile d’exprimer le théorème fondamental de l’arithmétique en terme de longueur. En effet, appelons Er l’ensemble des entiers de longueur r, pour tout entier r. Dire que tout nombre est produit de manière unique de nombres premiers se traduit en disant que N est la réunion des Er, et que les Er forment une partition de N puisque Ei ∩ Ej = ∅ pour i ≠ j.
E1 est donc l’ensemble des nombres premiers. Mais c’est un ensemble qui se construit pas à pas comme on va le voir. 2 étant le plus petit nombre premier, observons que les ensembles Er ont un plus petit élément qui est 2r. C’est donc le plus petit nombre de longueur r.
Considérons à présent les intervalles Ir définis par : Ir = [2r ; 2r+1[ pour tout entier r. Tout entier de cet intervalle est strictement inférieur au plus petit entier de longueur r+1. Il en résulte que la longueur maximum des entiers de Ir est r. Cette longueur est atteinte par 2r. Nous admettrons provisoirement que les longueurs des entiers de Irprennent toutes les valeurs de 1 à r. Observons que les intervalles Ir forment une partition de N et que par conséquent il en est de même des ensembles Ir ∩ Ei lorsque ivarie de 1 à r.
L’algorithme AGP consiste à écrire successivement ces ensembles en commençant par r = 0, l’algorithme commençant vraiment pour r = 1 puisque 1 n’est pas premier. Comme ces ensembles forment une partition de N, nous allons être amenés à réécrire les nombres entiers selon notre loi algorithmique.
Tableau 1 : Algorithme de Génération de Premiers
| Longueurs des entiers | ||||||
| Intervalles Ir | 1 | 2 | 3 | 4 | 5 | ... |
| Io = [20 ; 21 [ | 1 |
|||||
| I1 = [21 ; 22 [ |
2 3 |
|||||
| I2 = [ 22 ; 23 [ | 5
7 |
2×3 2×2 |
||||
| I3 = [ 23 ; 24 [ | 11 13 |
2×5
2×7 3×5 3×3 |
2×2×2 2×2×3 |
|||
| I4 = [ 24 ; 25 [ |
17 19 23 29 31 |
2×11 2×13 3×7 5×5 |
2×3×3 2×2×5 2×3×5 2×2×7 3×3×3 |
2×2×2×2 2×2×2×3 |
||
| I5 = [ 25 ; 26 [ |
37 41 43 47 53 59 61 |
2×31
2×29 2×23 2×19 2×17 3×19 3×17 3×13 3×11 5×11 5×7 7×7 |
2×2×11 2×2×13 2×2×7 3×3×5 3×3×7 2×5×5 |
2×2×2×5
2×2×2×7 2×2×3×3 2×2×3×5 2×3×3×3 |
2×2×2×2×2
2×2×2×2×3 |
|
| ... |
Générés par 2 ; 3 ; 5 ; 7 ; 11 et 13 |
Stabilisé à 5 entiers Générés par 2 ; 3 ; 5 et 7 |
Stabilisé à 2 entiers Générés par 2 et 3 |
|||
On pourrait présenter de manière imagée l’algorithme ainsi : chaque intervalle Ir est un train. La locomotive est représentée par les nouveaux nombres premiers ; les wagons sont formés à l’aide des anciens. Le wagon de queue du train I4 est formé par les premiers de l’intervalle I1 à savoir 2 et 3. De plus le wagon de queue comportera toujours deux éléments quelque soit l’intervalle (dans I1000 les nombres de longueur mille sont au nombre de 2). L’avant dernier wagon de I4 (les nombres de longueur 3) est formé des premiers qui se trouvent dans I1 et I2. Le nombre d’entiers de ce wagon est cinq et on peut montrer qu’il est stabilisé. C'est-à-dire que le nombre d’entiers de l’avant dernier wagon (les entiers de longueur 4) du train suivant I5 est aussi égal à cinq comme on peut l’observer sur le Tableau 1. Plus les trains sont longs plus il y a de wagons comportant un nombre stabilisé d’entiers. Ainsi on montre que dans I100 les trente-six derniers wagons ont un nombre d’entiers stabilisé (voir ci-dessous le théorème dit de « stabilisation »).
2. Les lois mathématiques de L’AGP
On donne ici une série de théorèmes qui expliquent le fonctionnement de l’AGP. Le théorème de « stabilisation » (théorème 4) nous paraît le plus important.
Soit l’intervalle Ir = [2r ; 2r+1[. On désigne par Lr,m les entiers de Ir de longueur m. L’entier m varie donc de 1 à r.
Théorème 1
A) Les nombres premiers q qui sont dans la décomposition des entiers de Lr,m sont tels que q < 2 r - m + 2.
B) Pour tout q premier vérifiant la condition q < 2 r - m + 2 il existe au moins un entier de Lr,m , avec 2 ≤ m ≤ r, qui contient q comme facteur.
Preuve A)
Si q ≥ 2 r - m + 2 alors 2m-1q ≥ 2r+1.
Or 2m-1q est le plus petit entier de longueur m qui contient q. Donc il n’y a aucun entier de Lr,m contenant q.
On a donc nécessairement q < 2 r - m + 2 .
Pour démontrer B nous avons besoin du lemme suivant :
Lemme
Pour tout réel x ≥ 2 on peut toujours trouver un nombre premier compris entre x et 2x.
Preuve
Rappelons que le postulat de Bertrand assure que pour tout entier n > 1 on peut toujours trouver un nombre premier compris entre n et 2n.[3]
Soit x réel, x ≥ 2 et E(x) la partie entière de x. On a E(x) > 1 et d’après Bertrand il existe un nombre premier p tel que E(x) < p < 2 E(x) qui entraîne E(x) + 1 ≤ p < 2E(x).
Comme E(x) ≤ x < E(x) +1. On déduit x < E(x) + 1 ≤ p < 2 E(x) ≤ 2x ce qui prouve notre assertion.
Preuve B)
Soit q < 2 r - m + 2.
Si 2 r - m + 1 ≤ q < 2 r - m + 2 alors 2 r ≤ 2 m - 1 q < 2 r - 1.
Donc pour 2 ≤ m ≤ r il existe bien au moins un entier de Lr,m qui contient q comme facteur.
Si q < 2 r - m + 1 alors 2 r - m + 1 / q > 1 et 2 r - m + 2 /q > 2.
Donc d’après le lemme précédent, il existe un nombre premier p entre 2 r - m + 2 /q et 2 r - m + 3 /q.
On en déduit pour 2 ≤ m ≤ r que 2 m - 2 pq est dans Ir et ce nombre est bien un entier de longueur m qui contient q comme facteur.
En d’autres termes les entiers de longueur m telle que 2 ≤ m ≤ r d’un intervalle Ir sont « engendrés » par tous les nombres premiers inférieurs ou égaux à ceux de l’intervalle I r - m +1. (On dira que des nombres premiers engendrent une collection H de nombres entiers si tous ces premiers se trouvent dans la décomposition des entiers de H et s’il n’y en a pas d’autres).
Pour bien comprendre ce résultat il est utile de reprendre le tableau précédent de notre algorithme correspondant à l’intervalle I4 = [ 24 ; 25[ :
Tableau 2
| L4,1 | L4,2 | L4,3 | L4,4 |
| 17 | 2×11 | 2×3×3 | 2×2×2×2 |
| 19 | 2×13 | 2×2×5 | 2×2×2×3 |
| 23 | 3×7 | 2×3×5 | |
| 29 | 5×5 | 2×2×7 | |
| 31 | 3×3×3 |
On a dit que les entiers de Lr,m sont engendrés par les nombres premiers qui vérifient q < 2 r - m + 2.
Donc en faisant r = 4 on a L4,m qui est engendré par les q < 2 6 - m :
Pour m = 4 on a L4,4 engendrés par les premiers q < 2² soit q = 2 et q = 3.
Pour m = 3 on a L4,3 engendrés par les premiers q < 23 soit q = 2 , q = 3, q = 5, q = 7.
Pour m = 2 on a L4,2 engendrés par les premiers q < 24 soit q = 2 et q = 3, q = 5, q = 7, q = 11 , q = 13.
Ce que l’on vérifie aisément avec le tableau de I4.
Théorème 2
Les nombres premiers qui engendrent Lr,m avec 2 ≤ m ≤ r sont les mêmes que ceux qui engendrent Lr+n,m+n, avec n entier relatif tel que n ≥ 2 - m.
Preuve
Les premiers qui engendrent Lr,m avec 2 ≤ m ≤ r sont les premiers q tels que q < 2 r - m + 2 .
Les premiers qui engendrent Lr+n,m+n avec 2 ≤ m+ n ≤ r + n (qui équivaut à n ≥ 2 - m sous l’hypothèse 2 ≤ m ≤ r) sont les premiers tels que q < 2 r+n - (m+n) + 2, c'est-à-dire q < 2 r - m + 2.
Ce sont donc les mêmes que ceux qui engendrent Lr,m.
Par exemple, on voit dans le Tableau 1 donnant le début de l’algorithme : les entiers de L4,3 sont 2×3×3 ; 2×2×5 ; 2×3×5 ; 2×2×7 ; 3×3×3, et ceux de L3,2 sont 2×5 ; 2×7 ; 5×5 ; 3×3.
Ces deux collections d’entiers sont engendrés par les mêmes premiers 2 ; 3 ; 5 et 7 tels que q < 23.
Théorème 3
Pour m ≥ (r+1)ln2 / ln3 tous les entiers de Lr,m sont pairs.
Preuve
En effet, 3m est le plus petit entier de longueur m qui n’est pas pair. Donc pour 3m ≥ 2r+1 tout entier de Lr,m est pair, ce qui est vrai pour m ≥ (r+1)ln2 / ln3.
Théorème 4 (dit de "stabilisation")
Pour r entier et pour m ≥ (r+1)ln2 / ln3 on a card( Lr,m)= card( Lr + n, m + n) pour tout entier n.
Preuve
D’après le Théorème 3, pour m ≥ (r+1)ln2 / ln3 les entiers de Lr,m sont pairs.
Dans ce cas, on en déduit que pour tout n, m + n ≥ (r+1)ln2 / ln3 + n.
Comme ln2 / ln3 < 1 on a n ln2 / ln3 < n et finalement m + n ≥ (r + n + 1)ln2 / ln3 qui prouve toujours d’après le théorème 3 que les entiers de Lr + n, m + n sont pairs.
Montrons à présent que, lorsque les entiers de Lr,m sont pairs, card (Lr,m)= card (Lr + 1, m+1).
Si q1.q2…qm est un élément de Lr,m alors 2q1.q2…qm est dans Lr + 1, m+1.
Et si n’ est un élément de Lr + 1, m+1 , comme il est pair, il est de la forme 2 q'1.q'2…q'm et q'1.q'2…q'm est élément de Lr,m.
Donc les entiers de Lr + 1, m+1 sont tous les entiers 2n tels que n soit entier de Lr,m.
On a donc card (Lr,m)= card (Lr + 1, m+1).
On en déduit par itération : card( Lr,m)= card( Lr + n, m + n) pour tout entier n.
Par exemple pour I100 on trouve m ≥ (101)ln2 / ln3 , soit m ≥ 64.
Il y a donc 36 longueurs d’entiers dans I100 dont le cardinal est stabilisé. En d’autres termes, pour employer l’image ferroviaire précédente, pour r ≥ 100 les 36 derniers wagons d’entiers de Ir auront toujours le même cardinal.
Théorème 5
Pour n ≥ (r+1)ln2 / (ln3 - ln2) le nombre des entiers de Lr+n,1+n se stabilise.
Preuve
En effet, un raisonnement analogue à celui des théorèmes 3 et 4 conduit à la majoration 3n+1 ≥ 2r + n +1 qui donne le résultat annoncé.
Théorème 6
Pour m ≥ (r+1)ln2 / ln (p) il n’y a aucun entier dans Lr,m dont tous les termes sont supérieurs ou égaux à p, un nombre premier.
Preuve
En effet, pm est le plus petit entier de longueur m dont tous les facteurs sont supérieurs ou égaux à p.
Donc pour pm ≥ 2r +1 , il n’y a aucun entier dans Lr,m dont tous les facteurs premiers sont supérieurs ou égaux à p. Soit pour m ≥ (r+1)ln2 / ln (p).
Remarque : si on désigne par m0 le plus petit entier m qui vérifie la majoration précédente, on peut en déduire que pour m < m0 il existe au moins un entier de Lr,m dont tous les facteurs premiers sont supérieurs ou égaux à p.
À titre d’exemple plaçons-nous dans I4. Pour p = 5 on trouve : m ≥ 2,15… ce qui donne m = 3 pour le plus petit entier vérifiant cette condition.
On se rapportera au Tableau 2 ci-dessus. Pour m = 2 on en déduit qu’il existe au moins un nombre dont tous les termes sont supérieurs ou égaux à 5, ce que confirme le nombre 5×5.
Toujours dans I4 et pour p = 7 on trouve : m ≥ 1,78 soit m ≥ 2. Nous laissons au lecteur le soin de trouver ce qu’il en résulte pour m.
Conclusion : l’ordre plutôt que le chaos
L’AGP a permis de révéler une structure. Les intervalles Ir apparaissent dans cet algorithme comme la cellule de fabrication d’une collection de nombres premiers Prqui n’interviennent jamais dans la formation des entiers de Ir et a fortiori dans les intervalles précédents. En revanche ils vont servir à engendrer les intervalles suivants : les entiers de longueur 2 de Ir+1, les entiers de longueur 3 de Ir+2 et ainsi de suite jusqu’à une longueur n dont le cardinal va se stabiliser. Par ailleurs chaque intervalle Ircomprend exactement r longueurs d’entiers qui sont engendrés de r à 2 respectivement par P1 ; P1 ∪ P2 ; ... ; P1 ∪ P2 …∪ Pr-1. Si bien que l’intervalle Ir apparaît aussi comme l’historique des nombres premiers construits avant lui. Il y a là un véritable mouvement d’horlogerie qui montre davantage l’ordre que le chaos. Si l’on considère la suite des nombres premiers donnés dans les tables, elle semble être régie par le hasard. Cela provient du fait, à notre avis, que la suite ordonnée des nombres entiers donne la priorité à la structure additive de N. Dans notre algorithme qui donne la priorité à la structure multiplicative qui définit les nombres premiers, un ordre nouveau apparaît avec des lois d’une rigoureuse précision. On voit que ce n’est plus le nombre premier seul, qu’il faut considérer mais la collection de ceux qui sont contenus dans chaque intervalle Ir. Ramener l’étude des nombres premiers de N à ceux des intervalles Ir, telle est la voie que nous proposons. L’encadrement entre des puissances de deux est essentiel. Il suffit de construire un algorithme avec comme encadrement des puissances de trois pour constater qu’il n’offre pas d’intérêt. On voit aussi que l’algorithme offre des perspectives dans le domaine du dénombrement et du même coup on retrouve le grand problème de la répartition des nombres premiers. L’étude des entiers de longueur 2, mis en évidence dans l’AGP, concerne les problèmes de cryptographie. Les nombres premiers de Mersenne ont une place privilégiée dans l’AGP. En effet le plus grand nombre de chaque intervalle Ir est 2r+1 - 1 et par conséquent tous les nombres premiers de Mersenne seront à cette place, ce qui n’est peut-être pas anodin. C’est sur ces perspectives que nous terminons cet article.
Bibliographie commentée
Jacques Bienvenu, "L'algorithme de génération des premiers (AGP)", Revue Tangente, n°108, 2006
Chris Caldwell, Site Web "The primes pages", http://primes.utm.edu/.
Un site fameux et très complet sur les nombres premiers.
Jean-Paul Delahaye, Merveilleux nombres premiers. Voyage au cœur de l'arithmétique. Éditions Belin/Pour la science, Paris, 2000.
Incontournable référence.
Gilles Godefroy, L’aventure des nombres, Editions Odile Jacob, 1997.
Une réflexion profonde sur la notion et l’histoire des nombres.
Andrew Grandville, "Nombres premiers et chaos quantique", 2002. En ligne http://smf4.emath.fr/Publications/Gazette/2003/97/smf_gaz...
Cet article fascinant et accessible porte sur des recherches récentes.
Edouard Lucas, Théorie des nombres, Gauthier-Villars, 1891, réédition Jacques Gabay, 1991.
Ouvrage historiquement très intéressant dans lequel on observe que toutes les questions ouvertes sur les nombres premiers posées en 1891 n’ont toujours pas été résolues.
M. Mendes France, G. Tenenbaum, Les nombres premiers. Que sais-je? vol. 571. Presses Universitaires de France, 1997.
Un classique.
[3] Le postulat conjecturé Joseph Bertrand en 1845 a été démontré pour la première fois en 1850 par Pafnouti Tchebychev. Une démonstration relativement simple a été publiée par Paul Erdös en 1932. Voir à ce sujet l'article de Wikipedia http://fr.wikipedia.org/wiki/Postulat_de_Bertrand
21:37 Publié dans L'Algorithme de Génération des Premiers | Lien permanent | Commentaires (0) | 
| 
del.icio.us | 
| 
Digg | 
Facebook