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} de {M_{p}} avec {1\lt d\le \sqrt{M_{p}}}.

  1. 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}}.
  2. Montrer {S_{n+1}\!=\!\alpha^{2^{n}}\!+\!\beta^{2^{n}}}{\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 ce contenu, vous devez :