\documentclass[a4paper]{article}
\usepackage{entete}
\author{Référence~: Cours de calcul formel. Corps finis, systèmes polynomiaux, applications. \\ Philippe~\textsc{Saux Picart}, Éric~\textsc{Rannou}}
\title{Primalité des nombres de Mersenne}
\date{2011-2012}

\begin{document}
\maketitle

On appelle {\em nombres de Mersenne} les
$$M_q = 2^q -1$$ pour $q\in\N$

On a d'abord le lemme~:
\begin{lem}
    Si $M_q$ est un nombre premier, alors $q$ est premier.
\end{lem}

\begin{proof}
    Si $q$ n'est pas premier, $q=mn$, avec $m,n>2$.

    Et alors $M_q = 2^{mn}-1$ qui est divisible par $2^n-1$.
\end{proof}

On a une caractérisation~:
\begin{thm}
    Pour tout nombre premier impair $q$~: 
    $$M_q\text{ est premier} \Longleftrightarrow \left( 2+\sqrt 3 \right)^{2^{q-1}} \equiv -1 \mod M_q.$$
\end{thm}

On remarque qu'il faut se placer dans un corps où $3$ admet une racine carrée. Dans la suite, on explicitera~: on prendra $\F_{M_q}$ ou une de ses extensions.

\begin{proof}[Démonstration du sens direct]
    \begin{lem}
        Pour tout entier $k$ non nul, $M_{2k+1}$ est congru à 7 modulo 12.
    \end{lem}
    \begin{prooflem}
        Par récurrence~:
        \begin{itemize}
            \item[$(k=1)$~:] On a bien $2^{2\times 1 +1} =7$.
            \item[$(k\to k+1)$~:] On a modulo 12~:
            \begin{align*}
                2^{2(k+1)+1}-1 & \equiv 4\times 2^{2k+1} -1 \\
                &\equiv \left( 2^{2k+1}-1 \right)\times 4 + 3 \\
                &\equiv 7\times4 +3 \\
                &\equiv 7
            \end{align*}
        \end{itemize}
    \end{prooflem}

    Donc, pour tout $q$ impair, $M_q \equiv 7 \mod 12$.

    Montrons maintenant que 3 n'est pas résidu quadratique modulo $M_q$.

    Pour cela, on montre le 
    \begin{lem}
        3 est résidu quadratique modulo un entier premier $p$ {\em si, et seulement si} $p \equiv \pm 1 \mod 12$.
    \end{lem}

    \begin{prooflem}
        Par la loi de réciprocité quadratique, on a~:
        $$\left( \frac p 3 \right) \left( \frac 3 p \right) = (-1)^{\frac{p-1}{2}}.$$
        Ainsi, par définition du symbole de Legendre~:
        $$\text{3 résidu modulo }p \Leftrightarrow \left( \frac{p}{3} \right) = (-1)^{\frac{p-1}{2}}.$$
        On remarque que le seul carré non nul de $\F_3$ est 1, et donc 3 est résidu quadratique modulo $p$ {\em si, et seulement si} l'une des conditions est vérifiée~:
        \begin{enumerate}[(i)]
            \item $p \equiv 1 \mod 3$ et $\frac{p-1}{2}$ est pair.
            \item $p \equiv 2 \mod 3$ et $\frac{p-1}{2}$ est impair.
        \end{enumerate}

        Dans le premier cas, $p$ est congru à 1 modulo 3 et 4, et donc modulo 12.

        Dans le second cas, $p$ est congru à 2 modulo 3, et 3 modulo 4, et donc par théorème chinois, à -1 modulo 12.
    \end{prooflem}

    Comme $M_q$ n'est congru ni à 1, ni à -1 modulo 12, 3 n'est pas résidu quadratique modulo $M_q$. $X^2-3$ est donc irréductible sur $\F_{M_q}$, et donc
    $\mathcal A = \EnsQ{\F_{M_q}[X]}{(X^2-3)}$ 
    est un corps, et on note la classe de $X$ dans $\mathcal A$ $\sqrt 3$.

    On remarque de plus que $2^{q+1} \equiv 2 \mod M_q$, et donc 2 admet une racine carrée $\sqrt 2 := 2^{\frac{q+1}{2}}$.

    On définit les quantités 
    $$\rho = \frac{1+\sqrt 3}{\sqrt 2} \text{ et } \overline{\rho}=\frac{1-\sqrt3}{\sqrt2}.$$
    On montre facilement que $\rho^2 = 2 + \sqrt3$ et $\overline\rho \rho = -1$.

    De plus, on remarque que comme $\sqrt3$ n'est pas résidu quadratique modulo $M_q$, par petit théorème de Fermat~:
    $$\left( \sqrt3 \right)^{M_q} = 3^{\frac{M_q-1}{2}} \sqrt3 = -\sqrt3.$$
    Comme $\mathcal A$ est de caractéristique $M_q$, on a par morphisme de Frobénius~:
    $$\left( a+b\sqrt3 \right)^{M_q} = a - b\sqrt3.$$

    De même, on a $\rho^{M_q}=\overline\rho$
    Comme $\mathcal A$ est de caractéristique $M_q$, on a par morphisme de Frobénius~:
    $$\left(a+b\sqrt3\right)^{M_q} = a - b\sqrt3.$$
    
    De même, on a $\sqrt2^{M_q} =  \sqrt 2$, et donc $\rho^{M_q}=\overline\rho$.
    
    On multiplie à gauche et à droite, et on obtient~:
    $$\left( 2+\sqrt3 \right)^{2^{q-1}} = \left( 2+\sqrt3 \right)^{\frac{M_q+1}{2}} = -1.$$
