Arithmétique

Les nombres premiers de Mersenne

2 − 1, 4 − 1, 8 − 1, 16 − 1… Retirer 1 à une puissance de 2 donne parfois un nombre premier. Ces nombres, étudiés par le moine Marin Mersenne en 1644, détiennent presque tous les records du plus grand nombre premier connu. Pourquoi eux ? Cinq planches pour le comprendre, chaque chiffre étant recalculé par la page.

Un nombre qui ne s'écrit qu'avec des 1

Un nombre de Mersenne est un nombre de la forme M_n = 2ⁿ − 1. En base deux, la base des ordinateurs, il s'écrit simplement avec n chiffres 1 : 2⁵ − 1 = 31 s'écrit 11111. Un nombre premier de Mersenne est un M_n qui est premier, c'est-à-dire divisible seulement par 1 et par lui-même.

Animation : les nombres 2ⁿ − 1 défilent, n = 2 à 32. Rouge : M_n est premier. Orange : n est premier mais M_n ne l'est pas. Gris : n n'est pas premier. La factorisation affichée est calculée à chaque passage.

Tableau calculé par la page : les dix premiers exposants premiers p, la valeur de M_p et son statut (test de Miller-Rabin déterministe, exact pour des nombres de cette taille).

Pourquoi l'exposant doit-il être premier ?

L'idée : si l'on peut couper la rangée de n chiffres 1 en paquets égaux de a chiffres, alors M_n est divisible par 11…1 (a fois), c'est-à-dire par M_a. En formule, si n = a × b :

2^ab − 1 = (2^a − 1) × (1 + 2^a + 2^2a + … + 2^(b−1)a)

Choisissez n, puis la taille a des paquets parmi les diviseurs de n. La figure pose l'addition en colonnes : b paquets de a uns, décalés, qui reconstituent exactement les n uns.

exposant n12

taille des paquets a

En bleu et violet (alternés) : les copies de M_a décalées de a rangs ; en vert : leur somme, qui est M_n. Aucune retenue n'apparaît, car les paquets ne se chevauchent pas.

Carte des exposants n = 1 à 60 (cliquez une case pour la choisir). Gris : n composé, donc M_n composé d'après la figure du haut. Orange : n premier mais M_n composé. Rouge : M_n premier. Chaque case est testée par Miller-Rabin.

M_n = 2ⁿ − 1—

Nombre de chiffres décimaux—

M_a (un paquet)—

Quotient M_n ÷ M_a et reste—

Contrôle : M_a × quotient − M_n—

Verdict sur M_n—

À retenir. Si n n'est pas premier, M_n ne l'est pas non plus : la rangée de 1 se découpe. Il ne reste donc que les exposants premiers p à examiner. Mais la réciproque est fausse : n = 11 est premier et pourtant M₁₁ = 2 047 n'est pas premier. C'est l'objet de la planche suivante.

Un exposant premier ne suffit pas : la chasse aux diviseurs

Pour savoir si M_p est premier, on peut chercher un diviseur. Heureusement, Fermat (1640) et Euler (1750) ont montré que ses diviseurs premiers ne sont pas quelconques : tout diviseur premier q de M_p (p premier impair) est de la forme

q = 2kp + 1 (k entier) et q ≡ 1 ou 7 (modulo 8).

Au lieu d'essayer tous les nombres impairs, on n'essaie que ces candidats. Pour chacun, on ne divise même pas M_p : on calcule 2^p modulo q (le reste de 2^p dans la division par q), par élévations au carré successives. Si ce reste vaut 1, alors q divise 2^p − 1.

exposant premier p

En haut, les 48 premiers candidats k = 1 à 48, examinés un à un. Gris : écarté car q n'est pas ≡ 1 ou 7 mod 8. Orange : q n'est pas premier. Bleu : testé, 2^p mod q ≠ 1. Rouge : diviseur trouvé. En bas, la recherche complète sur une échelle logarithmique : la zone balayée (bleu), les facteurs trouvés (rouge) et la ligne d'arrêt √(reste) (vert), qui recule chaque fois qu'un facteur est retiré.

Facteurs premiers trouvés—

Contrôle : produit des facteurs = M_p ?—

Dernier cofacteur et son statut—

Candidats k examinés / vraiment testés—

Nombres impairs qu'il aurait fallu essayer—

Contrôle des formes 2kp + 1 et ±1 mod 8—

À retenir. M₁₁ = 23 × 89 : les deux facteurs sont bien 2·1·11 + 1 et 2·4·11 + 1. Choisissez p = 67 : en 1903, Frank Cole monta au tableau sans un mot, calcula 2⁶⁷ − 1, puis 193 707 721 × 761 838 257 287, et obtint le même nombre. Il avoua avoir passé « trois années de dimanches » sur ce calcul ; la page le refait en un instant (k = 1 445 580). Mais pour M₆₁, qui est premier, il faut balayer tous les candidats jusqu'à √M₆₁ : la division d'essai devient vite impraticable.

Le test de Lucas-Lehmer : prouver sans chercher de diviseur

