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 : 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
Ceci est facile à voir du fait que m et n
n’ont aucun facteur commun autre que 1. Les fonctions
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 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
alors
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 Plaçons nous dans le corps Soit x un élément non nul de Continuons : Mais u n’est pas nul modulo q, sinon on
aurait On a alors Etape 2 : on suppose Nous avons besoin de plusieurs résultats dans le corps * -1 n’est pas un carré modulo Mp :
* 2 est un carré et une puissance quatrième modulo
Mp : d’après le petit théorème de Fermat, * 3 n’est pas un carré modulo Mp :
prenons les trois nombres consécutifs Soit g un générateur du groupe multiplicatif des
éléments non-nuls de Considérons Calculons maintenant * On cherche une racine carrée de v : soit
ce qui donne
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 3 n’est pas un carré modulo Mp et Comme dans la première partie, l’ordre des éléments de Concluons : |