ArithmétiqueNotion · Glossaire
test de Lucas-Lehmer
Le test de Lucas-Lehmer vérifie si un nombre de Mersenne M_p = 2^p − 1 est premier. Pour un exposant premier impair p, on part de s_0 = 4, puis on élève au carré, on retire 2 et on conserve le reste modulo M_p. Après exactement p − 2 itérations, M_p est premier si et seulement si le reste s_(p−2) vaut 0. L'exemple M_5 = 31 permet de suivre ce calcul jusqu'au verdict.
Sommaire
Ce que vous allez apprendre
- Reconnaître le domaine d'application du test de Lucas-Lehmer.
- Calculer la suite des restes pour M₅ = 31.
- Interpréter le reste final et éviter les cas où la règle classique ne s'applique pas.
En clair
Prenons le nombre 31, obtenu en retirant 1 à une puissance de 2 : 31 = 25 − 1. Pour savoir s'il est premier, le test de Lucas-Lehmer évite d'essayer tous les diviseurs possibles. Il part de 4, élève le résultat au carré, retire 2, puis ne garde que le reste de la division par 31.
Après trois répétitions, le reste vaut 0. Ce zéro final certifie que 31 est premier. La même recette vise spécialement les nombres de Mersenne, ceux qui s'écrivent comme une puissance de 2 diminuée de 1.
Définition
Le test de Lucas-Lehmer est un critère de primalité adapté aux nombres de Mersenne. Pour un exposant premier impair noté p, le nombre testé, noté Mp, est défini par . On construit ensuite une suite de restes : le premier terme vaut 4 et chaque terme suivant est le carré du précédent moins 2, réduit modulo Mp.
En notant si le terme d'indice i, la récurrence et le verdict s'écrivent :
Il faut donc effectuer exactement p − 2 itérations. Réduire modulo Mp à chaque étape conserve le reste utile et empêche les valeurs intermédiaires de croître inutilement.
Le critère général de Lucas concerne un entier impair n > 1. Il cherche un entier a tel que , tandis que pour chaque diviseur premier q de n − 1. La version de Lucas-Lehmer remplace cette recherche générale par une récurrence spécialisée qui exploite la forme des nombres de Mersenne.
Un exemple, pas à pas
Testons le nombre de Mersenne associé à l'exposant premier impair p = 5. Les données sont l'exposant 5, le nombre M5 = 25 − 1 = 31 et le terme initial s0 = 4. Le terme à contrôler porte l'indice p − 2 = 3.
1. Le premier calcul donne s1 = 42 − 2 = 14. Son reste modulo 31 est 14.
2. Le deuxième calcul donne s2 = 142 − 2 = 194. Comme 194 = 6 × 31 + 8, son reste modulo 31 est 8.
3. Le troisième calcul donne s3 = 82 − 2 = 62. Comme 62 = 2 × 31, son reste modulo 31 est 0.
Le terme attendu est bien s3, et son reste est nul : le test certifie donc que M5 = 31 est premier. Le schéma de la suite permet de suivre les trois réductions sans perdre le lien entre un reste et le calcul suivant.
Un contrôle direct confirme le verdict : aucun des nombres premiers 2, 3 et 5, qui sont les seuls à ne pas dépasser √31, ne divise 31.
En pratique
Pour tester un candidat de la forme 2p − 1, on vérifie d'abord que l'exposant p est premier et impair. Si p est composé, le nombre de Mersenne l'est aussi et la récurrence n'est pas nécessaire.
Un programme ne conserve que le reste modulo Mp après chaque carré. Ce geste limite la taille des valeurs manipulées, tout en préservant exactement le prochain reste.
Lorsque l'entier n'a pas la forme d'un nombre de Mersenne, cette version spécialisée n'est plus le bon outil. Il faut alors employer un test de primalité adapté aux entiers généraux, tel que le critère général de Lucas lorsque la factorisation de n − 1 est connue.
À ne pas confondre
Nombre de Mersenne et nombre premier de Mersenne. Tout entier Mp = 2p − 1 est un nombre de Mersenne, mais il n'est pas forcément premier. Par exemple, M11 = 2047 est divisible par 23 : la forme seule ne donne donc aucun certificat de primalité.
Test de Lucas général et test de Lucas-Lehmer. Le premier cherche un témoin a pour un entier impair et utilise les diviseurs premiers de n − 1. Le second suit une suite fixée pour un nombre de Mersenne. Un entier impair comme 29 relève du cadre général, pas de la récurrence spécialisée.
Limites et pièges
L'exposant doit être premier impair. Pour p = 2, M2 = 3 est premier, mais l'indice p − 2 vaut 0 et le terme initial 4 n'est pas nul modulo 3. Ce petit cas doit être traité séparément.
Un exposant premier ne suffit pas. Il rend possible la primalité de Mp, sans la garantir. Pour p = 11, le candidat vaut 2047 = 23 × 89 ; seul le reste final de Lucas-Lehmer tranche dans la procédure spécialisée.
La réduction modulo Mp est indispensable. Tester si la valeur entière de la suite devient exactement zéro serait une erreur : à chaque étape, le critère porte sur un reste. Dans l'exemple M5, 62 n'est pas zéro, mais son reste modulo 31 l'est.
Pour aller plus loin
La notion de nombre premier replace le verdict de Lucas-Lehmer dans son cadre : un entier supérieur à 1 qui n'admet que 1 et lui-même comme diviseurs positifs.
Le test de Lucas-Lehmer a été introduit par Édouard Lucas en 1878, puis sa formulation a été optimisée par Derrick Lehmer en 1930. Le prolongement naturel consiste à étudier pourquoi la récurrence transforme une question de divisibilité en un reste final nul. Cette justification relie les suites récurrentes, les congruences et la structure particulière de 2p − 1.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres