Nombre de Mersenne premier

Soit n ∈ ${\displaystyle \mathbb {N} ^{*}}$ ; si n n'est pas premier, alors le n-ième nombre de Mersenne (M_n = 2ⁿ – 1) n'est pas premier. En effet :

• Si n = 1, alors M_n = 2¹ − 1 = 1.
• Si n = kl est composé, alors M_n = 2^kl − 1 est composé. En effet :
  • k > 1 et l > 1, donc kl > k, et donc 2^kl − 1 > 2^k − 1 > 1 ;
  • 2^kl − 1 = (2^k − 1)×(2^k(l−1) + 2^k(l−2) + ... + 2^k×2 + 2^k + 1).

Les deux plus petits exemples avec indices composés sont :
4 = 2 × 2, 6 = 2 × 3 sont composés, et M₄ = 2⁴ – 1 = 15 = 3 × 5, M₆ = 2⁶ – 1 = 63 = 3² × 7 sont bien composés.

Plus précisément :
2 divise 4, 6, et M₂ = 3 divise bien M₄ = 15, M₆ = 63.

Autrement dit (contraposée) :
Soit n ∈ ${\displaystyle \mathbb {N} ^{*}}$ ; si le n-ième nombre de Mersenne (M_n = 2ⁿ – 1) est premier, alors n est premier[2].

Les huit plus petits exemples sont :
M₂ = 2² − 1 = 3, M₃ = 2³ − 1 = 7, M₅ = 2⁵ − 1 = 31, M₇ = 2⁷ − 1 = 127, M₁₃ = 2¹³ − 1 = 8 191, M₁₇ = 2¹⁷ − 1 = 131 071, M₁₉ = 2¹⁹ − 1 = 524 287, M₃₁ = 2³¹ − 1 = 2 147 483 647 ( A000668) sont premiers, et 2, 3, 5, 7, 13, 17, 19, 31 ( A000043) sont bien premiers.

La réciproque est fausse. En effet :
Soit n ∈ ${\displaystyle \mathbb {N} ^{*}}$ ; même si n est premier, le n-ième nombre de Mersenne (M_n = 2ⁿ – 1) peut ne pas être premier.

Les trois plus petits contre-exemples sont :
11, 23, 29 ( A054723) sont premiers, mais M₁₁ = 2¹¹ − 1 = 2 047 = 23 × 89, M₂₃ = 2²³ − 1 = 8 388 607 = 47 × 178 481, M₂₉ = 2²⁹ − 1 = 536 870 911 = 233 × 1 103 × 2 089 ( A065341) sont composés[3].

Conséquences :
Pour trouver des nombres de Mersenne premiers, on sait déjà qu'il faut se limiter à des M_p avec p premier, mais que ce n'est pas suffisant. Il faut ensuite affûter les critères de sélection des nombres premiers p.

• Ils constituent la suite des répunits en base 2.
• Conséquence :
  Pour tous entiers m ≥ 1 et n ≥ 1, pgcd(M_m, M_n) = M_pgcd(m,n).
  En particulier, si m divise n, alors M_m divise M_n. Donc, si n n'est pas premier, alors M_n n'est pas premier.

Exemple :
pgcd(M₄, M₆) = pgcd(2⁴ – 1, 2⁶ – 1) = pgcd(15, 63) = 3 = 2² – 1 = M₂ = M_pgcd(4,6).

• Tous les nombres de Mersenne M_n ≥ 7, premiers ou composés, sont des nombres brésiliens. En effet :
  M_n = (111...111)₂ avec n fois la présence du chiffre 1 dans l'écriture en base 2.
  Le nombre 7 est d'ailleurs le plus petit nombre brésilien.
• D'après le test de primalité de Lucas-Lehmer pour les nombres de Mersenne, pour un nombre premier p impair, M_p est premier si et seulement si M_p divise S_p–1, où S₁ = 4 et pour tout n ≥ 1, S_n+1 = S_n² – 2.