Édouard Lucas (1876), puis Derrick Lehmer (1930), ont trouvé un test qui dit si M_p est premier sans chercher un seul diviseur. On part de s₀ = 4 et on répète « élever au carré, retirer 2, garder le reste modulo M_p » :

s_k+1 = (s_k² − 2) mod M_p M_p est premier ⇔ s_p−2 = 0

Seulement p − 2 carrés, au lieu de milliards de divisions. Autre cadeau : diviser par M_p ne coûte rien en binaire, car 2^p ≡ 1 : il suffit de couper le nombre en tranches de p bits et de les additionner. La figure montre chaque s_k en binaire, une ligne par étape.

exposant premier p127

Ligne k = valeur de s_k écrite sur p bits (bit 1 en bleu, bit 0 en blanc). Les lignes ressemblent à du bruit… jusqu'à la dernière, encadrée en vert si elle est entièrement nulle (M_p premier), en rouge sinon.

Verdict de Lucas-Lehmer—

Premières valeurs s₀, s₁, s₂…—

Contrôle : réduction par tranches contre division exacte—

Contrôle indépendant : test de Miller-Rabin—

Proportion de bits à 1 (lignes 0 à p − 3)—

Coût comparé à la division d'essai—

À retenir. Lucas prouva à la main en 1876 que M₁₂₇ (39 chiffres) est premier : ce record de taille dura 75 ans. Le test est si simple qu'il fait des nombres de Mersenne les meilleurs candidats aux records. Essayez p = 11 ou p = 67 : le test dit « composé » sans donner aucun facteur — il prouve sans exhiber.

Les nombres parfaits, cousins des premiers de Mersenne

Un nombre est parfait s'il est égal à la somme de ses diviseurs autres que lui-même : 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14. Euclide a montré que si M_p est premier, alors N = 2^p−1 × M_p est parfait ; Euler a démontré deux mille ans plus tard que tous les nombres parfaits pairs sont de cette forme.

N = 2^p−1(2^p − 1) = 1 + 2 + 3 + … + M_p

premier de Mersenne M_p, p =5

N est un nombre triangulaire : M_p rangées de 1, 2, 3… points. Au-delà de 127 rangées, le triangle est dessiné plein.

En haut, N en binaire : p uns suivis de p − 1 zéros. En bas, la balance : les diviseurs propres de N mis bout à bout — les puissances de 2 en bleu, les multiples de M_p en rouge — remplissent exactement la barre de longueur N.

Nombre parfait N—

Contrôle : somme des diviseurs propres − N—

Contrôle : 1 + 2 + … + M_p − N—

Somme des cubes impairs 1³ + 3³ + … − N—

Où sont les nombres parfaits ? Le crible des diviseurs

Pour chaque entier n, on calcule σ(n), la somme de tous ses diviseurs, par un crible jusqu'à un million. Un nombre est parfait si σ(n)/n = 2 exactement, abondant au-dessus, déficient en dessous.

afficher jusqu'à n =10 000

σ(n)/n pour chaque n (abscisse logarithmique). Bleu : déficients ; orange : abondants ; rouge : parfaits, posés exactement sur la ligne verte σ(n)/n = 2.

Nombres parfaits ≤ 1 000 000 trouvés par le crible—

Contrôle : chacun est-il de la forme d'Euclide ?—

Proportion de nombres abondants—

Premier nombre impair abondant—

À retenir. Chaque nouveau premier de Mersenne donne un nouveau nombre parfait, et réciproquement pour les pairs : il y a donc exactement autant de nombres parfaits pairs connus que de premiers de Mersenne, 52. Existe-t-il un nombre parfait impair ? Personne ne le sait : le crible n'en trouve aucun, et l'on sait qu'il en faudrait un de plus de 1 500 chiffres.

Les géants : 52 premiers connus, et après ?

On ne sait toujours pas s'il existe une infinité de premiers de Mersenne. Mais une conjecture de Lenstra, Pomerance et Wagstaff prédit leur rythme : en moyenne, chaque exposant devrait être environ 1,476 fois le précédent, soit log₂ p qui croît de e^−γ ≈ 0,5615 par rang (γ = 0,5772… est la constante d'Euler). Trois volets pour confronter cette prédiction aux faits.

