Test de Lucas-Lehmer

(Oral Centrale Mp)
Pour tout entier

{n}

, on note

{M_{n}=2^{n}-1}

.
Les

{M_{p}}

avec

{p}

premier sont les nombres de Mersenne.
On définit la suite

{(S_{n})_{n\ge1}}

par

{S_{1}=4}

et :

{\forall\, n\ge2,\;S_{n}=S_{n-1}^{2}-2}

Le test de Lucas-Lehmer dit que si

{p}

est premier impair :

{M_p}

est premier

{\Leftrightarrow M_p\mid S_{p-1}}

.
L’objectif de cet exercice est de prouver la condition suffisante de ce test.
Soit

{p\ge3}

premier tel que

{M_{p}}

divise

{S_{p-1}}

.
On souhaite montrer que

{M_{p}}

est premier.
Pour cela, on raisonne par l’absurde.
Soit donc un diviseur

{d}

{M_{p}}

avec

{1\lt d\le \sqrt{M_{p}}}

Justifier que l’entier ${d}$ est au moins égal à ${3}$ .
On note ${\mathbb{N}_{d}=\{0,1,\ldots,d-1\}}$ .
On munit ${E=\{a\!+\!b\sqrt3,(a,b)\in\mathbb{N}_{d}^{2}\}}$ de : ${\begin{array}{l}(a\!+\!b\sqrt3)\!+\!(c\!+\!d\sqrt3)=\overline{a\!+\!c}\!+\!\overline{b\!+\!d}\sqrt3\phantom{\bigg(}\\(a\!+\!b\sqrt3)(c\!+\!d\sqrt3)\!=\!\overline{ac+3bd}\!+\!\overline{ad+bc}\sqrt{3}\end{array}}$ (ici ${\overline{x}}$ désigne le reste dans la division de ${x}$ par ${d}$ ).
On vérifie facilement ( on admet) que ${(E,+\times)}$ est un anneau de cardinal ${d^{2}}$ .
Montrer ${S_{n+1}\!=\!\alpha^{2^{n}}\!+\!\beta^{2^{n}}}$ où ${\begin{cases}\alpha\!=\!2\!+\!\sqrt3\\\beta\!=\!2\!-\!\sqrt3\end{cases}}$
- Soit ${\alpha\!=\!2\!+\!\sqrt3}$ vu comme élément de ${E}$ .
  Montrer que ${\alpha^{2^{p-1}}\!+\!1\!=\!0}$ dans ${E}$ .
- Que dire alors du groupe multiplicatif engendré par ${\alpha}$ dans l’anneau ${E}$ ?
  Aboutir à une contradiction et conclure.

Cliquer ici pour voir (ou cacher) le corrigé

Pour voir la suite de ce contenu, vous devez :

Pour poursuivre votre exploration, vous pouvez :