Test de primalité de Lucas-Lehmer pour les nombres de Mersenne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Lucas, Lehmer, Test de Lucas et Test de primalité de Lucas-Lehmer.
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].

Théorème[modifier | modifier le code]

On définit par récurrence la suite d'entiers (si)i≥0 par[3] :

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[modifier | modifier le code]

  • 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[modifier | modifier le code]

On a besoin de si est premier[6], un cas simple de réciprocité quadratique.

On se place dans l'anneau .

Puisque on a . Par ailleurs .

  • Si est premier on a donc
Notons que (1) est vrai si et seulement si .
  • Maintenant on suppose que (1) est vrai mais que n'est pas premier. Soit son plus petit facteur premier, si bien que . On obtient
est donc l'ordre de dans le groupe multiplicatif . Mais ce groupe a éléments où . On aurait donc
une contradiction puisque .

Finalement on se place dans l'anneau qui contient la racine 3ème de l'unité qui vérifie si bien que si est premier et on a donc bien .

Notes et références[modifier | modifier le code]

(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).

  1. (en) D. H. Lehmer, « An extended theory of Lucas' functions », Ann. Math., 2e série,‎ , p. 419-448 (JSTOR 1968235).
  2. (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).
  3. 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.
  4. (en) Paulo Ribenboim, The Little Book of Bigger Primes, Springer, , 2e éd. (ISBN 978-0-387-20169-6, lire en ligne), p. 77-78.
  5. (en) Eric W. Weisstein, « Lucas-Lehmer Test », MathWorld.
  6. (en) J. W. Bruce, « A Really Trivial Proof of the Lucas–Lehmer Test », The American Mathematical Monthly, vol. 100, no 4,‎ , p. 370–371 (DOI 10.2307/2324959)

Articles connexes[modifier | modifier le code]