\documentstyle[12pt]{article}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\textwidth}{15cm}
\setlength{\headheight}{0cm}
\setlength{\topmargin}{0cm} 
\setlength{\headsep}{0cm}
\setlength{\textheight}{23cm}
\setlength{\parindent}{1cm}



\def\aujourdhui{\number\day\space\ifcase\month\or
  Janvier\or F\'evrier\or Mars\or Avril\or Mai\or Juin\or
  Juillet\or Ao\^ut\or Septembre\or Octobre\or Novembre\or D\'ecembre\fi
, \number\year}


%\renewcommand{\thepage}{ }

%sublist
\newcounter{point}
\newenvironment{sublist}{
\begin{list}{\alph{point})}{\usecounter{point}
\setlength{\itemsep}{0cm}\setlength{\leftmargin}{0.5cm}}
}{\end{list}}
                                                                
%initialize point
\newcommand{\initpoint}{\setcounter{point}{0}}
%Print point and step
\newcommand{\np}{\stepcounter{point}
\mbox{\quad\quad\alph{point})\,\,\,}\displaystyle}


%liste d'exercices
\newcounter{exo}
\newenvironment{list-of-exercises}{
\begin{list}{\arabic{exo})}{\usecounter{exo}            
\setlength{\itemsep}{0cm}}                                      
}{\end{list}}                                                   
                                                                



% abbreviations
% Black Board Bold Face
\newcommand{\N}{{\mbox{\bf N}}}
\newcommand{\sN}{{\mbox{\bf \scriptsize N}}}
\newcommand{\Z}{{\mbox{\bf Z}}}
\newcommand{\sZ}{{\mbox{\bf \scriptsize Z}}}
\newcommand{\R}{{\mbox{\bf R}}}
\newcommand{\F}{{\mbox{\bf F}}}
%Comma, forall
\newcommand{\ko}{\: , \;}
\newcommand{\fa}{\forall \,}
%Overline, Underline
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}

%Greek letters
\newcommand{\eps}{\varepsilon}


%Calligraphic letters
\newcommand{\ca}{{\cal A}}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\cg}{{\cal G}}
\newcommand{\ch}{{\cal H}}
\newcommand{\ci}{{\cal I}}
\newcommand{\ck}{{\cal K}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cn}{{\cal N}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cq}{{\cal Q}}
\newcommand{\cs}{{\cal S}}
\newcommand{\ct}{{\cal T}}
\newcommand{\cu}{{\cal U}}
\newcommand{\cv}{{\cal V}}
\newcommand{\cw}{{\cal W}}
\newcommand{\cx}{{\cal X}}



