\documentstyle{article}
%\documentclass{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}



%sublist
\newcounter{point}
\newenvironment{sublist}{
\begin{list}{\alph{point})}{\usecounter{point}
\setlength{\itemsep}{0cm}\setlength{\leftmargin}{1.2em}}
}{\end{list}}
                                                                


%liste d'exercices
\newcounter{exo}
\newenvironment{list-of-exercises}{
\begin{list}{\arabic{exo})}{\usecounter{exo}            
\setlength{\itemsep}{0cm}}                                      
}{\end{list}}                                                   
                                                                
\newcommand{\plus}{\oplus}
\newcommand{\pgcd}{\mbox{PGCD}\,}
\newcommand{\ppcm}{\mbox{PPCM}\,}



% 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{\mult}[1]{(\Z/#1\Z)^*}
\newcommand{\R}{{\mbox{\bf R}}}
\newcommand{\Q}{{\mbox{\bf Q}}}
\newcommand{\F}{{\mbox{\bf F}}}
%Comma, forall
\newcommand{\ko}{\: , \;}
\newcommand{\fa}{\forall \,}
%Overline, Underline
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}

\newcommand{\eps}{\varepsilon}
\newcommand{\Del}{\Delta}
\newcommand{\del}{\partial}
%\renewcommand{\phi}{\varphi}
\newcommand{\Ga}{\Gamma}
\newcommand{\Om}{\Omega}
\newcommand{\om}{\omega}
\newcommand{\Si}{\Sigma}
\newcommand{\si}{\sigma}


%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{\lambdarr}[1]{\stackrel{#1}{\leftarrow}}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
\newcommand{\pl}{\parallel}



\newcommand{\mone}{15}
\newcommand{\mtwo}{28}
\newcommand{\mthree}{31}
\newcommand{\aone}{5}
\newcommand{\atwo}{9}
\newcommand{\athree}{3}
\newcommand{\prodmi}{13020}
\newcommand{\uone}{7}
\newcommand{\vone}{(-405)}
\newcommand{\utwo}{5}
\newcommand{\vtwo}{(-83)}
\newcommand{\uthree}{11}
\newcommand{\vthree}{(-149)}
\newcommand{\xone}{6076}
\newcommand{\xtwo}{2325}
\newcommand{\xthree}{4620}
\newcommand{\finalresult}{65}



\newcommand{\E}[1]{E\,(#1)}

%\renewcommand{\thepage}{ }


\begin{document}
\begin{center}
MT 282          \hfill Universit\'e Paris 7 \\
04/09/97        \hfill  U.F.R. de Math\'ematiques\\
\mbox{ }        \hfill B. Keller\\[0.5cm]
{\large\bf Un corrig\'e de l'examen de Septembre 1997}
\end{center}

\begin{list-of-exercises}

\item
Soit $d$ le nombre de danseurs de samba.
D'apr\`es les informations fournies, nous avons
\begin{eqnarray*}
d & \equiv & \aone   \;\; (\mone) \\
d & \equiv & \atwo   \;\; (\mtwo) \\
d & \equiv & \athree   \;\; (\mthree).
\end{eqnarray*}
Les nombres $\mone,\mtwo,\mthree$ sont premiers entre eux deux \`a deux. 
Ce syst\`eme de congruences admet donc une solution 
$d$ dont la classe modulo 
$\mone\times \mtwo\times \mthree = \prodmi$ est unique.
Pour trouver $d$, nous d\'eterminons
d'abord $x_1$, $x_2$, $x_3$ dont les classes sont les images
r\'eciproques de $(1,0,0), (0,1,0), (0,0,1)$ par la projection
\[
\Z/\prodmi \iso \Z/\mone \times \Z/\mtwo \times \Z/\mthree.
\]
Nous avons 
\[
\begin{array}{rcccrcl}
\mtwo\times \mthree\, u_1 + \mone\, v_1  =  1; & \mbox{sol. part.} & 
\mtwo\times \mthree\times\uone  + \mone \times\vone   =  1. \\
\mone\times \mthree\, u_2 + \mtwo\, v_2  =  1; & \mbox{sol. part.} &
\mone\times \mthree \times\utwo  + \mtwo \times\vtwo    =  1.  \\
\mone\times \mtwo  \, u_3 + \mthree\, v_3  =  1; & \mbox{sol. part.} &
\mone\times \mtwo\times\uthree  + \mthree \times\vthree  =  1 \\
\end{array}
\]
Posons
\[
x_1=\mtwo\times \mthree\times \uone=\xone \ko \quad
x_2=\mone\times \mthree\times \utwo=\xtwo \ko \quad
x_3=\mone\times \mtwo\times \uthree=\xthree .
\]
Nous avons donc 
$l \equiv \aone\times\xone+\atwo\times\xtwo+ \athree\times \xthree 
\equiv \finalresult \;(\prodmi)$. 
On a donc $d=\finalresult+k\times \prodmi$
pour un $k\in\Z$ et la valeur positive minimale de $d$
est $\finalresult$. {\em Le nombre de danseurs de samba est
(au moins) de $65$.}


\item
\begin{sublist}
\item $a=1000^{1996}$, $b=1997$. Le nombre $1997$ est premier
et ne divise pas $1000$. D'apr\`es le petit th\'eor\`eme de
Fermat, nous avons donc $1000^{1996} \equiv 1 \; (1997)$
et $r=1$.

\item $a=1+3+3^2+ \cdots + 3^{125}$, $b=127$. 
Nous avons
\[
a = \frac{3^{126}-1}{3-1}
\]
et donc $2a=3^{126}-1$. Le nombre $127$ est premier et ne
divise pas $3$. D'apr\`es le petit th\'eor\`eme de Fermat,
on a donc $3^{126} \equiv 1 \; (127)$ et $2a \equiv 0\; (127)$.
Puisque $2$ est inversible modulo $127$, il s'ensuit que
$a \equiv 0\;(127)$ et donc $r=0$.

\item $a=100^{192}$, $b=221$. Nous avons $b=13\times 17$ et
$\phi(b)=12\times 16=192$. Puisque $100$ est premier avec
$221$, nous avons $100^{192} \equiv 1\; (221)$ d'apr\`es
le th\'eor\`eme d'Euler. Donc $r=1$.

\item $a=65^{(65^{6})}$, $b=127$.
Le nombre $b=127$ est premier et ne divise pas $65$.
D'apr\`es le petit th\'eor\`eme de Fermat, la classe de
$a$ modulo $127$ ne d\'epend donc que de la classe de
$c=65^6$ modulo $126$. Nous avons $126=2\times 7 \times 9$.
R\'eduisons modulo les trois facteurs :
\begin{eqnarray*}
65^6 & \equiv & 1^6 \equiv 1 \; (2) \\
65^6 & \equiv & 2^6 \equiv 1 \; (7) \quad \mbox{(Fermat)} \\
65^6 & \equiv & 2^6 \equiv 1 \; (9) \quad \mbox{(Euler : $\phi(9)=6$)}
\end{eqnarray*}
Puisque $2$, $7$ et $9$ sont premiers entre eux deux \`a deux,
il s'ensuit d'apr\`es le th\'eor\`eme chinois que
$65^6\equiv 1\;(126)$. Donc $a \equiv 65^1 \equiv 65 \;(127)$
et $r=65$.
\end{sublist}

\item D'apr\`es le th\'eor\`eme chinois, nous avons
$A \iso \Z/15\Z$. Le groupe $A$ est donc cyclique d'ordre $15$.
L'\'el\'ement $(\ol{1}, \ol{1})$ en est un g\'en\'erateur.

Puisque $17$ est premier, le groupe $B=(\Z/17\Z)^*$ est cyclique
d'ordre $16$. Il est engendr\'e par la classe de $3$.
En effet, nous avons $3^2=9$, $3^4=-4$, $3^8=-1$ dans $\Z/17\Z$.
Donc $3$ est bien d'ordre $16$.

D'apr\`es un th\'eor\`eme du cours, l'application
\[
\F_3 \times \F_3 \ra \F_3[X]/(X^2+1) \ko
(a,b) \mapsto aX+b
\]
est un isomorphisme de groupes (pour l'addition).
Il s'ensuit que le groupe $C$ est d'ordre $9$ et qu'il
n'est pas cyclique car l'ordre maximal d'un \'el\'ement
y est de $3$ (puisque c'est le cas pour $\F_3\times \F_3$).


Le polyn\^ome $X^2+1$ n'admet pas de racine dans $\F_7$
(car les seuls carr\'es modulo $7$ sont $1$, $4$ et $2$).
Puisqu'il est de degr\'e $2$, il est donc irr\'eductible,
et $\F_7[X]/(X^2+1)$ est un corps (\`a $7^2=49$ \'el\'ements).
Il s'ensuit que le groupe $D=(\F_7[X]/(X^2+1)^*$ est cyclique
d'ordre $49-1=48$. Cherchons un g\'en\'erateur : la classe
de $2$ est clairement d'ordre $3$ dans $\F_7^*$ et donc
dans $D$ (qui contient $\F_7$ comme le sous-groupe image
des polyn\^omes constants non nuls). On v\'erifie aussi
que  l'\'el\'ement $\alpha=2x+3$ est d'ordre
$16$ (on a $\alpha^2=-2x-2$, $\alpha^4=x$ et $\alpha^8=-1$).
Puisque $3$ et $16$ sont premiers entre eux et que
$D$ est commutatif, il s'ensuit que $2\alpha=4x+6$
est d'ordre $3\times 16=48$. L'\'el\'ement $4x+6$
est donc un g\'en\'erateur de $D$.

\item 
\begin{sublist}

\item D'apr\`es un th\'eor\`eme du cours, si $P\in \F_p[X]$
est de degr\'e $n$, alors les \'el\'ements de 
$\F_p[X]/(P)$ s'\'ecrivent de fa\c{c}on unique sous la
forme $a_0+a_1 x + \ldots + a_n x^{n-1}$, $a_i\in \F_p$.
Comme $X^p$ est de degr\'e $p$, l'affirmation en r\'esulte.

\item Nous avons
\[
(1+bx)(1-bx+(bx)^2-(bx)^3 + \ldots + (-1)^{p-1} (bx)^{p-1}) = 1.
\]
L'\'el\'ement $1+bx$ est donc inversible d'inverse
$1-bx+(bx)^2-(bx)^3 + \ldots + (-1)^{p-1} (bx)^{p-1}$.

\item L'\'el\'ement $1+a'_0 b$ est inversible d'apr\`es b).
Donc le produit $a_0 (1+a'_0 b)= a_0 + bx$ est inversible
aussi (d'inverse $a'_0 (1+a'_0 b)^{-1}$).

\item Si $a_0 \in \F_p^*$, alors $a=a_0+bx$ o\`u
$b=a_1 + a_2 x + \ldots a_{p-1} x^{p-2}$. Cet \'el\'ement
est inversible d'apr\`es c). Si $a_0=0$, alors $a=bx$ et
$a^p=b^p x^p =0$. Dans ce cas $a$ ne peut \^etre inversible
(sinon, $a^p=0$ le serait aussi; contradiction).

\item Clairement $1=1+0\cdot x$ appartient \`a $U$ et si
$1+bx$ et $1+b'x$ appartiennent \`a $U$ alors
$(1+bx)(1+b'x)=1+x(b+b'+bb'x)$ appartient \`a $U$.
Donc $U$ est bien un sous-groupe. Ce sous-groupe
est form\'e des \'el\'ements 
$1+a_1 x+ a_2 x^2 + \ldots + a_{p-1} x^{p-1}$ qui,
d'apr\`es a), sont au nombre de $p^{p-1}$. Donc
$U$ est d'ordre $p^{p-1}$.

L'application $\phi$ est un homomorphisme de groupes
car
\begin{eqnarray*}
\phi((a_0, 1+bx), (a'_0, 1+b'x)) 
& = & \phi((a_0 a'_0, (1+bx)(1+b'x)) = a_0 a'_0 (1+bx)(1+b'x) \\
& = & a_0 (1+bx) a'_0 (1+b'x) = \phi((a_0, 1+bx)) \phi((a'_0, 1+b'x)).
\end{eqnarray*}
L'application $\phi$ est bijective d'inverse
$\psi : a_0 + bx \mapsto (a_0, 1+a_0^{-1} bx)$.
Donc c'est un isomorphisme de groupes.

\item Soit $1\leq i \leq p-1$ et
$a=1+x^i$. Alors $a^p= (1+x^i)^p = 1+x^{ip} =1$.
Il s'ensuit que si $\ol{k} \in \Z/p\Z$,
alors $(1+x^i)^k$ ne d\'epend pas du choix
du repr\'esentant $k$ de $\ol{k}$.
Donc l'application $f$ est bien d\'efinie.

\item Soit $I$ l'image de $f$. Soit 
$U_j=\{ 1+ bx^j \;|\; b\in A\}$, $1 \leq j \leq p$.
Montrons par r\'ecurrence descendante sur $j$
que $U_j\subset I$. Clairement $U_p=\{1\}$
est contenu dans $I$. Supposons que nous avons
d\'ej\`a montr\'e que $U_{j+1}$ est contenu dans
$I$. Soit $a=1+a_j x^j +b x^{j+1} \in U_j$.
Alors
\[
(1+x^j)^{-a_j} a = 
(1-a_j x^j + b' x^{j+1}) (1+a_j x^j + b x^{j+1}) =
1+b'' x^{j+1} \in U_{j+1}
\]
pour certains $b', b'' \in A$. Donc 
$a$ est le produit de $(1+x^j)^{a_j}$
par un \'el\'ement de $U_{j+1}$. Puisque
$(1+x^j)^{a_j}$ appartient \`a $I$ et
que $U_{j+1}$ est contenu dans $I$ (par
l'hypoth\`ese de r\'ecurrence), il s'ensuit
que $a$ appartient \`a $I$.


\item L'application $g$ est la compos\'ee de
$\phi$ avec
\[
\Phi : \Z/(p-1)/\Z \times (\Z/p\Z)^{p-1} \ra
\F_p^* \times U \ko 
(\ol{k}, \ol{k_1}, \ldots, \ol{k_{p-1}}) 
\mapsto (\zeta^k, f(\ol{k_1}, \ldots, \ol{k_{p-1}})).
\]
L'application $\Phi$ est un isomorphisme car
$\ol{k} \mapsto \zeta^k$ est un isomorphisme
de $\Z/(p-1)\Z$ sur $\F_p^*$ et
$f$ est un isomorphisme $(\Z/p\Z)^{p-1}$ sur $U$.
Donc $g=\phi\circ \Phi$ est un isomorphisme. 

\end{sublist}


\end{list-of-exercises}

\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
