Lucas-Lehmer : l'idée de la démonstration

Le DM s’est arrêté au pied du mur : le test de Lucas-Lehmer y était admis. Promesse tenue, voici l’idée de sa démonstration, puis l’histoire jusqu’au record actuel.

Le test, rappel

On fixe un nombre premier impair $p$ et on pose $M_p = 2^p - 1$. La suite du test est définie par :

$$s_0 = 4 \qquad \text{et} \qquad \forall k \in \mathbb{N},\ s_{k+1} = s_k^2 - 2.$$

Le verdict tient en une ligne : $M_p$ est premier si et seulement si $M_p$ divise $s_{p-2}$. Une récurrence, une division. C’est ce « c’est tout » qu’il faut expliquer.

L’idée de la démonstration

Le premier geste est de trouver une forme close pour $(s_k)$, exactement comme la formule de Binet en donnait une pour Fibonacci. Posez $\omega = 2 + \sqrt{3}$ et $\bar\omega = 2 - \sqrt{3}$. Deux identités immédiates : $\omega + \bar\omega = 4$ et $\omega\bar\omega = 4 - 3 = 1$. Alors :

$$\forall k \in \mathbb{N},\quad s_k = \omega^{2^k} + \bar\omega^{2^k}.$$

La récurrence tient en deux lignes. Initialisation : $\omega^{2^0} + \bar\omega^{2^0} = \omega + \bar\omega = 4 = s_0$. Hérédité : si $s_k = \omega^{2^k} + \bar\omega^{2^k}$, alors

$$s_{k+1} = s_k^2 - 2 = \omega^{2^{k+1}} + \bar\omega^{2^{k+1}} + 2\,(\omega\bar\omega)^{2^k} - 2 = \omega^{2^{k+1}} + \bar\omega^{2^{k+1}},$$

puisque $\omega\bar\omega = 1$. Le doublement de l’exposant à chaque étape, voilà le moteur caché : élever au carré, c’est doubler.

Deuxième geste : traduire la divisibilité. Supposons que $M_p$ divise $s_{p-2}$, c’est-à-dire $\omega^{2^{p-2}} + \bar\omega^{2^{p-2}} \equiv 0 \pmod{M_p}$. Ici, une honnêteté nécessaire : $\omega$ n’est pas un entier, et « congru modulo $M_p$ » demande donc de faire de l’arithmétique modulaire avec les nombres de la forme $a + b\sqrt{3}$, où $a$ et $b$ sont des entiers. C’est le point que nous admettons : ces calculs se comportent bien (on peut additionner, multiplier, réduire les coefficients modulo $M_p$, et $\bar\omega$ y reste l’inverse de $\omega$ puisque $\omega\bar\omega = 1$). En admettant cela, multiplions la congruence par $\omega^{2^{p-2}}$ :

$$\omega^{2^{p-1}} \equiv -1 \pmod{M_p}, \qquad \text{puis en élevant au carré :} \qquad \omega^{2^{p}} \equiv 1 \pmod{M_p}.$$

Autrement dit, la puissance $2^p$ ramène $\omega$ à $1$, mais la puissance $2^{p-1}$ donne $-1$, pas $1$. Le plus petit exposant qui ramène $\omega$ à $1$ (son ordre) divise $2^p$ sans diviser $2^{p-1}$ : c’est donc exactement $2^p$, un ordre gigantesque.

Dernier geste, le coup de grâce. Supposons $M_p$ non premier : il possède un diviseur premier $q \leqslant \sqrt{M_p}$. Toute la congruence précédente reste vraie modulo $q$, donc $\omega$ est d’ordre $2^p$ modulo $q$. Or, modulo $q$, il n’existe qu’un nombre fini d’objets $a + b\sqrt{3}$ : au plus $q^2$ valeurs, donc moins de $q^2$ inversibles. Un ordre ne peut pas dépasser le nombre d’inversibles (résultat admis lui aussi, cousin d’un théorème que vous verrez en arithmétique). D’où :

$$2^p \;\leqslant\; q^2 - 1 \;<\; q^2 \;\leqslant\; M_p = 2^p - 1,$$

contradiction. Donc $M_p$ est premier. La réciproque (si $M_p$ est premier, la divisibilité a bien lieu) est plus délicate encore, et nous l’admettons entièrement.

Retenez la structure : forme close, traduction en ordre, comptage qui explose. Et retenez ce qui manque : l’arithmétique dans $\mathbb{Z}[\sqrt{3}]$, le théorème sur l’ordre, la réciproque. Vous n’avez pas vu une preuve complète ; vous avez vu son squelette, et vous savez où sont les chairs manquantes.

1876, 1930, 1996 : trois âges d’un même test

Le 10 janvier 1876, Édouard Lucas annonce que $M_{127} = 2^{127} - 1$, trente-neuf chiffres, est premier. La légende parle de « dix-neuf ans de calculs » : c’est l’écart entre ses premiers travaux d’adolescent et l’annonce, pas dix-neuf ans de calcul continu ; le test proprement dit, mené sur un damier de $127 \times 127$ cases où des pions figuraient les chiffres binaires, représente des centaines d’heures. Son record tiendra soixante-quinze ans et reste le plus grand nombre premier jamais établi sans machine.

En 1930, Derrick Lehmer, dans sa thèse « An Extended Theory of Lucas’ Functions », nettoie et complète l’héritage : condition nécessaire et suffisante, valable pour tout $p$ premier impair, sous la forme exacte que vous avez utilisée.

Depuis 1996, le projet collaboratif GIMPS (Great Internet Mersenne Prime Search) distribue la chasse sur les machines de dizaines de milliers de volontaires : chacun installe un logiciel gratuit, reçoit des exposants à tester, renvoie les verdicts. Palmarès actuel : le plus grand nombre premier connu est

$$2^{136\,279\,841} - 1,$$

soit $41\,024\,320$ chiffres, découvert le 12 octobre 2024 par Luke Durant, un volontaire de San José, sur une flotte de GPU loués dans le cloud. C’est le 52e nombre premier de Mersenne connu, le 18e trouvé par GIMPS, et le premier découvert par GPU plutôt que par un ordinateur personnel.

La chaîne complète tient en une phrase : une suite définie par récurrence (chapitre A0), une forme close prouvée par récurrence, un test de trois lignes, et un record de quarante et un millions de chiffres. La récurrence n’est pas un exercice d’école ; c’est l’outil qui détient, aujourd’hui encore, le record du monde.

Sources

• GIMPS, communiqué officiel : Mersenne Prime Discovery, $2^{136279841}-1$ is Prime!
• GIMPS, liste des nombres premiers de Mersenne connus
• Keith Conrad, The Lucas-Lehmer Test (démonstration complète)
• D. H. Lehmer, « An Extended Theory of Lucas’ Functions », Annals of Mathematics 31 (1930), p. 419-448
• MacTutor, biographie d’Édouard Lucas
• Wikipédia, Largest known prime number et Great Internet Mersenne Prime Search