Mersenne : 2ⁿ − 1 ne peut être premier que si n l’est, et la réciproque est fausse

Trois, sept, trente et un, cent vingt-sept. Ce sont des puissances de deux diminuées d’une unité, avec pour exposants deux, trois, cinq et sept, et ils sont tous premiers. Les exposants quatre et six, qui ne sont pas premiers, donnent quinze et soixante-trois, qui ne le sont pas non plus. Tout invite à lire une équivalence : l’exposant est premier si, et seulement si, le résultat l’est. Avec l’exposant onze, on obtient deux mille quarante-sept, qui vaut vingt-trois fois quatre-vingt-neuf. Un sens de l’équivalence est un théorème. L’autre est faux, et le XVII^e siècle s’y est trompé.

Cet article est le septième de la série Le peuple des nombres premiers, tirée de Mathématiques en terminales scientifiques (Tome 2). Il ne suppose que la définition d’un nombre premier, posée dans « Un nombre premier n’est pas “un nombre qu’on ne peut pas décomposer” », paru le 7 octobre, et le critère de la racine carrée, justifié dans l’article sur le crible d’Ératosthène. L’article à paraître le 21 octobre, « Euclide, Euler, et les nombres parfaits pairs », en aura besoin.

1. Une factorisation que l’on connaît déjà

Tout part d’une identité. Pour tout réel $a$ et tout entier $n\geq 2$ ,

$\displaystyle a^{n}-1=(a-1)\bigl(a^{n-1}+a^{n-2}+\cdots+a+1\bigr).$

On la vérifie en développant le membre de droite. Les produits par $a$ donnent $a^{n}+a^{n-1}+\cdots+a$ , les produits par $-1$ donnent $-a^{n-1}-\cdots-a-1$ , et tout se compense, sauf $a^{n}$ et $-1$ . Lorsque $a$ est entier, l’identité dit que $a-1$ divise $a^{n}-1$ .

Soient alors $a$ et $n$ deux entiers au moins égaux à $2$ , et supposons $a\geq 3$ . Le second facteur est au moins égal à $a+1$ , donc strictement supérieur à $1$ , et $a-1$ est un diviseur de $a^{n}-1$ compris entre $2$ et $a^{n}-1$ exclu. Le nombre $a^{n}-1$ n’est pas premier. En base dix, on le voit à l’œil nu : $10^{n}-1$ s’écrit avec $n$ chiffres $9$ et se divise par $9$ . La base $2$ est la seule pour laquelle le facteur $a-1$ vaut $1$ et ne gêne rien.

2. Pourquoi l’exposant doit être premier

Reste l’exposant. Supposons $n$ composé, c’est-à-dire $n=bc$ avec $b\geq 2$ et $c\geq 2$ . L’identité, appliquée au nombre $2^{b}$ et à l’exposant $c$ , donne

$\displaystyle 2^{n}-1=\bigl(2^{b}\bigr)^{c}-1=\bigl(2^{b}-1\bigr)\bigl(2^{b(c-1)}+2^{b(c-2)}+\cdots+2^{b}+1\bigr).$

Le premier facteur vaut au moins $2^{2}-1=3$ , le second au moins $2^{b}+1$ . Le nombre $2^{b}-1$ est donc un diviseur de $2^{n}-1$ distinct de $1$ et de $2^{n}-1$ , qui n’est pas premier. Les deux sections réunies donnent l’énoncé suivant.

Théorème. Soient $a$ et $n$ deux entiers au moins égaux à $2$ . Si $a^{n}-1$ est premier, alors $a=2$ et $n$ est premier.

L’argument fournit plus que ce qu’on lui demande. Chaque diviseur $b$ de l’exposant produit un diviseur $2^{b}-1$ du nombre. Pour $n=6$ , les diviseurs $2$ et $3$ donnent $3$ et $7$ , et en effet $63=3\times 21=7\times 9$ . Pour $n=10$ , les diviseurs $2$ et $5$ donnent $3$ et $31$ , et $1023=3\times 11\times 31$ .

3. La réciproque, et le nombre 2047

Le Tome 2 appelle nombre de Mersenne tout entier $M_{p}=2^{p}-1$ dont l’exposant $p$ est premier. La définition porte sur l’exposant, non sur le résultat : un nombre de Mersenne peut fort bien ne pas être premier. Le théorème dit que les nombres premiers de la forme $2^{n}-1$ sont à chercher parmi les nombres de Mersenne. Il ne dit pas qu’on les y trouve à tous les coups.

Les premières valeurs entretiennent pourtant l’illusion : $M_{2}=3$ , $M_{3}=7$ , $M_{5}=31$ et $M_{7}=127$ sont premiers. Pour $127$ , il suffit de constater que $\sqrt{127}<12$ et qu’aucun des nombres premiers $2$ , $3$ , $5$ , $7$ , $11$ ne le divise. Puis vient

$\displaystyle M_{11}=2^{11}-1=2047=23\times 89.$

L’erreur qu’on vient d’éviter a un nom. Du théorème « si $2^{n}-1$ est premier, alors $n$ est premier », on ne peut pas tirer « $n$ est premier, donc $2^{n}-1$ l’est ». Ce serait employer l’affirmation du conséquent, une règle de déduction qui n’existe pas, et dont l’article sur les règles de déduction a montré comment elle se déguise. Quatre cas favorables ne démontrent rien sur le cinquième.

La suite ne tranche pas davantage. Parmi les onze nombres premiers $p\leq 31$ , huit donnent un nombre de Mersenne premier : $2$ , $3$ , $5$ , $7$ , $13$ , $17$ , $19$ et $31$ . Les trois autres échouent : outre $M_{11}$ , on a $M_{23}=47\times 178481$ et $M_{29}=233\times 1103\times 2089$ .

4. Le Père Mersenne s’est trompé aussi

Marin Mersenne (1588–1648), religieux de l’ordre des Minimes et correspondant de presque tous les savants de son temps, affirme en 1644, dans ses Cogitata physico-mathematica, que $2^{n}-1$ est premier pour $n=2$ , $3$ , $5$ , $7$ , $13$ , $17$ , $19$ , $31$ , $67$ , $127$ et $257$ , et composé pour les autres exposants jusqu’à $257$ . Il ne dit pas comment il le sait. La liste contient cinq erreurs : $M_{67}$ et $M_{257}$ ne sont pas premiers, et $M_{61}$ , $M_{89}$ et $M_{107}$ le sont.

L’erreur sur $M_{67}$ a mis plus de deux siècles à se dévoiler. Édouard Lucas démontre en 1876 que ce nombre est composé, par une méthode qui n’en exhibe aucun diviseur. Il faut attendre 1903 pour que Frank Nelson Cole en donne la factorisation :

$\displaystyle 2^{67}-1=147573952589676412927=193707721\times 761838257287.$

La méthode de Lucas, perfectionnée au XX^e siècle, sert encore à tester les nombres de Mersenne. C’est elle qui a établi, en octobre 2024, la primalité de $2^{136279841}-1$ , un nombre de $41\,024\,320$ chiffres, alors le plus grand nombre premier connu et le cinquante-deuxième nombre de Mersenne premier recensé.

5. Où chercher les diviseurs d’un nombre de Mersenne

Les diviseurs trouvés plus haut ont un air de famille : $23=2\times 11+1$ , $89=8\times 11+1$ , $47=2\times 23+1$ . Le résultat qui l’explique ne figure pas dans le Tome 2 ; il emploie le petit théorème de Fermat, objet d’une note du blog, selon lequel $2^{q-1}\equiv 1\pmod q$ pour tout nombre premier impair $q$ .

Proposition. Soient $p$ un nombre premier impair et $q$ un nombre premier qui divise $M_{p}$ . Alors $q\equiv 1\pmod{2p}$ .