Chaque point est un premier de Mersenne connu : en abscisse son rang, en ordonnée log₂ p (le nombre de chiffres binaires de l'exposant). Si la conjecture est juste, les points s'alignent sur une droite de pente 0,5615.

ajuster à partir du rang1

Points bleus : les 52 exposants (le dernier, 136 279 841, en rouge). Droite bleue en tirets : ajustement par moindres carrés ; droite verte : pente prédite e^−γ, passant par le même point moyen.

Pente mesurée (moindres carrés)—

Pente prédite e^−γ—

Rapport moyen entre exposants successifs—

Nombre attendu jusqu'à p = 136 279 841—

La page applique le test de Lucas-Lehmer à tous les exposants premiers jusqu'à 2 300, sans rien savoir d'avance, puis compare ce qu'elle trouve à la liste historique… et à la liste publiée par Mersenne lui-même en 1644.

Chaque trait est un exposant premier p testé (abscisse logarithmique) : gris si M_p est composé, rouge et plus haut s'il est premier. La bande orange marque la liste de Mersenne (p ≤ 257).

Exposants testés—

Premiers de Mersenne trouvés—

Contrôle : accord avec la liste historique—

La liste de Mersenne (1644) jugée par le calcul—

Comment connaître les premiers et les derniers chiffres d'un nombre de 41 millions de chiffres sans l'écrire ? Les derniers : on calcule 2^p modulo 10²⁰. Les premiers : on prend la partie fractionnaire de p × log₁₀ 2, calculé ici avec 70 décimales exactes.

premier de Mersenne

Nombre de chiffres décimaux—

20 premiers chiffres—

20 derniers chiffres—

Contrôle par le calcul exact du nombre entier—

Imprimé à 4 800 chiffres par page—

Rang et découverte—

Taille des records (nombre de chiffres, échelle logarithmique) selon l'année de découverte. Droite en tirets : tendance depuis 1952, l'ère des ordinateurs. Le nombre choisi est entouré en rouge.

Tendance mesurée depuis 1952—

À retenir. — Les points suivent la droite prédite sans la coller : les trous et les grappes (89, 107, 127 ; ou 2 203 et 2 281) sont ceux d'un hasard régulier en moyenne. Si la conjecture dit vrai, il y a une infinité de premiers de Mersenne, mais de plus en plus espacés.

Repères historiques

vers −300 — Euclide, Éléments, livre IX : si 1 + 2 + 4 + … + 2^p−1 est premier, son produit par 2^p−1 est parfait.

1588 — Pietro Cataldi vérifie que M₁₇ et M₁₉ sont premiers.

1640 — Fermat, dans une lettre à Mersenne : les diviseurs de M_p sont de la forme 2kp + 1.

1644 — Marin Mersenne, Cogitata physico-mathematica : M_n serait premier pour n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 et pour aucun autre n ≤ 257. La liste contient des erreurs (planche 5).

1772 — Euler prouve que M₃₁ = 2 147 483 647 est premier, record pendant un siècle.

1876 — Édouard Lucas prouve que M₁₂₇ est premier ; record jusqu'en 1951.

1903 — Frank Cole factorise M₆₇ devant l'American Mathematical Society.

1930 — Derrick Lehmer met le test de Lucas sous sa forme définitive.

1952 — Raphael Robinson programme le SWAC : M₅₂₁, M₆₀₇, M₁₂₇₉, M₂₂₀₃, M₂₂₈₁ en une année.

1996 — Lancement du GIMPS, recherche collaborative sur les ordinateurs de volontaires : il a trouvé tous les records depuis.

2024 — Luke Durant, sur des processeurs graphiques loués dans le nuage, trouve M_136279841 : 41 024 320 chiffres, le plus grand nombre premier connu à ce jour.

En résumé

Une forme qui trie

2ⁿ − 1 ne peut être premier que si n l'est (planche 1), et ses diviseurs éventuels ont la forme 2kp + 1 (planche 2). La forme élimine d'emblée l'immense majorité des cas.

Un test imbattable

Lucas-Lehmer prouve la primalité en p − 2 élévations au carré, et la réduction modulo 2^p − 1 est gratuite en binaire (planche 3). Voilà pourquoi les records sont des nombres de Mersenne.

Un mystère intact

Une infinité de premiers de Mersenne ? De nombres parfaits ? Un parfait impair ? Les calculs s'accordent avec les conjectures (planches 4 et 5), mais aucune n'est démontrée.

Pour aller plus loin

Pourquoi les diviseurs ont la forme 2kp + 1. Si q premier divise 2^p − 1, l'ordre de 2 modulo q (le plus petit exposant e tel que 2^e ≡ 1) divise p, donc vaut p. Il divise aussi q − 1 (petit théorème de Fermat), donc p divise q − 1, et q − 1 étant pair, q = 2kp + 1. De plus 2 = (2^(p+1)/2)² est un carré modulo q, ce qui impose q ≡ ±1 mod 8.

Pourquoi Lucas-Lehmer marche. On pose ω = 2 + √3 ; alors s_k = ω^{2^k} + ω^{−2^k}. Le test revient à vérifier que ω a l'ordre maximal 2^p dans un anneau construit sur M_p, ce qui n'est possible que si M_p est premier.

Les records en pratique. Pour un exposant de 136 millions, chaque carré porte sur des nombres de 136 millions de bits : on le calcule par transformée de Fourier rapide. Le GIMPS ajoute un premier tri par division d'essai (planche 2) et par la méthode p − 1 de Pollard, puis un test de Fermat probabiliste muni d'une preuve vérifiable, et enfin Lucas-Lehmer pour confirmer.

Questions ouvertes. Infinité des premiers de Mersenne ; infinité des M_p composés à exposant premier ; existence d'un M_p qui serait divisible par le carré d'un nombre premier ; existence d'un nombre parfait impair.