Cdtjkyj

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 |

On définit par récurrence la suite d'entiers (s_i)_i≥0 par^[3] :

s0=4et∀i∈Nsi+1=si2−2.{displaystyle s_{0}=4quad {rm {et}}quad forall iin mathbb {N} quad s_{i+1}=s_{i}^{2}-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 M_p = 2^p – 1 est premier si et seulement si s_{p – 2} est divisible par M_p^[4].

Le nombre s_{p − 2} mod M_p est appelé le « résidu de Lucas-Lehmer » de p^[5].

Exemples |

• Le nombre de Mersenne M₃ = 7 est premier. Le test de Lucas-Lehmer le vérifie de la manière suivante. À partir de s₀ = 4, on calcule s_{3 − 2} = s₁ = 4² − 2 = 14 ≡ 0 mod 7. Puisque la valeur de s₁ mod 7 est 0, la conclusion est que M₃ est premier.


• En revanche, M₁₁ = 2 047 = 23 × 89 n'est pas premier. Encore une fois, s₀ = 4 mais on calcule maintenant, modulo 2 047, les termes successifs de la suite s jusqu'à l'indice 11 − 2 = 9 :
  
  
  
  • 
    s₁ = 4² − 2 = 14
  
  
  • 
    s₂ = 14² − 2 = 194
  
  
  • 
    s₃ = 194² − 2 ≡ 788 mod 2 047
  
  
  • 
    s₄ ≡ 788² − 2 ≡ 701 mod 2 047
  
  
  • 
    s₅ ≡ 701² − 2 ≡ 119 mod 2 047
  
  
  • 
    s₆ ≡ 119² − 2 ≡ 1 877 mod 2 047
  
  
  • 
    s₇ ≡ 1 877² − 2 ≡ 240 mod 2 047
  
  
  • 
    s₈ ≡ 240² − 2 ≡ 282 mod 2 047
  
  
  • 
    s₉ ≡ 282² − 2 ≡ 1 736 mod 2 047
  
  
  
  

Puisque la valeur de s₉ mod 2 047 n'est pas 0, la conclusion est que M₁₁ = 2 047 n'est pas premier.

Preuve |

 Cette section peut contenir un travail inédit ou des déclarations non vérifiées (juillet 2017). Vous pouvez aider en ajoutant des références ou en supprimant le contenu inédit.

On a besoin de 32p−1−1≡−1mod2p−1{displaystyle 3^{2^{p-1}-1}equiv -1{bmod {2}}^{p}-1} si 2p−1{displaystyle 2^{p}-1} est premier^[6], un cas simple de réciprocité quadratique.

On se place dans l'anneau Z2p−1[3]={a+b3mod2p−1}{displaystyle mathbb {Z} _{2^{p}-1}[{sqrt {3}}]={a+b{sqrt {3}}{bmod {2}}^{p}-1}}.

Puisque p∣2p−1−1{displaystyle pmid 2^{p-1}-1} on a 22p−1−1≡1mod2p−1{displaystyle 2^{2^{p-1}-1}equiv 1{bmod {2}}^{p}-1}. Par ailleurs 2+3=12−3=(2.3+23)23.23{displaystyle 2+{sqrt {3}}={frac {1}{2-{sqrt {3}}}}={frac {(2.3+2{sqrt {3}})^{2}}{3.2^{3}}}}.

• Si 2p−1{displaystyle 2^{p}-1} est premier on a (2.3+23)2p−1≡(formule du binôme)(2.3)2p−1+(23)2p−1⏟322p−132p−1−1≡2.3−23mod2p−1{displaystyle (2.3+2{sqrt {3}})^{2^{p}-1}!!!!!{underset {scriptstyle {text{(formule du binôme)}}}{equiv }}!!!!!(2.3)^{2^{p}-1}+underbrace {(2{sqrt {3}})^{2^{p}-1}} _{{sqrt {3}}2^{2^{p}-1}3^{2^{p-1}-1}}equiv 2.3-2{sqrt {3}}{bmod {2}}^{p}-1} donc

(2+3)2p−1=(2.3+23)2p(3.23)2p−1≡(2.3+23)(2.3−23)−3.23≡−1mod2p−1(1){displaystyle (2+{sqrt {3}})^{2^{p-1}}={frac {(2.3+2{sqrt {3}})^{2^{p}}}{(3.2^{3})^{2^{p-1}}}}equiv {frac {(2.3+2{sqrt {3}})(2.3-2{sqrt {3}})}{-3.2^{3}}}equiv -1{bmod {2}}^{p}-1qquad qquad (1)}

Notons que (1) est vrai si et seulement si Sp−2=(2−3)2p−2((2+3)2p−1+1)≡0mod2p−1{displaystyle S_{p-2}=(2-{sqrt {3}})^{2^{p-2}}left((2+{sqrt {3}})^{2^{p-1}}+1right)equiv 0{bmod {2}}^{p}-1} où S0=4,Sn+1=Sn2−2=(2+3)2n+1+(2−3)2n+1{displaystyle S_{0}=4,S_{n+1}=S_{n}^{2}-2=(2+{sqrt {3}})^{2^{n+1}}+(2-{sqrt {3}})^{2^{n+1}}}.

• Maintenant on suppose que (1) est vrai mais que 2p−1{displaystyle 2^{p}-1} n'est pas premier. Soit q{displaystyle q} son plus petit facteur premier, si bien que q2≤2p−1{displaystyle q^{2}leq 2^{p}-1}. On obtient

(1)⟹(2+3)2p−1≡−1modq{displaystyle (1)implies (2+{sqrt {3}})^{2^{p-1}}equiv -1{bmod {q}}}

2p{displaystyle 2^{p}} est donc l'ordre de 2+3{displaystyle 2+{sqrt {3}}} dans le groupe multiplicatif Zq[3]×{displaystyle mathbb {Z} _{q}[{sqrt {3}}]^{times }}. Mais ce groupe a r{displaystyle r} éléments où r≤q2−1{displaystyle rleq q^{2}-1}. On aurait donc

(2+3)r≡1modq{displaystyle (2+{sqrt {3}})^{r}equiv 1{bmod {q}}}

une contradiction puisque r≤q2−1<2p{displaystyle rleq q^{2}-1<2^{p}}.

Finalement on se place dans l'anneau Z2p−1[i,3]{displaystyle mathbb {Z} _{2^{p}-1}[i,{sqrt {3}}]} qui contient la racine 3^e de l'unité
ζ3=−12+i32{displaystyle zeta _{3}=-{frac {1}{2}}+i{frac {sqrt {3}}{2}}} qui vérifie ζ3−ζ32=i3{displaystyle zeta _{3}-zeta _{3}^{2}=i{sqrt {3}}} si bien que si 2p−1{displaystyle 2^{p}-1} est premier −i332p−1−1=(ζ3−ζ32)2p−1≡ζ32p−1−ζ32(2p−1)≡ζ3−ζ32≡i3mod2p−1{displaystyle -i{sqrt {3}},3^{2^{p-1}-1}=(zeta _{3}-zeta _{3}^{2})^{2^{p}-1}equiv zeta _{3}^{2^{p}-1}-zeta _{3}^{2(2^{p}-1)}equiv zeta _{3}-zeta _{3}^{2}equiv i{sqrt {3}}{bmod {2}}^{p}-1} et on a donc bien 32p−1−1≡−1mod2p−1{displaystyle 3^{2^{p-1}-1}equiv -1{bmod {2}}^{p}-1}.

Notes et références |

Articles connexes |

• Great Internet Mersenne Prime Search


• Prime95


• 
  Test de Lucas-Lehmer-Riesel (en)
  

v · m Nombres premiers
Donnés par une formule	combinatoire factoriel (n!±1) primoriel (pn#±1) Euclide (pn#+1) polynomiale de Pythagore (4n + 1) cubain (x3 − y3)/(x − y) quatrain (x4 + y4) exponentielle Fermat (22n + 1) Mersenne (2p – 1) Double de Mersenne (22p–1 –1) Pierpont (2u3v + 1) Carol ((2n – 1)2 – 2) Kynea ((2n + 1)2 – 2) Thebit (3·2n – 1) Wagstaff ((2p + 1)/3) Proth (k2n + 1) Cullen (n2n + 1) Woodall (n2n – 1) Mills (⌊A3n⌋)
Appartenant à une suite	Fibonacci Lucas Motzkin Bell Pell Perrin Newman-Shanks-Williams
Ayant une propriété remarquable	bon chanceux fortuné Higgs illégal Pillai Ramanujan régulier Stern super supersingulier Wall-Sun-Sun Wieferich Paire de Wieferich Wilson Wolstenholme
Ayant une propriété dépendant de la base	diédral palindrome Reimerp répunit (10n − 1)/9 permutable circulaire tronquable minimal long unique Smarandache-Wellin partie entière de puissances de constante troncature de constante
Propriétés mettant en jeu plusieurs nombres	singleton Chen {p ; p+2 premier ou semi-premier} équilibré (faible, fort) {pn ; pn = (<, >) (pn–1 + pn+1)/2} Sophie Germain {p ; 2p + 1 premier} sûr {p ; (p – 1)/2 premier} n-uplet jumeaux (p, p + 2) cousins (p, p + 4) sexy (p, p + 6) triplet (p, p + 2 ou p + 4, p + 6) quadruplet (p, p + 2, p + 6, p + 8) quintuplet (p – 4, p, p + 2, p + 6, p + 8) ou (p, p + 2, p + 6, p + 8, p + 12) sextuplet (p – 4, p, p + 2, p + 6, p + 8, p + 12) suite progression arithmétique (p + an) chaîne de Cunningham (p, 2p ± 1, etc.)
Classement par taille	titanesque (1 000+ chiffres) gigantesque (10 000+) méga (1 000 000+) record
Généralisations (entier quadratique)	Eisenstein Gauss
Nombre composé	pseudo-premier presque premier semi-premier interpremier
Nombre connexe	probable (NPP)
Conjectures et théorèmes de théorie des nombres	Conjecture d'Agoh-Giuga Conjecture d'Artin Conjecture de Bateman-Horn Conjecture de Bouniakovski Conjecture de Brocard Conjecture de Cramér Conjecture de Dickson Conjecture d'Elliott-Halberstam Conjecture de Firoozbakht Conjecture de Goldbach (forte–faible) Conjecture de Grimm Conjecture de Hardy-Littlewood (première–seconde conjecture) Conjecture de Legendre Conjecture de Lemoine Conjecture des nombres premier de Waring Conjecture d'Oppermann Conjecture de Polignac Conjecture de Redmond–Sun Fonction de compte des nombres premiers Formules pour les nombres premiers Hypothèse H de Schinzel Nouvelle conjecture de Mersenne Théorème de Green-Tao Théorème des nombres premiers Théorème de la progression arithmétique Théorème de Rosser Théorème de Vinogradov
Constantes liées aux nombres premiers	Constante de Brun Constante de Legendre Constante de Mills Constante des nombres premiers
Prime Pages Liste de nombres premiers Liste de suites de nombres premiers

• Portail de l’arithmétique et de la théorie des nombres