Démonstration. Le nombre $M_{p}$ est impair, donc $q$ l’est aussi. Comme $2^{p}\equiv 1\pmod q$ , il existe un plus petit entier $d\geq 1$ tel que $2^{d}\equiv 1\pmod q$ . Montrons d’abord que tout entier $m\geq 1$ vérifiant $2^{m}\equiv 1\pmod q$ est un multiple de $d$ . La division euclidienne donne $m=dk+r$ avec $0\leq r<d$ , puis $2^{m}=\bigl(2^{d}\bigr)^{k}\,2^{r}\equiv 2^{r}\pmod q$ , donc $2^{r}\equiv 1\pmod q$ ; par minimalité de $d$ , le reste $r$ ne peut être que nul.

Appliqué à $m=p$ , ce fait montre que $d$ divise $p$ , donc $d=1$ ou $d=p$ ; or $d=1$ voudrait dire que $q$ divise $2-1=1$ . Ainsi $d=p$ . Appliqué à $m=q-1$ , grâce au petit théorème de Fermat, il montre que $p$ divise $q-1$ . Enfin $q-1$ est pair et $p$ impair, donc $2p$ divise $q-1$ . $\quad\Box$

La proposition change la recherche d’un diviseur. Pour $M_{11}=2047$ , on a $45^{2}=2025$ et $46^{2}=2116$ : un diviseur premier inférieur à la racine carrée vaut au plus $45$ et est congru à $1$ modulo $22$ . Les candidats sont $23$ et $45$ , et $45$ n’est pas premier. Une seule division suffit. Pour $M_{13}=8191$ , la racine carrée est inférieure à $91$ , et les candidats congrus à $1$ modulo $26$ sont $27$ , $53$ et $79$ . Le premier n’est pas premier ; les divisions par $53$ et par $79$ laissent les restes $29$ et $54$ . Deux divisions établissent donc que $8191$ est premier, là où le crible en demandait vingt-quatre, une par nombre premier inférieur à $91$ .

6. Ce que l’on ignore

Personne ne sait s’il existe une infinité de nombres de Mersenne premiers. Plus surprenant, personne ne sait non plus s’il existe une infinité de nombres de Mersenne composés. On démontre, avec des outils qui dépassent ce fil et que nous admettons ici, que si $p\equiv 3\pmod 4$ et si $2p+1$ est premier, alors $2p+1$ divise $M_{p}$ : c’est le cas de $23$ pour $M_{11}$ et de $47$ pour $M_{23}$ . Il suffirait donc qu’il existe une infinité de tels couples $(p,\,2p+1)$ ; mais cela non plus, on ne le sait pas.

Les nombres de Mersenne premiers ont une autre vie, bien plus ancienne que Mersenne lui-même. Chacun d’eux fabrique un nombre parfait pair, et tout nombre parfait pair en provient. C’est l’objet de l’article à paraître le 21 octobre, « Euclide, Euler, et les nombres parfaits pairs ».

Le théorème de la section 2, la vérification de $M_{2}$ à $M_{7}$ et la factorisation de $M_{11}$ forment l’exercice Nombres de Mersenne des exercices d’approfondissement, section Familles de nombres entiers, de Mathématiques en terminales scientifiques (Tome 2), dont une note donne aussi la liste des exposants connus jusqu’à $5000$ . La liste de Mersenne et ses erreurs, la factorisation de $M_{67}$ , la forme des diviseurs de $M_{p}$ et la question des nombres de Mersenne composés n’y figurent pas et sont ajoutées ici.

Formalis Mathematica

Rigueur et formalisme au cœur de l’apprentissage et de l’enseignement des mathématiques

Mersenne : 2ⁿ − 1 ne peut être premier que si n l’est, et la réciproque est fausse

1. Une factorisation que l’on connaît déjà

2. Pourquoi l’exposant doit être premier

3. La réciproque, et le nombre 2047

4. Le Père Mersenne s’est trompé aussi

5. Où chercher les diviseurs d’un nombre de Mersenne

6. Ce que l’on ignore

Votre commentaire Annuler la réponse.

1. Une factorisation que l’on connaît déjà

2. Pourquoi l’exposant doit être premier

3. La réciproque, et le nombre 2047

4. Le Père Mersenne s’est trompé aussi

5. Où chercher les diviseurs d’un nombre de Mersenne

6. Ce que l’on ignore

Partagez :

Similaire

Votre commentaire Annuler la réponse.