Nombres parfaits, nombres de Mersenne et test de Lucas-Lehmer

Les nombres parfaits sont les nombres égaux à la somme de leurs diviseurs autres que eux-mêmes comme 6 ou 28. Euclide montre que si 2^p – 1 et p sont premiers alors 2^p–1(2^p – 1) est parfait. Euler a démontré la réciproque : un nombre parfait pair est de la forme 2^p–1(2^p – 1).

Prenons un nombre quelconque constitué de r facteurs premiers à des puissances diverses :  ; pour avoir un diviseur de n on peut choisir une puissance de p₁ de  manières (+1 pour la puissance 0), une puissance de p₂ de  manières … donc au final on a   diviseurs possibles. La somme des diviseurs est alors

puisque si on développe le membre de gauche on aura tous les produits possibles sans aucune répétition de tous les termes primaires de n. Remarquons que si pgcd(m, n)=1 alors

 et .

Ceci est facile à voir du fait que m et n n’ont aucun facteur commun autre que 1. Les fonctions  et  sont des fonctions multiplicatives. Montrer qu’un nombre P est parfait revient donc à montrer que

.

Revenons aux nombres parfaits en prenant n=2^p – 1 premier ainsi que p :

la somme des diviseurs de 2^p – 1 est la somme des termes 2ⁱ  et la somme des diviseurs de

2^p –1  est 1+(2^p – 1)=2^p . En enlevant n, on a bien un nombre parfait.

Réciproquement prenons un nombre parfait pair P, de la forme q2^n–1  avec q impair et n>1 ; 2^n–1   et q sont premiers entre eux donc

,

mais comme P est parfait, on doit avoir

.

2ⁿ– 1 est impair donc divise q, soit q=(2ⁿ– 1)r  ou encore q+r=2ⁿ– 1 qui est inférieur ou égal à  .

On a donc

 ;

l’inégalité du début est donc une égalité et =q+r, par conséquent q et r sont les seuls diviseurs de q ; conclusion r=1, q est premier, vaut 2ⁿ– 1 et P = 2^n–1(2ⁿ – 1) avec n et 2ⁿ – 1 premiers (en fait si 2ⁿ – 1 est premier, n l’est aussi mais la réciproque est fausse…trouvez un contre-exemple).

Ceci amène à plusieurs questions :

* y-a-t’il des nombres parfaits impairs ? on n’en connaît aucun alors qu’il n’y a à priori aucune raison qu’il n’y en ait pas… la conjecture est donc : « il n’y a pas de nombre parfait impair » !

* quels sont les nombres de la forme 2ⁿ– 1 premiers ? ce sont les nombres de Mersenne dont on a conjecturé qu’ils étaient une infinité et font l’objet d’actives recherches car ils permettent de produire les très grands nombres premiers indispensables en cryptographie.

Attention, les nombres de Mersenne ne sont pas tous premiers !

Edouard Lucas (1842 – 1891) a trouvé le test suivant permettant de vérifier si on a un nombre de Mersenne premier ; ce test a été amélioré par Derrick Lehmer dans les années 30 : on prend la suite définie par

,  (on peut changer la valeur initiale),

alors

 est premier si et seulement si M_p divise  (ou ).

Quelques exemples réalisés avec Maple :

> restart;

> M := 2^n-1:seq(M,n=[2,3,5,7,11,13,17]);

# on calcule les premiers Mersenne

> 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;

#procédure de calcul, renvoie true si le test est bon, false

#sinon, calcule également le temps mis pour le calcul.

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

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

Pour les détails sur les nombres de Mersenne, voir

      http://fr.wikipedia.org/wiki/Nombre_premier_de_Mersenne

Le projet de recherche des nombres premiers de Mersenne, GIMPS

      http://www.mersenne.org/french_prime.htm

Un cours assez complet

      http://algo.inria.fr/banderier/Recipro/node1.html de http://www-lipn.univ-paris13.fr/~banderier/

Date un peu mais amusant http://www.fatrazie.com/nb_premiers.htm

Et évidemment http://mathworld.wolfram.com/MersennePrime.html

