On définit par récurrence la suite d'entiers (si)i≥0 par[3] :
![{\displaystyle s_{0}=4\quad {\rm {et}}\quad \forall i\in \mathbb {N} \quad s_{i+1}=s_{i}^{2}-2.}](//wikimedia.org/api/rest_v1/media/math/render/svg/0496a4648c34368807c0a71d9d2dbfbc67c03a28)
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].
Remarque préliminaire : Si
est premier, alors
aussi. En effet, si
, alors
car
. Nous ne nous intéresserons donc qu'aux nombres de Mersenne
pour
impair (le cas
étant trivial).
La preuve qui va suivre utilise la théorie des corps finis et notamment le petit théorème de Fermat. Elle est inspirée de celle donnée dans l'ouvrage de Saux-Picard-Rannou[6].
À partir de maintenant, que
soit premier ou non, on va poser
. On écrit
la classe de
, de sorte que
. Nous avons donc agrandi l'anneau
en un anneau contenant une racine carrée de 3.
On prouve tout d'abord la caractérisation suivante :
Théorème : Si
impair, alors
est premier si et seulement si
dans
.
Sa preuve est découpée en la condition nécessaire suivie de la condition suffisante. Elle est suivie de la preuve de la correction du test de Lucas-Lehmer, qui en découlera alors presque immédiatement.
Condition nécessaire à la primalité
On suppose que
est premier.
Etude de carrés modulo
:
D'une part, le nombre 3 n'est pas carré modulo
. En effet : comme
est impair,
donc
. Donc
est un carré donc, en écrivant
, on a
(voir le symbole de Legendre). Or, par le théorème de la réciprocité quadratique,
. Or,
est impair donc
.
On note la conséquence qui est que, si
est premier, alors
d'où
.
D'autre part, le nombre 2 est carré modulo
. En effet :
, donc
, et sachant que
est impair, on écrit
qui est une racine de
dans
. Une conséquence est que, quand
est premier, on a
.
Conclusion :
Si
est premier, alors
est un corps donc on peut poser
et
son
-conjugué. Alors
et
. Alors on est armés pour calculer ce qu'on voulait calculer :
Mais
, donc
. Cela conclut la condition nécessaire.
Condition suffisante à la primalité
Si
est un facteur premier de
, alors
divise
dans
donc n'est pas inversible donc il existe un idéal maximal de
contenant
noté
(
existe car c'est un anneau fini). On a
donc
dans
donc
est un corps de caractéristique
(dès qu'un nombre premier est nul dans un corps, ça veut dire que ce corps l'a pour caractéristique). On pose
,
. On a
. Or,
car
est impair car
l'est. Donc l'ordre de
dans
est exactement
(en effet, en mettant au carré, on voit que l'ordre est une puissance de 2, et en utilisant le fait que
, ça ne peut pas être une puissance inférieure à
).
On pose, dans
,
qui est donc à coefficients dans
(cette flèche signifie l'existence d'un morphisme d'inclusion). Donc
est invariant par le morphisme de Frobenius dans
donc ses racines sont permutées par celui-ci, donc
ou
. Dans le cas où
, on trouve que
vu son ordre ce qui est contradictoire car
. Ainsi,
donc
d'où l'égalité donc
est premier. Cela conclut la condition suffisante.
Test de Lucas-Lehmer
Soit
impair fixé. On pose
et, pour
,
.
Nous allons prouver le théorème de Lucas-Lehmer :
est premier si et seulement si
.
Comme éléments de
, on pose
,
,
. On montre par récurrence que
.
:
et
. Si
, si
, alors
. Donc à présent :
si et seulement si
si et seulement si
donc si et seulement si
est premier.