\end{proof}

\begin{proof}[Démonstration du sens réciproque]
    On note dans la suite $\Z_n$ l'anneau $\EnsQ{\Z}{n\Z}$.

    On note encore $\mathcal A$ une extension de $\Z_{M_q}$ contenant une racine de 3~: plus précisemment, si $\Z_{M_q}$ contient une racine de 3, on prend $\mathcal A = \Z_{M_q}$, et sinon on prend $\mathcal A = \EnsQ{\Z_{M_q}[X]}{(X^2-3)}$.

    On suppose $M_q$ non premier, et on appelle $p$ un de ses diviseurs premiers.

    $p$ est donc un diviseur de 0 dans $\mathcal A$, et a fortiori n'est pas inversible. Il est donc contenu dans un idéal maximal $\mathcal M$ de $\mathcal A$.

    Alors $\EnsQ{\mathcal A}{\mathcal M}$ est un corps, de caractéristique $p$ ($p$ non nul dans $\mathcal M$).

    On appelle $\alpha$ (resp. $\beta$) la classe de $2+\sqrt3$ (resp. $2-\sqrt3$) dans $\EnsQ{\mathcal A}{\mathcal M}$.

    Notre hypothèse s'écrit donc $\alpha^{2^{q-1}} \equiv -1\mod M_q$, et on en déduit que $\alpha$ est d'ordre $2^q$ dans $\EnsQ{\mathcal A}{\mathcal M}$.

    On pose maintenant $Q=(X-\alpha)(X-\beta)=X^2-4X+1$. C'est un polynôme à coefficient dans le corps premier de $\EnsQ{\mathcal A}{\mathcal M}$, $\F_p$.

    Donc, comme $\alpha$ est racine de $Q$, $\alpha^p$ aussi, et donc $\alpha^p = \alpha$ ou $\alpha^p=\beta$.

    Dans le premier cas, comme l'ordre de $\alpha$ est $2^q$, $2^q$ divise $p-1$. Or $p$ divise $M_q=2^q-1$, donc $p < 2^q$. D'où une contradiction.

    Dans le second cas, $\alpha^p = \beta = \alpha^{-1}=\alpha^{M_q}$. On a alors $p \equiv 2^q-1 \mod 2^q$, et ceci impose $p=M_q$. Encore une contradiction.
    
\end{proof}

\begin{rmq}
    On peut citer un corollaire direct de ce théorème~:
    \begin{thm}[Test de Lehmer-Lucas]
        On définit la suite $(L_n)\in\Z_{M_q}^\N$ par
        $$L_0=4\text{ et } L_{n+1} = L_n^2 - 2 \mod M_q.$$
        Alors on a~:
        $$M_q\text{ premier} \Longleftrightarrow L_{q-2} \equiv 0 \mod M_q.$$
    \end{thm}
    Cet algorithme permet de calculer directement dans $\Z_{M_q}$ plutôt que dans une extension. Au final, il est de complexité $\mathcal O(q^3)$ (on peut accélerer un peu avec la transformée de Fourier discrète).
\end{rmq}

\end{document}