Les six plus petits termes de cette suite de Lucas-Lehmer sont :
S₁ = 4, S₂ = 4² – 2 = 14, S₃ = 14² – 2 = 194, S₄ = 194² – 2 = 37 634, S₅ = 37 634² − 2 = 1 416 317 954, S₆ = 1 416 317 954² – 2 = 2 005 956 546 822 746 114 (voir la suite A003010 de l'OEIS).

(M₂ = 3 ne divise pas S₁ = 4 mais 2 est pair, et M₂ = 3 est bien premier.)
M₃ = 7 divise S₂ = 14 = 2 × 7, M₅ = 31 divise S₄ = 37 634 = 2 × 31 × 607, M₇ = 127 divise S₆ = 2 005 956 546 822 746 114 = 2 × 127 × 7 897 466 719 774 591, et M₃ = 7, M₅ = 31, M₇ = 127 sont bien premiers.
M₄ = 15 = 3 × 5 ne divise pas S₃ = 194 = 2 × 97, M₆ = 63 = 3² × 7 ne divise pas S₅ = 1 416 317 954 = 2 × 708 158 977, et M₄, M₆ sont bien composés[3].

• Si a divise M_p avec p premier impair, alors :${\displaystyle a\equiv 1{\pmod {2p}}\quad {\text{et}}\quad a\equiv \pm 1{\pmod {8}}.}$
• Un théorème d'Euler entraîne que pour q premier ≥ 5,
  M_q est premier si et seulement s'il existe un unique couple (x, y) d'entiers ≥ 1 tel que M_q = (2x)² + 3(3y)².

Exemples :
Pour M₅ = 31 : q = 5 est premier ≥ 5 ; (2 × 1)² + 3 (3 × 1)² = 31 ; ni x ni y ne peut diminuer, donc ni y ni x ne peut augmenter ; donc il existe un unique couple (x, y) d'entiers ≥ 1 tel que (2 x)² + 3 (3 y)² = 31 (à savoir (1, 1)) ; et M₅ = 31 est bien premier.
Pour M₁₁ = 2 047 : q = 11 est premier ≥ 5 ; 2 047 est impair et (2 x)² est pair, donc y doit être impair ; 2 047 − 3 (3 × 1)² = 2 020 = 2² × 5 × 101, 2 047 − 3 (3 × 3)² = 1 804 = 2² × 11 × 41, 2 047 − 3 (3 × 5)² = 1 372 = 2² × 7³, 2 047 − 3 (3 × 7)² = 724 = 2² × 181 ne sont pas des carrés, et 2 047 − 3 (3 × 9)² = –140 < 0 ; donc il n'existe aucun couple (x, y) d'entiers ≥ 1 tel que (2 x)² + 3 (3 y)² = 2 047 ; et M₁₁ = 2 047 = 23 × 89 n'est effectivement pas premier.

(Bas Jansen[4] a étudié M_q = x² + d·y² pour d compris entre 0 et 48.)

• Si q ≡ 3 (mod 4) est premier, alors :
  2q + 1 est aussi premier si et seulement si 2q + 1 divise M_q[5].

Exemples :
7 = 3 + 1 × 4, 7 est premier, 2 × 7 + 1 = 15 = 3 × 5 ne divise pas M₇ = 127, et 15 n'est effectivement pas aussi premier.
11 = 3 + 2 × 4, 11 est premier, 2 × 11 + 1 = 23 divise M₁₁ = 2 047 = 23 × 89, et 23 est effectivement aussi premier.

• Ramanujan a conjecturé (en 1913) que l'équation M_q = 6 + x², appelée équation de Ramanujan-Nagell, n'a que cinq solutions : (q, x) ∈ {(3, 1), (4, 3), (5, 5), (7, 11), (15, 181)} ; ce fut démontré par Trygve Nagell en 1948.
• La constante d'Erdős-Borwein ${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{2^{n}-1}}}$, définie comme la somme de la série des inverses des nombres de Mersenne (premiers ou non), est irrationnelle[6].

Marin Mersenne, moine de l'ordre des Minimes au début du XVII^e siècle, est l'auteur de la proposition : si M_n est premier, alors n aussi ; il l'aurait par ailleurs démontrée[7] - [8].

En 1732, Euler rappelle que la réciproque est fausse : M_p peut être composé alors que p est premier. Il donne le plus petit contre-exemple : 11 est premier mais M₁₁ = 2 047 = 23 × 89 ne l'est pas[9]; il mentionne que c'est aussi le cas pour p = 23, 83, 131, 179, 191, et 239[9].

En 1878, Édouard Lucas développe une méthode pour tester si un nombre de Mersenne M_p (avec p premier) est premier. Dans les années 1930, Derrick Lehmer l'améliore. Le test de primalité de Lucas-Lehmer pour les nombres de Mersenne est exceptionnellement simple comparativement à la taille des nombres considérés. Grâce à ce test très rapide, depuis longtemps les plus grands nombres premiers connus sont des nombres premiers de Mersenne.

Les quatre premiers nombres premiers de Mersenne sont connus dès l'Antiquité. Au XII^e siècle, Ibn Fallus donne une liste de nombres parfaits dans un commentaire de l'introduction à l'arithmétique de Nicomaque. On y trouve ceux correspondant aux cinquième, sixième, et septième nombres de Mersenne. Mais il ne fournit aucun calcul et sa liste comporte des erreurs, qui peuvent laisser penser qu'il s'est appuyé sur des hypothèses fausses ou insuffisantes, et n'a pas vérifié la primalité de ces nombres de Mersenne[10]. On trouve le cinquième (2¹³ – 1) dans un manuscrit anonyme daté de 1456 ou 1461. Les deux suivants (2¹⁷ – 1 et 2¹⁹ – 1) sont donnés par Pietro Cataldi en 1588. Au début du XVII^e siècle, Marin Mersenne fournit une liste des nombres premiers « de Mersenne » jusqu’à l'exposant 257, qui se révélera fausse : elle inclut par erreur 67 et 257, et omet 61, 89, et 107[11].

En 1750, Euler vérifie que 2³¹ – 1 est premier. Le suivant dans l'ordre chronologique (mais non numérique), 2¹²⁷ – 1, est trouvé par Lucas en 1876 ; puis 2⁶¹ – 1 est démontré premier par Ivan Pervouchine en 1883. Encore deux autres sont trouvés au début du XX^e siècle par R. E. Powers (en) en 1911 et en 1914.

La recherche des nombres premiers de Mersenne est révolutionnée par l'utilisation des calculateurs électroniques. La première identification d'un nombre de Mersenne par ce moyen a lieu à 22 heures le 30 janvier 1952 par un ordinateur SWAC à l'Institut d'Analyse Numérique (Institute for Numerical Analysis) du campus de l'université de Californie à Los Angeles, sous la direction de Derrick Lehmer, avec un programme écrit par Raphael Robinson.

C'est le premier nombre premier de Mersenne identifié depuis 38 ans. Le suivant est découvert moins de deux heures plus tard par le même ordinateur, qui en trouve trois de plus dans les mois suivants.

En décembre 2018, 51 nombres premiers de Mersenne sont connus, le plus grand étant M_82 589 933, qui est aussi à la même date le plus grand nombre premier connu[12]. Comme plusieurs de ses prédécesseurs, il est découvert par un calcul distribué sous l'égide du projet GIMPS, Great Internet Mersenne Prime Search (qui signifie « grande recherche par Internet de nombres premiers de Mersenne »).

Les nombres de Mersenne (premiers ou non) sont les répunits en base 2. La suite ${\displaystyle \left({\frac {b^{n}-1}{b-1}}\right)_{n\in \mathbb {N} ^{*}}}$ des répunits en base b est la suite de Lucas U(b + 1, b). Or toute suite de Lucas U(P, Q) avec P et Q premiers entre eux est à divisibilité forte. Par le même raisonnement que pour la suite des nombres de Mersenne (voir supra), une condition nécessaire (mais non suffisante) pour que le n-ième terme d'une telle suite soit premier est donc que n le soit également.

Les nombres premiers de Solinas[28] sont les nombres premiers de la forme p = f(2^k) où f est un polynôme unitaire à coefficients entiers[29] de faible « poids de réduction modulaire » (une condition technique destinée à ce que les calculs de réduction modulo p soient rapides et qui, pour simplifier, est parfois remplacée par : les coefficients non nuls de f sont peu nombreux et valent ±1[30] - [31] - [32]). Solinas[28] donne une série d'exemples, dont le premier est f(t) = t – 1, de « poids » 1 (qui correspond aux nombres de Mersenne) et le dernier est f(t) = t⁴ – t³ + t² + 1, de « poids » 4, mais qui inclut aussi f(t) = t^d – t^d–1 + t^d–2 – … + (–1)^d, de « poids » 3.

Puisque les nombres de Mersenne sont les répunits en base 2, leur écriture binaire ne comporte aucun 0. De manière analogue, on peut étudier dans les bases supérieures les nombres premiers dont l'écriture est dépourvue d'un certain chiffre[33]. Il a été prouvé en 2019 qu'il existe une infinité de nombres premiers dont le développement en base 10 ne comporte pas l'un quelconque des chiffres de 0 à 9[34].

• Liste de grands nombres
• Nombre de Fermat
• Nombre double de Mersenne
• Nouvelle conjecture de Mersenne
• Plus grand nombre premier connu
• Great Internet Mersenne Prime Search

• (en) Chris Caldwell, « Mersenne Primes: History, Theorems and Lists », sur Prime Pages
• (en) Bas Jansen, « Mersenne primes and class field theory », sur Université de Leyde (thèse, 2012, dir. Hendrik Lenstra)