Nombres parfaits, nombres de Mersenne et test de Lucas-Lehmer 1. Nombres parfaits et nombres de MersenneLes nombres parfaits sont les nombres égaux à la somme de leurs diviseurs autres que eux-mêmes comme 6 ou 28. Euclide montre que si 2p – 1 et p sont premiers alors 2p–1(2p – 1) est parfait. Euler a démontré la réciproque : un nombre parfait pair est de la forme 2p–1(2p – 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 p1 de manières (+1 pour la puissance 0), une puissance de p2 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=2p – 1 premier ainsi que p :
la somme des diviseurs de 2p – 1 est la somme des termes 2i et la somme des diviseurs de 2p –1 est 1+(2p – 1)=2p . En enlevant n, on a bien un nombre parfait. Réciproquement prenons un nombre parfait pair P, de la forme q2n–1 avec q impair et n>1 ; 2n–1 et q sont premiers entre eux donc , mais comme P est parfait, on doit avoir . 2n– 1 est impair donc divise q, soit q=(2n– 1)r ou encore q+r=2n– 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 2n– 1 et P = 2n–1(2n – 1) avec n et 2n – 1 premiers (en fait si 2n – 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 2n– 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 ! 2. Test de Lucas-LehmerEdouard 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 Mp 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 s0, il suffit de prendre u et v de sorte que ). Le raisonnement va consister à trouver une contradiction au fait que Mp n’est pas premier : supposons que soit divisible par Mp , 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 q2 é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 Mp : 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 Mp : 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 Mp : 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 Mp 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 Mp 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. |