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.
Ce test a été montré en 1932 par A. E. Western en se plaçant dans le corps ℚ(√3)[6].
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.
↑(en) D. H. Lehmer, « An extended theory of Lucas' functions », Ann. Math., 2e série, vol. 31, , p. 419-448 (JSTOR1968235).
↑(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) A. E. Western, « On Lucas's and Pepin's tests for the primeness of Mersenne's numbers », Journal of the Mathematical Society of London, .
↑(en) J. W. Bruce, « A Really Trivial Proof of the Lucas–Lehmer Test », The American Mathematical Monthly, vol. 100, no 4, , p. 370–371 (DOI10.2307/2324959)