Test de Lucas-Lehmer

(Oral Centrale Mp)
Pour tout entier {n}, on note {M_{n}=2^{n}-1}.
En particulier, les {M_{p}} avec {p} premier sont appelés 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 affirme que, si {p} est premier impair: {M_{p}\text{\ est premier si et seulement si\ }M_{p}\text{\ divise\ }S_{p-1}}L’objectif de cet exercice est de prouver la condition suffisante de ce test.
Soit {p} entier premier tel que {M_{p}} divise {S_{p-1}} (donc {p\ge3}).
On souhaite montrer que {M_{p}} est premier. Pour cela, on raisonne par l’absurde.
On se donne donc un diviseur {d} de {M_{p}} tel que {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 l’ensemble {E=\{a+b\sqrt3,(a,b)\in\mathbb{N}_{d}^{2}\}} des lois : {\begin{cases}(a+b\sqrt3)+(a'+b'\sqrt3)=\overline{a+a'}+\overline{b+b'}\,\sqrt3\phantom{\bigg(}\\(a+b\sqrt3)(a'+b'\sqrt3)=\overline{aa'+3bb'}+\overline{ab'+ba'}\,\sqrt{3}\end{cases}}(dans cette notation, {\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. Pour {n\in\mathbb{N}}, montrer que {S_{n+1}=\alpha^{2^{n}}+\beta^{2^{n}}}, où {\begin{cases}\alpha=2+\sqrt3\\\beta=2-\sqrt3\end{cases}}
    • On considère {\alpha=2+\sqrt3} comme un élément de {E}.
      Montrer que dans l’anneau {E}, on a : {\alpha^{2^{p-1}}+1=0}.
    • 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é
 Vous devez être abonné(e) et connecté(e) au site pour voir ce contenu