Ok

En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Ces derniers assurent le bon fonctionnement de nos services. En savoir plus.

06/12/2010

L'Algorithme de Génération des Premiers

L'Algorithme de Génération des Premiers (AGP)


         Jacques Bienvenu

        Professeur de mathématiques et Docteur ès lettres e-mail

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.

Version [pdf ] (1.07 Mo, 12 pages) 


   


SOMMAIRE
Bibliographie

Tableau Algorithme de Génération de Premiers
Version courte de l'article en anglais - The Prime-Generating Algorithm




Voici un nouvel algorithme dont le but n’est pas comme le crible d’Eratosthène de trouver les nombres premiers, mais qui permet de mieux comprendre la manière dont ils se forment. On l'appellera Algorithme de Génération des Premiers ou AGP. 



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.



Longueur d’un entier

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. 

Avec cette définition  les nombres premiers deviennent les nombres entiers de longueur 1. Il semble que la notion de longueur  ait existé sous la dénomination d’ordre  que nous avons rencontré dans un ancien traité d’arithmétique d’Edouard Lucas [2]. Toutefois, l’ordre au sens de longueur n’a pas eu en arithmétique la même fortune que celle de l’ordre de multiplicité des facteurs premiers. Aussi, prendrons-nous le terme de longueur qui évite toute confusion.

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 Eont 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 = [2; 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 




    La première remarque est que l’algorithme peut être considéré comme un crible. Ainsi pour trouver les nombres premiers de I4 il faut écrire tous les entiers de longueur 4, 3 et 2, puis on en déduit que les entiers de I4 qui n’ont pas été recensés par ce crible sont  ceux de longueur 1, c’est à dire les premiers. Certes, ce crible est moins commode pour le calcul que celui d’Eratosthène mais il est vraisemblable qu’il ne poserait pas de problème pour une programmation  avec ordinateur. Mais l’intérêt de l’algorithme est ailleurs. Commençons par quelques observations. Chaque Ir contient 2r éléments et l’intervalle suivant deux fois plus. Ir comporte exactement r longueurs d’entiers. Donc quand on passe d’un intervalle Ir au suivant, on augmente les longueurs de 1, et on obtient une nouvelle liste de nombres premiers. Le prix à payer pour gagner une longueur est donc de doubler le nombre de termes. Reportons nous au Tableau 1 de l’AGP et observons l’intervalle I4 : chaque longueur de I4 est engendré par des nombres premiers bien précis. La longueur 4 par 2 et 3 ; la longueur 3 par 2 ; 3 ; 5 ; 7, la longueur 2 par 2 ; 3 ; 5 ; 7  ; 11 ; 13. Les couleurs des cellules du Tableau 1ci-dessus illustrent qu’il en est de même pour les longueurs  5 ; 4 ; 3 de I5 et pour les longueurs 2 et 3 de I3.

    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, ≥ 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   <  2 r - m + 2.  

Si  2 r - m + 1 ≤     <  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    <  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 = 4 on a L4,4 engendrés par les premiers q < 2² soit  = 2 et = 3.

Pour m = 3 on a L4,3 engendrés par les premiers q < 23 soit  = 2 , q = 3, q = 5, q = 7.
 
Pour = 2 on a L4,2 engendrés par les premiers < 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 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  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.q2qm est un élément de Lr,m alors 2q1.q2qm 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'2q'm et  q'1.q'2q'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 ≥   2n +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  ≥  2+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 = 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 : ≥  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.





                     



[1]  Gilles Godefroy,  L’aventure des nombres, Editions Odile Jacob, 1997, p.133.
[2] Edouard Lucas, Théorie des nombres, Gauthier-Villars,1891, réédition Jacques Gabay,1991, p.382.

[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