Test de primalité de Lucas-Lehmer pour les nombres de Mersenne
- REDIRECT Modèle:Voir homonymes
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<ref>Modèle:Article.</ref>,<ref>Modèle:Article.</ref>.
Théorème
On définit par récurrence la suite d'entiers (si)i≥0 par<ref>Cette suite est décalée dans les articles originaux de Lehmer et dans Modèle:Lien web et Modèle:Ouvrage : si = Si+1 avec S1 = 4 et Modèle:Nobr La condition s'écrit alors : Sp – 1 est divisible par Mp.</ref> :
- <math>s_0=4\quad{\rm et}\quad\forall i\in\N\quad s_{i+1}=s_i^2-2.</math>
Les premiers termes de cette suite sont 4, 14, 194Modèle:Etc. (Modèle:OEIS).
Le nombre sp − 2 mod Mp est appelé le « résidu de Lucas-Lehmer » de p<ref>Modèle:MathWorld.</ref>.
Exemples
- 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 = Modèle:Nombre = 23 × 89 n'est pas premier. Encore une fois, s0 = 4 mais on calcule maintenant, modulo Modèle:Nombre, 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 Modèle:Nombre
- s4 ≡ 7882 − 2 ≡ 701 mod Modèle:Nombre
- s5 ≡ 7012 − 2 ≡ 119 mod Modèle:Nombre
- s6 ≡ 1192 − 2 ≡ Modèle:Nombre mod Modèle:Nombre
- s7 ≡ Modèle:Nombre2 − 2 ≡ 240 mod Modèle:Nombre
- s8 ≡ 2402 − 2 ≡ 282 mod Modèle:Nombre
- s9 ≡ 2822 − 2 ≡ Modèle:Nombre mod Modèle:Nombre
Puisque la valeur de s9 mod Modèle:Nombre n'est pas 0, la conclusion est que M11 = Modèle:Nombre n'est pas premier.
Preuve
Ce test a été montré en 1932 par A. E. Western en se plaçant dans le corps ℚ(√3)<ref>Modèle:Article.</ref>. Modèle:Section travail inédit On a besoin de <math> 3^{2^{p-1}-1} \equiv -1 \bmod 2^p -1</math> si <math>2^p -1</math> est premier<ref>Modèle:Article</ref>, un cas simple de réciprocité quadratique.
On se place dans l'anneau <math>\mathbb{Z}_{2^p-1}[\sqrt{3}] =\{ a+ b \sqrt{3} \bmod 2^p-1\}</math>.
Puisque <math>p \mid 2^{p-1} -1</math> on a <math>2^{2^{p-1}-1} \equiv 1 \bmod 2^p -1</math>. Par ailleurs <math>2+\sqrt{3}= \frac{1}{2-\sqrt{3}}= \frac{(2\times 3+2 \sqrt{3})^2}{3 \times 2^3}</math>.
- Si <math>2^p -1</math> est premier on a <math>(2\times 3+2 \sqrt{3})^{2^p-1}\!\!\!\!\! \underset{\scriptstyle\text{(formule du binôme)}}{\equiv}\!\!\!\!\! (2\times 3)^{2^p -1} + \underbrace{(2\sqrt{3})^{2^p-1}}_{ \sqrt{3} 2^{2^p-1} 3^{2^{p-1}-1}} \equiv 2\times 3-2\sqrt{3} \bmod 2^p-1</math> donc
- <math>(2+\sqrt{3})^{2^{p-1}} =\frac{(2\times 3+2 \sqrt{3})^{2^p}}{(3 \times 2^3)^{2^{p-1}}}\equiv \frac{(2\times 3+2 \sqrt{3})(2\times 3-2\sqrt{3})}{-3\times 2^3}\equiv -1 \bmod 2^p-1 \qquad \qquad(1)</math>
- Notons que (1) est vrai si et seulement si <math>S_{p-2} = (2-\sqrt{3})^{2^{p-2}}\left((2+\sqrt{3})^{2^{p-1}} +1\right) \equiv 0 \bmod 2^p-1 </math> où <math>S_0 = 4,\,S_{n+1} = S_n^2-2=(2+\sqrt{3})^{2^{n+1}}+(2-\sqrt{3})^{2^{n+1}}</math>.
- Maintenant on suppose que (1) est vrai mais que <math>2^p-1</math> n'est pas premier. Soit <math>q</math> son plus petit facteur premier, si bien que <math>q^2 \le 2^p-1</math>. On obtient
- <math>(1) \implies (2+\sqrt{3})^{2^{p-1}} \equiv -1 \bmod q</math>
- <math>2^{p}</math> est donc l'ordre de <math>2+\sqrt{3}</math> dans le groupe multiplicatif <math>\mathbb{Z}_q[\sqrt{3}]^\times</math>. Mais ce groupe a <math>r</math> éléments où <math>r \le q^2-1</math>. On aurait donc
- <math>(2+\sqrt{3})^{r} \equiv 1 \bmod q</math>
- une contradiction puisque <math>r \le q^2-1 < 2^p</math>.
Finalement on se place dans l'anneau <math>\mathbb{Z}_{2^p-1}[\mathrm{i},\sqrt{3}]</math> qui contient la racine 3e de l'unité <math>\zeta_3 = -\frac{1}{2}+\mathrm{i} \frac{\sqrt{3}}{2}</math> qui vérifie <math>\zeta_3-\zeta_3^2 = \mathrm{i} \sqrt{3}</math> si bien que si <math> 2^p -1</math> est premier <math>-\mathrm{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 \mathrm{i} \sqrt{3} \bmod 2^p-1</math> et on a donc bien <math>3^{2^{p-1}-1} \equiv -1 \bmod 2^p-1</math>.
Notes et références
Modèle:Traduction/Référence Modèle:Références