\documentstyle[12pt]{article}
%\documentclass[12pt]{article}
\setlength{\oddsidemargin}{0cm}
\setlength{\textwidth}{16cm}
\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 21 janvier 1997\\
U.F.R. de Math\'ematiques\hfill \mbox{B.~Keller }\\[0.5cm]
{\bf D.E.U.G. Math\'ematiques : MT 282 \\[0.5cm]
              Corrig\'e du devoir \`a la maison de janvier 1997}
\end{center}
\noindent



\begin{list-of-exercises}

\item {\bf Comprendre le crit\`ere.}
\begin{sublist}
\item Pour $s=5$, on trouve la suite $4,14,8,0,-2,2,2,2, \ldots$.
En particulier $L_4=0$ en accord avec le fait que $2^5-1=31$
est premier.
Pour $s=11$, on trouve la suite 
$4,14,194,788,701,119,1877,240,282,1736, \ldots$.
En particulier, $L_{10}=1736\neq 0$ en accord avec le
fait que $2^{11}-1=2047= 23\times 89$ n'est pas premier.
\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 {\em Montrer que $x$ est inversible dans $A$ et
qu'on a $x+x^{-1}=4$.}
Dans $A$, on a $x^2-4x+1=0$. Donc $x(4-x)=1$ dans $A$
et $x$ est inversible d'inverse $x^{-1}=4-x$ dans $A$.
Il s'ensuit aussi que $x+x^{-1}=x+(4-x)=4$.

\item {\em Montrer que $L_i= x^{(2^{i-1})} + x^{-(2^{i-1})}$, $i\geq 1$.}
Nous proc\'edons par r\'ecurrence sur $i$. Nous avons bien
$L_1=4=x+x^{-1}$ d'apr\`es a). Supposons l'affirmation vraie
au cran $i$. Alors nous avons
\begin{eqnarray*}
L_{i+1} & = & L_i^2-2 = (x^{(2^{i-1})}+x^{-(2^{i-1})})^2 -2 \\
        & = & x^{2^i} + x^{-2^i} +2 -2 = x^{2^i}+x^{-2^i}.
\end{eqnarray*}

\item {\em Montrer que $x^{(2^{s-1})} + x^{-(2^{s-1})} \neq 2$, 
et que $x^{(2^{s})} + x^{-(2^{s})}=2$ dans $A$.}
D'apr\`es b), nous avons 
\[
x^{2^{s-1}}+ x^{-2^{s-1}}=L_s.
\]
Or $L_s=L_{s-1}^2-2=-2$ d'apr\`es l'hypoth\`ese.
Comme $n$ est impair, nous avons $p\neq 2$ et donc
$L_s=-2\neq 2$. Finalement, nous avons 
\[
x^{2^s}+x^{-2^s} = L_{s+1}=L_s^2-2=4-2=2.
\]

\item  {\em Montrer que pour $a\in A$, on a $a^2=0$ ssi $a=0$.}
1er cas : supposons que $X^2-4X+1$ est irr\'eductible. Alors $A$ est
un corps. Donc $A$ est int\`egre, c'est-\`a-dire que
$uv=0$ implique $u=0$ ou $v=0$ dans $A$. En particulier
$a^2=0$ implique $a=0$ dans $A$.

2e cas : supposons que $X^2-4X+1$ est r\'eductible et qu'il
admet deux racines distinctes $\alpha$ et $\beta$.
Alors $X-\alpha$ et $X-\beta$ sont premiers entre eux
et d'apr\`es le th\'eor\`eme chinois, nous avons un isomorphisme
\[
A \iso \F_p[X]/(X-\alpha)\;\times\; \F_p[X]/(X-\beta).
\]
Nous savons aussi que $\F_p[X]/(X-\alpha)$ est isomorphe
\`a $\F_p$ par l'application qui \`a la classe de $P$
associe $P(\alpha)$. Nous obtenons donc un isomorphisme
\[
A \iso \F_p \times \F_p.
\]
Soit $(a_1, a_2)$ l'image de $a$ par cet isomorphisme.
Comme $a^2=0$, nous avons $(a_1,a_2)^2=0$ ce qui veut
dire que $a_1^2=0$ et $a_2^2=0$. Comme $\F_p$ est un
corps, il s'ensuit que $a_1=0$ et $a_2=0$ et donc $a=0$.

3e cas : finalement, supposons que $X^2-4X+1$ est r\'eductible
avec une racine double $\alpha$. Alors 
\[
X^2-4X+1=(X-\alpha)^2= X^2-2\alpha X + \alpha^2
\]
et $2\alpha=4$. Comme $p\neq 2$, il s'ensuit que $\alpha=2$.
Donc $2$ est racine de $X^2-4X+1$, c'est-\`a-dire que
$-3=0$ dans $A$ et donc dans $\F_p$. Donc $p=3$. 
Mais $2^s-1=(-1)^s-1=-2$ dans $\F_3$ car $s$ est impair.
Donc $p\neq 3$ est ce cas est impossible.


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

Si $x^m=1$ alors clairement $x^m+x^{-m}=1+1=2$. R\'eciproquement,
si $x^m+x^{-m}=2$, alors pour $a=x^m-1$, nous avons
$a^2=x^{2m}-2x^m +1 = x^m(x^m-2+x^{-m}) =0$. Donc $a=0$
d'apr\`es d), et $x^m=1$.

\item {\em Montrer que $x$ est d'ordre $2^s$ dans le groupe $A^*$.}
D'apr\`es c) et e) nous avons $x^{2^s}=1$ et $x^{2^{s-1}}\neq 1$.
La premi\`ere condition montre que l'ordre de $x$ est
un diviseur de $2^s$. La deuxi\`eme montre que l'ordre
de $x$ ne peut pas \^etre un diviseur propre de $2^s$.
Donc l'ordre de $x$ est \'egal \`a $2^s$.


\item {\em Supposons le polyn\^ome $X^2-4X+1$ r\'eductible sur
$\F_p$. Montrer qu'on a $x^{p-1} =1$.}
Nous avons vu dans d), que si $X^2-4X+1$ est r\'eductible,
il admet deux racines distinctes et nous avons l'isomorphisme
\[
A \iso \F_p \times \F_p.
\]
Soit $(x_1, x_2)$ l'\'el\'ement qui correspond \`a $x$
par cet isomorphisme. Alors comme $x$ est inversible,
il en va de m\^eme pour $x_1$ et $x_2$ et nous avons
$(x_1, x_2)^{p-1}=(1,1)$. Il s'ensuit que $x^{p-1}=1$.


\item {\em 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$.}

D'apr\`es a), nous avons $x+x^{-1}=4$. Donc
$x^p+x^{-p}= (x+x^{-1})^p = 4^p =4$, d'apr\`es le petit
th\'eor\`eme de Fermat. Nous obtenons donc
\[
x^p+x^{-p}= x+x^{-1}
\]
et
\[
(x^{p+1}-1)(x^{p-1}-1) = (x^{2p}+x^{p+1}+x^{p-1}+1)
=x^p\,(x^p - x - x^{-1} + x^{-p}) = 0.
\]
Comme $A$ est un corps, il s'ensuit que $x^{p+1}=1$
ou $x^{p-1}=1$.


\item {\em Montrer que $p=2^s-1$.}
D'apr\`es g) et h) nous avons $x^{p-1}=1$ ou $x^{p+1}=1$.
Or l'ordre de $x$ dans $A^*$ est $2^s$ d'apr\`es f).
Dans le premier cas, $2^s$ doit \^etre un diviseur de
$p-1$ et donc $2^s \leq p-1$, $2^s-1 \leq p-2$ ce qui
est impossible puisque $p$ divise $2^s-1$.
Donc $x^{p+1}=1$ et $p+1$ est un multiple de $2^s$.
Donc $2^s\leq p+1$ et $2^s-1\leq p$. De l'autre c\^ot\'e,
$p$ divise $2^s-1$. Donc $p=2^s -1$.
\end{sublist}


\item {\bf Sur les carr\'es de $\F_p$\,.}
Soit $p$ un nombre premier impair. 
\begin{sublist}
\item {\em Soit $a\in \F_p^*$. 
Montrer que $a^{(p-1)/2} = \pm 1$.}
Consid\'erons $u=a^{(p-1)/2}$. Nous avons $u^2=a^{p-1}=1$
d'apr\`es le petit th\'eor\`eme de Fermat.
Donc $(u-1)(u+1)=0$ et $u=\pm 1$ car $\F_p$ est un corps.

\item {\em 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.}
Supposons que $a=b^2$. Alors $a^{(p-1)/2} = b^{p-1}=1$
d'apr\`es le petit th\'eor\`eme de Fermat.
Supposons maintenant que $a^{(p-1)/2}=1$.
Soit $g$ un g\'en\'erateur du groupe cyclique $\F_p^*$.
Soit $l\in \Z$ tel que $g^l=a$. Alors $a^{(p-1)/2}= g^{l (p-1)/2} =1$.
Comme $g$ est d'ordre $p-1$, il s'ensuit que
$l(p-1)/2$ est divisible par $p-1$ et que $l/2$ est un entier.
Si nous posons $b=g^{l/2}$, nous avons $a=b^2$.

D'apr\`es a), nous savons que $a^{(p-1)/2}=\pm 1$.
Donc si $a$ n'est pas un carr\'e et donc $a^{(p-1)/2} \neq 1$, 
on doit avoir $a^{(p-1)/2}=-1$.

\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 {\em Montrer \`a l'aide de 3) b) et de la
r\'eciprocit\'e quadratique qu'on a
$2^{(p-1)/2}=1$ et $3^{(p-1)/2}=-1$ dans $\F_p$.}

D'apr\`es 3 b) et la r\'eciprocit\'e quadratique, il
suffit de montrer que $p\equiv \pm 1 \; (8)$. Or
$p=2^s-1$ et $s$ est un entier impair $\geq 3$. Donc
$p\equiv -1\; (8)$. Pour calculer la classe de $p$
modulo $12$, d'apr\`es le lemme chinois, il suffit de
calculer les classes modulo $3$ et $4$. Nous avons
$p\equiv -1\;(4)$ car nous avons m\^eme $p\equiv -1\;(8)$.
En outre $p\equiv (-1)^s-1\equiv -2\;(3)$. Il s'ensuit que
$p\equiv 7\;(12)$. Donc $p \not \equiv \pm 1\;(12)$
et l'affirmation s'ensuit d'apr\`es 3 b) et la r\'eciprocit\'e
quadratique.


\item {\em 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}).
\]
}
On a 
\begin{eqnarray*}
y^2 & = & (x-2)^2= x^2-4x+4 = (x^2-4x+1)+3= 3\ko \\
(1+y)^2 & = & 1+2y+y^2 = 2x -4+1+3 = 2x \ko\\
(1-y)^2 & = & 1-2y+y^2 = -2x +4 +1 +3 = 2(4-x) = 2 x^{-1}.
\end{eqnarray*}
Donc
\begin{eqnarray*}
2^{(p+1)/2} L_s  & = & 2^{(p+1)/2} (x^{2^{s-1}} + x^{-2^{s-1}}) \\
   & = & 2^{2^{s-1}} \, (x^{2^{s-1}}+x^{-2^{s-1}}) = 
                    (2x)^{2^{s-1}} + (2x^{-1})^{2^{s-1}} \\
   & = & (1+y)^{2^s} +(1-y)^{2^s} = (1+y)^{p+1} + (1-y)^{p+1}.
\end{eqnarray*}
En utilisant que $(a+b)^{p+1} = (a+b)^p (a+b) =
(a^p+b^p)(a+b)$ dans $A$ nous obtenons
\begin{eqnarray*}
(1+y)^{p+1} & = & (1+y^p)(1+y) = 1+y^p + y + y^{p+1}\ko \\
(1-y)^{p+1} & = & (1-y^p)(1-y) = 1-y^p - y + y^{p+1}. 
\end{eqnarray*}
Donc
\[
(1+y)^{p+1} + (1-y)^{p+1} = 2(1+y^{p+1})) = 2(1+(y^2)^{(p+1)/2})
 = 2(1+3^{p+1}/2).
\]


\item {\em 
Conclure qu'on a $L_s\equiv -2\;(p)$ et $L_{s-1}\equiv 0\;(p)$.}
D'apr\`es a), on a 
\begin{eqnarray*}
2^{(p+1)/2} & = & 2\times 2^{(p-1)/2} = 2 \ko\\
3^{(p+1)/2} & = & 3\times 3^{(p-1)/2} = -3.
\end{eqnarray*}
D'apr\`es b), on obtient $2 L_s = 2\,(1-3) = 2 \,(-2)$.
Donc $L_s=-2=L_{s-1}^2 -2$. Il s'ensuit que $L_{s-1}^2=0$
et $L_{s-1}=0$.



\end{sublist}

\end{list-of-exercises}

\end{document}