%Arrows
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\arr}[1]{\stackrel{#1}{\rightarrow}}
\newcommand{\longarr}[1]{\stackrel{#1}{\longrightarrow}}
\newcommand{\longlarr}[1]{\stackrel{#1}{\longleftarrow}}
\newcommand{\iso}{\stackrel{_\sim}{\rightarrow}}
\newcommand{\liso}{\stackrel{_\sim}{\leftarrow}}
\newcommand{\larr}[1]{\stackrel{#1}{\leftarrow}}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
\newcommand{\pl}{\parallel}



%French terminology
\newcommand{\tg}{\mbox{tg}\,}
\newcommand{\arctg}{\mbox{arctg}\,}


%\renewcommand{\arraystretch}{2}




\begin{document}
\begin{center}
Universit\'e Paris 7  \hfill 8 d\'ecembre 1996\\
U.F.R. de Math\'ematiques\hfill \mbox{B.~Keller }\\[0.5cm]
{\bf D.E.U.G. Math\'ematiques : MT 282 \\[0.5cm]
              Devoir \`a la maison}\\[0.5cm]
(\`a rendre la semaine du 13 janvier)
\end{center}
\noindent
Soit $s$ un entier impair $>1$, $n=2^s-1$ et 
$L_i$, $i\geq 1$, la suite d'entiers modulo $n$ d\'efinie
par
\[
L_1=4\ko L_{i+1}=L_i^2 -2\ko i\geq 1.
\]
Le {\em crit\`ere de Lucas-Lehmer} affirme que
\begin{center}
{\em $2^s -1$ est premier si et seulement si
$L_{s-1}\equiv 0\;(n)$.} 
\end{center}
Dans ce cas, le nombre
$2^s-1$ est appel\'e un {\em nombre premier de Mersenne}.
Actuellement (d\'ecembre 1996), le plus grand nombre
premier connu est le nombre premier de Mersenne
\[
2^{1398269}-1.
\]

\begin{list-of-exercises}

\item {\bf Comprendre le crit\`ere.}
\begin{sublist}
\item Calculer la suite des $L_i$ pour $s=5$ et
$s=11$. Conclusion ?

\item (facultatif)
Quelle est la classe de $L_{s-1}$ modulo $2^{s}-1$
obtenue \`a l'aide de votre calculette pour 
$s=13, 17, 19, 31, 61, 89, 107$ ? Si votre calculette
est assez performante, vous trouvez $0$ pour toutes
ces valeurs de $s$. Comment s'expliquent les r\'esultats
diff\'erents de $0$ obtenus sur des calculettes moins
performantes~?
\end{sublist}

\item {\bf Suffisance de la condition.} 
Supposons que $L_{s-1}\equiv 0\; (n)$.
Nous voulons montrer que $n$ est premier. Soit $p$ un facteur
premier de $n$. Notons $A$ l'anneau quotient de
$\F_p[X]$ par l'id\'eal engendr\'e par $X^2-4X+1$ et
$x$ l'image de $X$ dans $A$.

\begin{sublist}
\item Montrer que $x$ est inversible dans $A$ et qu'on a 
$x+x^{-1}=4$.
\item Montrer que $L_i= x^{(2^{i-1})} + x^{-(2^{i-1})}$, $i\geq 1$.

\item Montrer que $x^{(2^{s-1})} + x^{-(2^{s-1})} \neq 2$, 
et que $x^{(2^{s})} + x^{-(2^{s})}=2$ dans $A$.

\item  Montrer que pour $a\in A$, on a $a^2=0$ ssi $a=0$.
Indication : on distinguera deux cas suivant que
$X^2-4X+1$ est irr\'eductible ou non.

\item Soit $m\in \N$. Montrer qu'on a $x^m+x^{-m}=2$ ssi
$x^m=1$. Indication : Consid\'erer $a=x^m-1$.

\item Montrer que $x$ est d'ordre $2^s$ dans le groupe $A^*$.

\item Supposons le polyn\^ome $X^2-4X+1$ r\'eductible sur
$\F_p$. Montrer qu'on a $x^{p-1} =1$.

\item Supposons le polyn\^ome $X^2-4X+1$ irr\'eductible sur
$\F_p$. Montrer qu'on a $x^p + x^{-p} = 4$. En d\'eduire
qu'on a $x^{p-1}=1$ ou $x^{p+1}=1$.

\item Montrer que $p=2^s-1$.
\end{sublist}


\item {\bf Sur les carr\'es de $\F_p$\,.}
Soit $p$ un nombre premier impair. 
\begin{sublist}
\item Soit $a\in \F_p^*$. Montrer que $a^{(p-1)/2} = \pm 1$
Indication : consid\'erer $u=a^{(p-1)/2}$ et son carr\'e.

\item Montrer qu'un \'el\'ement $a\in \F_p^*$ est le
carr\'e d'un \'el\'ement de $\F_p^*$ ssi $a^{(p-1)/2} =1$
et que $a^{(p-1)/2} =-1$ si $a$ n'est pas un carr\'e.

\end{sublist}

La `loi de r\'eciprocit\'e quadratique' permet
de montrer que $2$ est un carr\'e dans $\F_p$ ssi
$p \equiv \pm 1\;(8)$ et que $3$ est un carr\'e
dans $\F_p$ ssi $p \equiv \pm 1\;(12)$. On admettra
ce fait qui sera utilis\'e dans 4).



\item {\bf N\'ecessit\'e de la condition.}
Supposons que $p=2^s-1$ est premier. Gardons les 
notations $A$ et $x$ de la partie 2). 
\begin{sublist}
\item Montrer \`a l'aide de 3) b) et c) qu'on a
$2^{(p-1)/2}=1$ et $3^{(p-1)/2}=-1$ dans $\F_p$.

\item Posons $y=x-2$. Montrer qu'on a
$y^2=3$, $2x=(1+y)^2$, $2x^{-1}=(1-y)^2$ et
\[
2^{(p+1)/2} L_s = (1+y)^{p+1} + (1-y)^{p+1} = 2(1+y^{p+1})
= 2(1+3^{(p+1)/2}).
\]
Indication : on utilisera que $(a+b)^{p+1} = (a+b)^p (a+b) =
(a^p+b^p)(a+b)$ dans $A$.

\item Conclure qu'on a $L_s\equiv -2\;(p)$ et $L_{s-1}\equiv 0\;(p)$.
\end{sublist}

\end{list-of-exercises}

\end{document}