ainsi que http://mathworld.wolfram.com/Lucas-LehmerTest.html

La démonstration se fait en deux temps : si  alors  est premier, puis la réciproque.

Etape 1 : posons  et , alors  ; supposons que ,  à déterminer avec , on calcule : , or  donc  et , soit .

On a donc  (si on démarre avec une autre valeur de s₀, il suffit de prendre u et v de sorte que ).

Le raisonnement va consister à trouver une contradiction au fait que M_p n’est pas premier : supposons que  soit divisible par M_p , lui-même divisible par q premier et , alors  est divisble par q.

Plaçons nous dans le corps ,  contient évidemment , avec égalité lorsque  est un carré modulo q. Dans  il y a q² éléments ou q, et les éléments non-nuls sont au nombre de  ou .

Soit x un élément non nul de , il existe un plus petit nombre positif d, appelé ordre de x, tel que  et divise  ou  (en fait comme  divise , on peut ne pas s’occuper de ce cas et donc ne pas s’inquiéter de ce que  soit un carré modulo q ou non).

Continuons :  est divisible par q donc  mais comme , on a .

Mais u n’est pas nul modulo q, sinon on aurait  ce qui est impossible sauf si q = 1, si bien que  . L’ordre de v doit donc diviser  qui est une puissance de 2 ; or tout nombre divisant strictement  divise  : si l’ordre de v était plus petit que  alors on aurait  et non , moralité l’ordre de v est bien .

On a alors  et  divise , soit  puisqu’on avait supposé que  ; il y a bien contradiction.

Etape 2 : on suppose  premier ; si on montre que  alors on aura .

Nous avons besoin de plusieurs résultats dans le corps  :

* -1 n’est pas un carré modulo M_p :  est divisible par 2 mais pas par 4,  est impair et  ou -1 n’est pas un carré.

* 2 est un carré et une puissance quatrième modulo M_p : d’après le petit théorème de Fermat,  et  ; on en tire  et  (à condition évidemment que ).

* 3 n’est pas un carré modulo M_p : prenons les trois nombres consécutifs ,  et  ; un des trois doit être divisible par 3 :  est premier et  est une puissance de 2 donc 3 doit diviser .

Soit g un générateur du groupe multiplicatif des éléments non-nuls de  : ce groupe est cyclique et a  éléments et les différentes puissances de g représentent tous les éléments de .

Considérons , racine cubique (par exemple les racines cubiques de 1 dans  sont 5 et 25). non-triviale de 1, soit une solution de l’équation , et donc de .

Calculons maintenant  ; -3 est donc un carré alors que -1 n’en est pas un, conclusion : 3 n’est pas un carré puisque .

*  a une racine carrée mais pas de racine quatrième : comme 3 n’est pas un carré, nous avons , ce qui donne  (dans le développement du binôme l’exposant apparaît dans tous les termes sauf le premier et le dernier, donc ).

On cherche une racine carrée de v : soit

,

ce qui donne  ; comme on a  et , on peut écrire . De toutes manières comme 2 a une racine quatrième, pour que v en ait une, il faudrait que  ait une racine carrée et soit donc un carré. Comme précédemment on a le système  d’où l’on tire

 ;

2 est un carré mais -1 n’en est pas un donc -2 n’est pas un carré et on ne peut trouver a et b.

* La démonstration maintenant : 3 n’est pas un carré mod M_p donc  a  éléments (il est évidemment sous-entendu que  est ici une solution de l’équation ). Les nombres u et v sont représentés dans  par  et  qui satisfont toujours  et  ; par récurrence on a .

3 n’est pas un carré modulo M_p et  ; avec Fermat, on a , on obtient donc , soit .

Comme dans la première partie, l’ordre des éléments de  divise  ;  est impair et l’ordre de v est une puissance de 2 divisant  : on peut alors trouver un élément de  qui est une racine carrée de v mais qui n’a pas de racine carrée lui-même ; cet élément a alors pour ordre  et v a pour ordre .

Concluons : , ce qui achève la réciproque.