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é

  1. C’est évident car {M_{p}=2^{p}-1\ge7} est impair.
  2. Par récurrence. L’égalité est vraie si {n=0} car {S_{1}=4=\alpha+\beta}.

    Supposons {S_{n+1}=\alpha^{2^{n}}+\beta^{2^{n}}}, pour un certain {n\in\mathbb{N}}.

    Alors, avec {\alpha\beta=1} : {S_{n+2}=\bigl(\alpha^{2^{n}}+\beta^{2^{n}}\bigr)^{2}-2=\alpha^{2^{n+1}}+\beta^{2^{n+1}}}ce qui achève la récurrence.

    • Par hypothèse, il existe {q\in\mathbb{N}} tel que {qM_{p}=S_{p-1}=\alpha^{2^{p-2}}+\beta^{2^{p-2}}}.

      Après produit par {\alpha^{2^{p-2}}}, on obtient : {qM_{p}\,\alpha^{2^{p-2}}=\alpha^{2^{p-1}}+1}.

      Or {\alpha=2+\sqrt3} et {d\mid M_{p}}.

      L’égalité précédente, vue dans {E}, se réduit à {\alpha^{2^{p-1}}=-1}.

    • De ce qui précède, il résulte bien sûr {\alpha^{2^{p}}=1}, toujours dans l’anneau {E}.

      On sait que les {k\in\mathbb{Z}} tels que {\alpha^{k}=1} forment un idéal {n\mathbb{Z}}, avec {n} dans {\mathbb{N}^{*}}.

      Du fait que {\alpha^{2^{p}}=1}, l’entier {n} divise {2^{p}} donc un {2^{k}} avec {0\le k\le n}.

      En fait {n} est exactement égal à {2^{p}} car {\alpha^{2^{p-1}}=-1\ne1} (car {d\ge3}).

      Ainsi on dispose dans {E} de {2^{p}} éléments distincts deux à deux.

      Mais c’est absurde car {E} est de cardinal {d^{2}}, et {d^{2}\le M_{p}=2^{p}-1}.

      Cette contradiction nous assure donc que l’entier {M_{p}} est premier.