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.
| 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×3×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 2
r
é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 1
ci-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
= [2
r ; 2
r+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 2
m-1q ≥
2
r+1.
Or 2
m-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 2
x.
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 2
n.
[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 < 2
E(
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
=
[ 2
4 ; 2
5[ :
| 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
<
2
3
soit
q =
2 ,
q = 3,
q = 5,
q = 7.
Pour
m =
2 on a
L4,2
engendrés par les premiers
q < 2
4
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 L
r,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
< 2
3.
Théorème
3
Pour
m ≥
(
r+1)
ln2 /
ln3 tous
les entiers de
Lr,m
sont pairs.
Preuve
En effet, 3
m
est le plus petit entier de longueur
m qui
n’est pas pair. Donc pour 3
m ≥
2
r+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 L
r
+ n, m + n sont pairs.
Montrons à présent que, lorsque les entiers
de L
r,m
sont pairs, card (
Lr,m)=
card (
Lr + 1, m+1).
Si
q1.q2…
qm
est un
élément de
Lr,m alors 2
q1.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 L
r,m.
Donc les entiers de
Lr + 1, m+1
sont tous les entiers 2
n
tels que
n
soit entier de L
r,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 3
n+1
≥
2
r +
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 ≥ 2
r +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
Pr
qui 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
Ir
comprend 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 2
r+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_gazette_97_29-44.pdf
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.