Nombres de Mersenne

Eric Wegrzynowski

Les nombres de Mersenne sont les nombres de la forme

où n est un entier positif. Ce sont en particulier des nombres dont l'écriture en base 2 est constituée de n chiffres 1 (on les appelle des repunits en base 2).

Certains de ces nombres sont premiers (on les appelle alors nombres premiers de Mersenne). C'est le cas lorsque :

> M := 2^n-1:

> seq(M,n=[2,3,5,7]);

On connait actuellement 37 nombres premiers de Mersenne. Le plus grand d'entre eux est d'ailleurs le plus grand nombre premier connu aujourd'hui. Il s'agit de

dont l'écriture en base 10 comprend 909526 chiffres. Il a été découvert en janvier 1998.

Une condition nécessaire pour qu'un nombre de Mersenne soit premier est que l'exposant n soit lui meme premier. En effet, si l'exposant n n'est pas premier et est le produit de deux entiers p et q , alors est divisible par et par .

Il existe un test performant pour vérifier si un nombre de Mersenne est premier : le test de Lucas-Lehmer. Ce test s'appuie sur une condition nécessaire et suffisante de primalité de :

est premier si et seulement si il divise le terme de la suite définie par

> lucas := proc(n)

> local M,L,k;

> M := 2^n-1;

> L := 4;

> for k from 2 to n-1 do

> L := (L^2 - 2) mod M;

> od;

> evalb(L=0);

> end:

Quelques vérifications de primalité de nombres de Mersenne (avec temps de calculs sur Pentium II 400 Mhz)

Les résultats affichés indiquent dans l'ordre : le nombre de chiffres du nombre de Mersenne concerné, le résultat du test de Lucas, le temps de calcul en secondes.

> n := 2281: length(M); debut := time(): lucas(n); time()-debut;

> n := 3217: length(M); debut := time(): lucas(n); time()-debut;

> n := 4253: length(M); debut := time(): lucas(n); time()-debut;

> n := 4423: length(M); debut := time(): lucas(n); time()-debut;

> n := 9689: length(M); debut := time(): lucas(n); time()-debut;