Extrait de la p. 316 du mémoire Théorie des fonctions numériques simplement périodiques d'Édouard Lucas (1878).
En mathématiques, le test de Lucas-Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon notable par Derrick Henry Lehmer dans les années 1930, grâce à son étude des suites de Lucas[1],[2].
Les premiers termes de cette suite sont 4, 14, 194, etc. (suite A003010 de l'OEIS).
Soit p un nombre premier différent de 2. Le nombre de Mersenne Mp = 2p – 1 est premier si et seulement si sp – 2 est divisible par Mp[4].
Le nombre sp − 2 mod Mp est appelé le « résidu de Lucas-Lehmer » de p[5].
Exemples
Le nombre de Mersenne M3 = 7 est premier. Le test de Lucas-Lehmer le vérifie de la manière suivante. À partir de s0 = 4, on calcule s3 − 2 = s1 = 42 − 2 = 14 ≡ 0 mod 7. Puisque la valeur de s1 mod 7 est 0, la conclusion est que M3 est premier.
En revanche, M11 = 2 047 = 23 × 89 n'est pas premier. Encore une fois, s0 = 4 mais on calcule maintenant, modulo 2 047, les termes successifs de la suite s jusqu'à l'indice 11 − 2 = 9 :
s1 = 42 − 2 = 14
s2 = 142 − 2 = 194
s3 = 1942 − 2 ≡ 788 mod 2 047
s4 ≡ 7882 − 2 ≡ 701 mod 2 047
s5 ≡ 7012 − 2 ≡ 119 mod 2 047
s6 ≡ 1192 − 2 ≡ 1 877 mod 2 047
s7 ≡ 1 8772 − 2 ≡ 240 mod 2 047
s8 ≡ 2402 − 2 ≡ 282 mod 2 047
s9 ≡ 2822 − 2 ≡ 1 736 mod 2 047
Puisque la valeur de s9 mod 2 047 n'est pas 0, la conclusion est que M11 = 2 047 n'est pas premier.
Preuve
Remarque préliminaire : Si est premier, alors aussi. En effet, si , alors car . Nous ne nous intéresserons donc qu'aux nombres de Mersenne pour impair (le cas étant trivial).
La preuve qui va suivre utilise la théorie des corps finis et notamment le petit théorème de Fermat. Elle est inspirée de celle donnée dans l'ouvrage de Saux-Picard-Rannou[6].
À partir de maintenant, que soit premier ou non, on va poser . On écrit la classe de , de sorte que . Nous avons donc agrandi l'anneau en un anneau contenant une racine carrée de 3.
On prouve tout d'abord la caractérisation suivante :
Théorème : Si impair, alors est premier si et seulement si dans .
Sa preuve est découpée en la condition nécessaire suivie de la condition suffisante. Elle est suivie de la preuve de la correction du test de Lucas-Lehmer, qui en découlera alors presque immédiatement.
Condition nécessaire à la primalité
On suppose que est premier.
Etude de carrés modulo :
D'une part, le nombre 3 n'est pas carré modulo . En effet : comme est impair, donc . Donc est un carré donc, en écrivant , on a (voir le symbole de Legendre). Or, par le théorème de la réciprocité quadratique, . Or, est impair donc .
On note la conséquence qui est que, si est premier, alors d'où .
D'autre part, le nombre 2 est carré modulo . En effet : , donc , et sachant que est impair, on écrit qui est une racine de dans . Une conséquence est que, quand est premier, on a .
Conclusion :
Si est premier, alors est un corps donc on peut poser et son -conjugué. Alors et . Alors on est armés pour calculer ce qu'on voulait calculer : Mais , donc . Cela conclut la condition nécessaire.
Condition suffisante à la primalité
Si est un facteur premier de , alors divise dans donc n'est pas inversible donc il existe un idéal maximal de contenant noté ( existe car c'est un anneau fini). On a donc dans donc est un corps de caractéristique (dès qu'un nombre premier est nul dans un corps, ça veut dire que ce corps l'a pour caractéristique). On pose , . On a . Or, car est impair car l'est. Donc l'ordre de dans est exactement (en effet, en mettant au carré, on voit que l'ordre est une puissance de 2, et en utilisant le fait que , ça ne peut pas être une puissance inférieure à ).
On pose, dans , qui est donc à coefficients dans (cette flèche signifie l'existence d'un morphisme d'inclusion). Donc est invariant par le morphisme de Frobenius dans donc ses racines sont permutées par celui-ci, donc ou . Dans le cas où , on trouve que vu son ordre ce qui est contradictoire car . Ainsi, donc d'où l'égalité donc est premier. Cela conclut la condition suffisante.
Test de Lucas-Lehmer
Soit impair fixé. On pose et, pour , .
Nous allons prouver le théorème de Lucas-Lehmer : est premier si et seulement si .
Comme éléments de , on pose , , . On montre par récurrence que . : et . Si , si , alors . Donc à présent : si et seulement si si et seulement si donc si et seulement si est premier.
Notes et références
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lucas–Lehmer primality test » (voir la liste des auteurs).
↑(en) D. H. Lehmer, « An extended theory of Lucas' functions », Ann. Math., 2e série, vol. 31, , p. 419-448 (JSTOR 1968235).
↑(en) D. H. Lehmer, « On Lucas' test for the primality of Mersenne numbers », J. London Math. Soc., vol. 10, , p. 162-165 (lire en ligne).
↑Cette suite est décalée dans les articles originaux de Lehmer et dans (en) Chris Caldwell, « A proof of the Lucas-Lehmer Test », sur Prime Pages et (en) Benjamin Fine et Gerhard Rosenberger, Number Theory : An Introduction via the Distribution of Primes, Springer, (lire en ligne), p. 226 : si = Si+1 avec S1 = 4 et Sk = Sk–12 – 2. La condition s'écrit alors : Sp – 1 est divisible par Mp.
↑(en) Paulo Ribenboim, The Little Book of Bigger Primes, Springer, , 2e éd., 356 p. (ISBN978-0-387-20169-6, lire en ligne), p. 77-78.