Mersenne number

Partons de 1 et doublons cinq fois : 2, 4, 8, 16, 32. En retirant 1 au résultat, nous obtenons 31. Cette construction s'écrit 2⁵ − 1 : l'exposant 5 indique le nombre de facteurs 2.

Le nombre 31 est premier, car ses seuls diviseurs positifs sont 1 et 31. Il est donc un nombre premier de Mersenne. Toutefois, choisir un exposant premier ne garantit pas toujours que le nombre obtenu soit premier : cette seconde vérification est le cœur du problème.

Dans la convention de cette fiche, un nombre de Mersenne d'exposant premier p est l'entier noté M_p et défini par M_p = 2^p − 1. La lettre p désigne donc l'exposant, tandis que M_p désigne la valeur obtenue.

Si M_p est lui-même premier, on parle de nombre premier de Mersenne. La primalité de p est une condition nécessaire, mais elle ne suffit pas : avec p = 11, on obtient 2¹¹ − 1 = 2047 = 23 × 89.

Pour un exposant premier impair p, le test de Lucas–Lehmer part du nombre s₀ = 4 et répète s_i+1 = s_i² − 2, en ne conservant que le reste modulo M_p. Après p − 2 termes calculés à partir de s₀, M_p est premier exactement lorsque s_p−2 est congru à 0 modulo M_p. Le cas p = 2, qui donne M₂ = 3, se vérifie séparément.

Vérifions que le nombre de Mersenne d'exposant p = 5 est premier. Sa valeur est M₅ = 2⁵ − 1 = 31, et le test de Lucas–Lehmer demande le terme d'indice p − 2 = 3.

1. Partons de s₀ = 4. Le terme suivant vaut s₁ = 4² − 2 = 14.

2. Calculons s₂ = 14² − 2 = 194. Comme 194 = 6 × 31 + 8, son reste modulo 31 est 8. Nous pouvons donc poursuivre avec 8.

3. Calculons s₃ = 8² − 2 = 62. Le reste de 62 dans la division par 31 est 0. La figure récapitule ces trois passages et met en évidence le reste final nul.

4. Puisque s₃ ≡ 0 modulo 31, le test conclut que M₅ = 31 est premier.

5. Contrôlons ce petit cas autrement. Un diviseur premier de 31 qui serait différent de 31 ne pourrait dépasser √31, qui est inférieur à 6. Or 31 n'est divisible ni par 2, ni par 3, ni par 5. Ce contrôle confirme le verdict.

Pour produire de petits candidats, choisissez un exposant premier p, calculez 2^p, puis retirez 1. Les premiers essais donnent M₂ = 3, M₃ = 7, M₅ = 31 et M₇ = 127.

Il reste ensuite à tester la valeur obtenue. Pour un petit entier, la recherche de diviseurs suffit ; pour un grand candidat de Mersenne à exposant premier impair, le test de Lucas–Lehmer exploite directement sa forme particulière.

Pendant le test, remplacez chaque grand terme par son reste modulo M_p. Cette réduction ne change pas le reste final et empêche les nombres intermédiaires de croître inutilement, comme dans le passage de 194 à 8 pour M₅ = 31.

Exposant premier et valeur première. Dans M_p = 2^p − 1, la lettre p est l'exposant. Dire que p est premier ne dit pas encore que M_p l'est : p = 11 conduit au nombre composé 2047.

Nombre de Mersenne et nombre de Fermat. Un nombre de Mersenne a une puissance de 2 diminuée de 1. Un nombre de Fermat a la forme 2²ⁿ + 1, pour un entier naturel n : le signe et la structure de l'exposant diffèrent.

Test spécialisé et test général. Lucas–Lehmer est adapté aux nombres de Mersenne. Un test de primalité général traite des entiers sans supposer qu'ils s'écrivent 2^p − 1.

Le cas p = 2. Il donne M₂ = 3, qui est premier, mais la récurrence de Lucas–Lehmer formulée pour les exposants premiers impairs ne s'y applique pas telle quelle. Ce cas initial se vérifie directement.

Une condition nécessaire n'est pas suffisante. L'exposant 11 est premier, mais M₁₁ = 2047 = 23 × 89. L'étape « p est premier » élimine des exposants, sans certifier le candidat restant.

Deux infinitudes non démontrées. On ne sait pas prouver qu'il existe une infinité de nombres premiers de Mersenne. On ne sait pas davantage prouver qu'il existe une infinité d'exposants premiers donnant un nombre de Mersenne composé.

Des repères historiques, pas un compteur en direct. Les listes et records datés de la définition de référence documentent l'histoire de la recherche. Leur formulation ne doit pas être interprétée comme un décompte actualisé en temps réel.

test de Lucas–Lehmer — Approfondir la suite récurrente qui décide la primalité d'un candidat de Mersenne.

nombre premier — Revoir les diviseurs, la compositivité et la place des familles particulières de nombres premiers.

nombre de Fermat — Comparer une autre famille construite à partir de puissances de 2, avec un signe plus et un exposant d'une forme différente.