\documentstyle{article}
\setlength{\oddsidemargin}{-0.5cm}
\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}}                                                   
                                                                



% 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{\Q}{{\mbox{\bf Q}}}
%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{\La}{\Lambda}
\newcommand{\lam}{\lambda}
\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{\larr}[1]{\stackrel{#1}{\leftarrow}}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
\newcommand{\pl}{\parallel}




\newcommand{\plus}{\oplus}
\newcommand{\pgcd}{\mbox{PGCD}\,}
\newcommand{\add}[1]{\Z/#1}
\newcommand{\ind}{\mbox{{\rm ind}}}

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

\setlength{\baselineskip}{0.1cm}
\begin{list-of-exercises}
\item Soit $x$ le nombre de candidats. D'apr\`es les 
informations fournies, nous avons
\begin{eqnarray*}
x & \equiv & 3  \;\; (5) \\
x & \equiv & 3  \;\; (6) \\
x & \equiv & 4 \;\; (7).
\end{eqnarray*}
Les nombres $5,6,7$ sont premiers entre eux deux \`a deux. 
Ce syst\`eme de congruences admet donc une solution 
$x$ dont la classe modulo $5\times 6\times 7 = 210$ est unique.
Pour trouver $x$, 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/210 \iso \Z/5 \plus \Z/6 \plus \Z/7.
\]
Nous avons 
\[
\begin{array}{rcccrcl}
42\, u_1 + 5\, v_1  =  1; & \mbox{sol. part.} & 
42 \times 3+5\times (-25)  =  1. & \mbox{Posons } & x_1=126. \\
35\, u_2 + 6\, v_2  =  1; & \mbox{sol. part.} &
35\times(-1) + 6 \times 6   =  1. & \mbox{Posons } & x_2=-35. \\
30\, u_3 + 7\, v_3  =  1; & \mbox{sol. part.} &
30\times (-3) + 7 \times 13  =  1. & \mbox{Posons } &  x_3=-90 .
\end{array}
\]
Nous avons donc
$x \equiv 3\times 126+3\times (-35) + 
4\times (-90) \equiv -87 \equiv 123
\;\; (210)$.  
En conclusion, {\bf $123$ candidats participertont \`a l'\'epreuve.}

\item Supposons que $H$ est distingu\'e et que $x\in G$. Nous
avons $xHx^{-1}=H$, donc 
$xH=Hx$ et $x'=x$ convient.

R\'eciproquement, supposons la condition v\'erifi\'ee. 
Soit $x\in G$ et soit $x'\in G$ tel que
$xH=Hx'$. Alors $x'=ex'=xh$ pour
un $h\in H$ car $ex'\in Hx'$.
Donc $xH=Hx'=Hxh$. En multipliant
cette \'egalit\'e \`a droite par
$h^{-1}$, nous trouvons $xH=Hx$,
c'est-\`a-dire que $xHx^{-1}=H$ et
que $H$ est bien distingu\'e.

\item \begin{sublist}
\item Nous avons 
\[
a\equiv 1+2+0+1+0+0+1+2+4+1+2\equiv 0 \;\;(7)
\] et $r=0$.
\item Le nombre $p=47$ est premier.
D'apr\`es le petit th\'eor\`eme de 
Fermat, nous avons $x^p\equiv x\;\;(p)$ pour tout entier $x$.
En particulier $a=23^p\equiv 23\;\;(p)$
et $r=23$. 

\item D'apr\`es le th\'eor\`eme
d'Euler, nous avons $x^{\phi(36)}\equiv 1\;\;(36)$
pour tout entier $x$ premier \`a
$36$. Or, $\phi(36)=\phi(4)\phi(9)=2\times 6=12$. 
Donc $17^{13}\equiv 17^1
\;\;(36)$ et $r=17$.


\item Nous avons $495=5\times 9\times 11$
et les nombres $5, 9$ et $11$ sont premiers entre eux deux \`a deux.
Ainsi, d'apr\`es le th\'eor\`eme chinois (appliqu\'e deux fois),
pour conna\^{\i}tre le reste de $a$ modulo $495$, il suffit de
d\'eterminer les restes de $a$ modulo $5$, $9$ et $11$.

Nous avons $191\equiv 1\;\;(5)$ et donc $a\equiv 1\;\;(5)$.

Nous avons $191\equiv 4\;\;(11)$. Comme $4$ et $11$ sont premiers
entre eux, le reste de $4^{(141^{128})}$ ne d\'epend que
du reste de $141^{128}$ modulo $10$. Ce dernier vaut $1$,
car $141\equiv 1 \;\;(10)$.

Finalement nous avons $191\equiv 2\;\;(9)$ et comme
$2$ et $9$ sont premiers entre eux, le reste de $2^{(141^{128})}$
modulo 9
ne d\'epend que du reste de $141^{128}$ modulo $\phi(9)=6$.
Nous avons $141\equiv 3\;\;(6)$ et $3^2\equiv 3\;\;(6)$.
En appliquant plusieurs fois la seconde congruence, nous trouvons
\[
3^{128}=(3^2)^{64} \equiv 3^{64} \equiv (3^2)^{32} 
\equiv 3^{32} \equiv  \ldots \equiv 3\;\;(6).
\]
Ainsi, $2^{(141^{128})}\equiv 2^3\equiv -1\;\;(9)$.

Nous obtenons ainsi le syst\`eme de congruences
\begin{eqnarray*}
a & \equiv & 1 \;\;(5) \\
a & \equiv & -1 \;\;(9) \\
a & \equiv & 4 \;\;(11) .
\end{eqnarray*}
Nous le r\'esolvons par la m\'ethode bien connue (voir le corrig\'e
de l'exercice 1) pour trouver $a \equiv 26\;\;(495)$. En conclusion,
{\bf le reste de la division de $191 ^{(141^{128})}$ par $495$ est
\'egal \`a $26$.}

\end{sublist}


\item Montrons que (i) implique (ii). 
Si $n$ est premier on sait que le groupe $(\Z/n\Z)^*$ 
est cyclique.
Soit $a$ un entier dont la classe
engendre $(\Z/n\Z)^*$. Alors $a$ est 
d'ordre $n-1$ et on a donc 
$a^{(n-1)}\equiv 1\;\;(n)$ et 
$a^d\not\equiv 1\;\;(n)$ pour tout 
diviseur propre $d$ de $n-1$. 
En particulier, $a^{(n-1)/q}\not\equiv 1\;\;(n)$ 
pour tout facteur premier $q$ de $n-1$. 

Montrons que (ii) implique (i). 
Si on a $a^{n-1}\equiv 1\;\;(n)$, 
alors $a$ est clairement inversible 
dans $\Z/n\Z$ (d'inverse $a^{n-2}$). 
L'ordre de $a$ dans le groupe $(\Z/n\Z)^*$ 
divise $(n-1)$ et ne divise pas $(n-1)/q$, 
pour tout facteur premier $q$ de $n-1$. 
Donc l'ordre est \'egal \`a $n-1$ et le
groupe $(\Z/n\Z)^*$ a $n-1$ \'el\'ements 
(au moins). Les classes de $1, \ldots, n-1$ 
appartiennent donc \`a $(\Z/n\Z)^*$ ce qui 
montre que tout entier positif inf\'erieur \`a $n$ 
est premier \`a $n$. Donc $n$ est bien premier. 

\item
\begin{sublist}
\item Le nombre $5$ admet la d\'ecomposition 
en facteurs premiers $5=(1+2i)(1-2i)$ dans $\Z[i]$. 
Donc $5^n=(1+2i)^n (1-2i)^n$ est une 
d\'ecomposition en facteurs premiers dans $\Z[i]$. 
Nous avons $(x+iy)(x-iy)=(1+2i)^n(1-2i)^n$.
D'apr\`es l'unicit\'e de la d\'ecomposition 
en facteurs premiers dans $\Z[i]$, 
{\bf la d\'ecomposition en facteurs premiers 
de $(x+iy)$ doit \^etre de la forme 
\[
x+iy= u(1+2i)^a (1-2i)^b
\]
o\`u $u$ est une unit\'e de $\Z[i]$
et $a,b$ sont des entiers positifs
tels que $a+b=n$ } (car la norme de $x+iy$
est de $5^n=N(1+2i)^a N(1-2i)^b=5^a \times 5^b$). 

\item D'apr\`es a), si $(x,y)$ est une solution, 
alors $x+iy=u(1+2i)^a(1-2i)^{n-a}$, o\`u 
$u\in\{1,-1,i,-i\}$ et $0\leq a\leq n$. 
Il y a donc au plus $4(n+1)$ solutions. 
\end{sublist}

\item 
\begin{sublist}
\item Les classes de $1$ et de $-1$
sont des solutions  \'evidentes de $x^2=1$ 
dans $\Z/p^m \Z$. Il n'y a
pas d'autres solutions. En effet, 
comme $p$ est impair, le groupe $(\Z/p^m \Z)^*$ 
est cyclique d'ordre pair. Il contient donc exactement
deux \'el\'ements qui v\'erifient
$x^2=1$. En conclusion, {\bf les solutions 
ont les nombres $\pm 1+k\times p^m$, $k\in \Z$}.

\item Ecrivons  $n=q_1 q_2 \ldots q_r$ 
o\`u les $q_i$ sont des puissances strictement 
positives de nombres premiers distincts d
eux \`a deux. D'apr\`es le lemme chinois, la 
projection canonique $p$ est un isomorphisme d'anneaux
\[
\Z/n\Z \iso (\Z/q_1\Z)\times (\Z/q_2\Z) \times\ldots \times (\Z/q_r\Z).
\]
Si on note $p(x)=(x_1, \ldots, x_r)$, 
l'\'equation $x^2=1$ se traduit par 
\[
(x_1, \ldots, x_r)^2=(1,\ldots , 1)
\]
c'est-\`a-dire par les \'equations
$x_i^2=1$ dans $\Z/q_i\Z$, $i=1, \ldots, r$. 
Comme $n$ est impair, les $q_i$ le sont aussi, 
et d'apr\`es a), chaque \'equation $x_i^2=1$ admet 
exactement $2$ solutions. Ainsi, l'\'equation
$(x_1, \ldots, x_r)^2=(1,\ldots, 1)$
admet $2^r$ solutions. En conclusion,
{\bf le nombre de solutions modulo $n$ 
de l'\'equation $x^2=1$ est de
$2^r$, o\`u $r$ est le nombre de facteurs 
premiers distincts de $n$.
Il y a exactement $2$ solutions si et seulement 
si $n$ est puissance d'un nombre premier (impair).}

\item Ecrivons $n=2^m u$ o\`u $u$ est impair. 
D'apr\`es le lemme chinois, la projection $p$ 
est un isomorphisme d'anneaux
\[
\Z/n\Z \iso 
(\Z/u\Z)\times(\Z/2^m \Z).
\]
Si l'on note $p(x)=(x_1, x_2)$, l'\'equation $x^2=1$ dans $\Z/n\Z$
se traduit par les \'equations
$x_1^2=1$ dans $\Z/u\Z$ et
$x_2^2=1$ dans $\Z/2^m\Z$. D'apr\`es b), 
nous connaissons le nombre de solutions 
de $x_1^2=1$ dans $\Z/u\Z$. Nous savons que
$(\Z/2^m\Z)^*$ est isomorphe \`a
$\{1\}$ si $m\leq 1$; \`a $\Z/2\Z$ si $m=2$; \`a 
$\Z/2\times \Z/2^{(m-2)}\Z$ si $m\geq 3$. 
L\'equation $x_2=1$ admet donc $1$, 
resp. $2$, resp. $4$ solutions si $m\leq 1$, 
resp. $m=2$, resp. $m\geq 3$. En conclusion, 
{\bf si $2^m$ est la puissance maximale de $2$ 
qui divise $n$ et que $r$ est le nombre de 
facteurs premiers impairs de $n$, le nombre 
de racines modulo $n$ de l'\'equation $x^2=1$ 
est de  $2^r$ si $m\leq 1$, de $2^{r+1}$ si 
$m=2$, et de $2^{r+2}$ si $m\geq 3$.}
\end{sublist}



\end{list-of-exercises}
\end{document}