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



%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 \\
01/02/94	\hfill  U.F.R. de Math\'ematiques\\
\mbox{ }	\hfill B. Keller\\[0.5cm]
{\large\bf Un corrig\'e de l'examen du 01.02.95}
\end{center}

\begin{list-of-exercises}

\item Soit $x$ le nombre de dents dont il faut faire avancer la
grande roue. D'apr\`es les informations fournies,
nous avons
\begin{eqnarray*}
x & \equiv & 1  \;\; (25) \\
x & \equiv & 1  \;\; (8) \\
x & \equiv & 2 \;\; (9).
\end{eqnarray*}
Les nombres $25,8,9$ sont premiers entre eux deux \`a deux. 
Ce syst\`eme de congruences admet donc une solution 
$x$ dont la classe modulo $25\times 8\times 9 = 1800$ 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/1800 \iso \Z/25 \plus \Z/8 \plus \Z/9.
\]
Nous avons 
\[
\begin{array}{rcccrcl}
72\, u_1 + 25\, v_1  =  1; & \mbox{sol. part.} & 
72\times 8 + 25 \times (-23)  =  1. & \mbox{Posons } & x_1=576. \\
225\, u_2 + 8\, v_2  =  1; & \mbox{sol. part.} &
225\times 1 + 8 \times (-28)   =  1. & \mbox{Posons } & x_2=225. \\
200\, u_3 + 9\, v_3  =  1; & \mbox{sol. part.} &
200\times (-4) + 9 \times 89  =  1 & \mbox{Posons } &  x_3=-800 .
\end{array}
\]
Nous avons donc
$x \equiv 1\times 576+1\times 225 -2\times 800 \equiv -799 \equiv 1001
\;\; (1800)$.  {\bf Il faut faire avancer la grande roue de $1001$ dents.}



\item Nous avons $14=2\times 7$, $12=3\times 4$ et $72=8\times 9$. 
Trois applications du th\'eor\`eme chinois donnent donc un
isomorphisme entre $A$ et
\[
D= \add{2}\plus\add{4}\plus\add{8} \plus \add{3}\plus\add{7}\plus \add{9}.
\]
De m\^eme, les factorisations $6=2\times 3$, $28=4\times 7$ et
$72=8\times 9$ permettent de conclure que $B\cong D$; et
les factorisations $6=2\times 3$, $36=4\times 9$, $56=7\times 8$
montrent que $C\cong D$. Donc {\bf les groupes $A$, $B$ et $C$
sont isomorphes deux \`a deux.}



\item Notons $P$ l'ensemble des produits $hk$, o\`u $h\in H$ et
$k\in K$. 

L'\'el\'ement neutre $e$ de $G$ appartient \`a $K$ et $H$. 
Donc $e=ee$ appartient aussi \`a $P$. 

Supposons maintenant que $h_1 k_1$ et $h_2 k_2$ sont deux 
\'el\'ements de $P$ (o\`u $h_1, h_2 \in H$ et $k_1, k_2\in K$).
Nous avons
\[
(h_1 k_1)(h_2 k_2)= h_1 (k_1 h_2 k_1^{-1}) (k_1 k_2).
\]
Puisque $H$ est distingu\'e, nous avons $k_1 h_2 k_1^{-1}\in H$.
Donc nous avons $h_1 (k_1 h_2 k_1^{-1})\in H$, $k_1 k_2 \in K$,
et $(h_1 k_1)(h_2 k_2)$ appartient bien \`a $P$.

Finalement, supposons que $hk\in P$, $h\in H$, $k\in K$.
Alors
\[
(hk)^{-1}= k^{-1} h^{-1}= (k^{-1} h^{-1} k) k^{-1}.
\]
Puisque $H$ est distingu\'e, $k^{-1} h^{-1} k$ appartient encore
\`a $H$. Ainsi $(hk)^{-1}$ appartient \`a $P$.

On en conclut que $P$ est un sous-groupe de $G$. 


\item Il s'agit de montrer que $G$ contient un \'el\'ement d'ordre $n$.
Pour tout diviseur $d$ de $n$ soit $c(d)$ le nombre d'\'el\'ements d'ordre
$d$ dans $G$. Nous avons
\[
n=|G|= \sum_{d|n} c(d)
\]
et donc
\[
c(n)= n-\sum_{d|n, d<n} c(d)\geq n- \sum_{d|n, d<n} \phi(d)
\]
car $c(d)\leq \phi(d)$ pour tout $d|n, d<n$ d'apr\`es l'hypoth\`ese.
Or, on sait que
\[
n=\sum_{d|n} \phi(d).
\]
Donc $c(n)\geq \phi(n)\geq 1$. Ainsi $G$ contient au moins un \'el\'ement
d'ordre $n$. 



\item 
\begin{sublist}
\item On a $10^n\equiv (-1)^n \;\;(11)$ pour tout $n\in\Z$.
Donc
\[
a=123456789012345\equiv
(5-4)+(3-2)+(1-0)+(9-8)+(7-6)+(5-4)+(3-2)+1\equiv 8 \;\;(11)
\]
et $r=8$.

\item Nous avons $a\equiv -2\;\;(7)$ et $a^6\equiv 1\;\;(7)$.
Comme $2000\equiv 2\;\;(6)$, il s'ensuit que $a^{2000}
\equiv a^{2} \equiv 4 \;\;(7)$. Donc $r=4$.

\item Le nombre $p=101$ est premier. D'apr\`es le petit 
th\'eor\`eme de Fermat, nous avons donc $a^p \equiv a \;\;(p)$.
Ainsi $53^{101}\equiv 53\;\;(101)$ et $r=53$.

\item Soit $n\in\N$. D'apr\`es le th\'eor\`eme d'Euler, nous avons
\[
5^{\phi(2^n)}\equiv 1\;\;(2^n).
\]
Or $\phi(2^n)=2^{n-1}$. En posant $n=10$ nous trouvons $r=1$.

\item Soit $p$ un nombre premier. On sait que $p+1$ est d'ordre $p^{n-1}$
dans $(\Z/p^n \Z)^*$ pour tout $n\in \N$. En particulier, 
$p+1$ est d'ordre $p$ dans $\Z/p^2 \Z$. Donc 
$(p+1)^{(p+1)}\equiv p+1 \;\;(p^2)$.
En posant $p=23$ nous trouvons $r=24$. 

\item Le nombre $17$ est premier. D'apr\`es le petit th\'eor\`eme
de Fermat, il suffit de conna\^{\i}tre la classe de $5^9$ modulo
$17-1=16$ pour calculer $3^{5^9}$. Or $5$ est d'ordre $2^{n-2}$ dans
$(\Z/2^{n}\Z)^*$ pour tout $n\geq 2$. Donc $5^{4}\equiv 1\;\;(16)$
et $5^9\equiv 5\;\;(16)$. Ainsi
\[
3^{5^9}\equiv 3^5\equiv 27\times 9 \equiv 5\;\;(17)
\]
et $r=5$. 
\end{sublist}

\item 
\begin{sublist}
\item Le nombre $4$ divise $52=53-1$. L'\'equation
$x^4=1$ admet donc $4$ solutions distinctes, puissances d'une
solution primitive. Comme $2$ engendre $(\Z/53\Z)^*$ (table
des indices), une solution primitive est $2^{13}$. 
Comme $2^{10}\equiv 17 \;\;(53)$ (table des indices),
nous avons $2^{13}\equiv 17\times 8 \equiv 30 \;\; (53)$.
Donc {\bf l'ensemble des solutions est $\{1,30,-1,-30\}$ dans $\Z/53\Z$}. 


\item L'\'equation $x^{3}\equiv 11 \;\;(53)$ est \'equivalente
\`a $3 \times \ind_2 (x) = \ind_2 (11)$ dans $\Z/52$.
Or $\ind_2 (11) = 6$, d'apr\`es la table des indices.
Comme $3$ est inversible dans $\Z/52\Z$, il s'ensuit
que $\ind_2 (x)= 2$ et donc que $x= 4$ est l'unique solution
dans $\Z/53\Z$. 

\end{sublist}

\item 
\begin{sublist}
\item On a $13\equiv 1\;(12)$ et donc $13^{13}\equiv 1^{13}\equiv 1\;(12)$.
Donc $13^{13}-1\equiv 0 \;(12)$ ce qui signifie que $12$ divise
$M=13^{13}-1$. 

\item Soit $p$ un diviseur premier de $M$ qui ne divise pas $12$. 
On a donc $13^{13}\equiv 1\;(p)$ mais $13^1\not\equiv 1\;(p)$.
Donc $13$ est d'ordre $13$ dans $(\Z/p\Z)^*$. D'apr\`es le
th\'eor\`eme de Lagrange, il s'ensuit que $13$ divise $p-1$.
Donc $p-1=k\times 13$ pour un $k\in\Z$. Comme $p$ est impair,
$p-1$ est pair et $k$ doit \^etre pair. Donc on a m\^eme
$p\equiv 1\;(26)$. 

\item D'apr\`es a), $M$ est divisible par $2$ et $3$. D'apr\`es
c), les autres diviseurs premiers $p$ inf\'erieurs \`a $100$ de
$M$ se trouvent parmi les nombres $27, 53$ et $79$. Or 27
n'est pas premier. Montrons que $53$ divise $M$. En effet,
nous avons $13\equiv 2^{24}\; (53)$ d'apr\`es la table
des indices, et donc $13^{13}\equiv 2^{13\times 24}\equiv 1 \;(53)$ 
car, d'apr\`es le petit th\'eor\`eme de Fermat, $2^{52}\equiv 1\;(53)$.
Donc $53$ divise $M$.

Montrons que $79$ ne divise pas $M$. En effet, nous avons 
$13\equiv 3^{34}\;(79)$ d'apr\`es la table des indices). Donc
$13^{13}\equiv 13^{13\times 34} \;(79)$. Or $13\times 34= 2\times 13\times 17$
n'est pas divisible par $78=2\times 3\times 13$, qui est l'ordre
de $3$ dans $(\Z/79\Z)^*$. Donc $13^{13}\not\equiv 1\;(79)$
et $79$ ne divise pas $M$. 

{\bf Les seuls diviseurs premiers de $M$ inf\'erieurs \`a $100$
sont donc $2$, $3$ et $53$.}
\end{sublist}

\item 
\begin{sublist}
\item Nous avons $\alpha=2\times (-1+8i)$ et $2=(-i)\times (1+i)^2$.
Il s'agit de d\'ecomposer $\beta=-1+8i$. La norme de $\beta$
est \'egale \`a $65=5\times 13$. Donc l'un des deux diviseurs premiers de $5$,
\`a savoir $1+2i$ ou $1-2i$, doit diviser $\beta$. Nous avons
\[
\frac{-1+8i}{1+2i} = \frac{(-1+8i)(1-2i)}{5} =\frac{15+10i}{5}= 3+2i.
\]
Donc $1+2i$ divise $\beta$. Le quotient $3+2i$ est premier,
car sa norme $N(3+2i)=13$ est un nombre premier de $\Z$. Ainsi
la d\'ecomposition recherch\'ee est
\[
\alpha=(-i)\times (1+i)^2 \times (1+2i)\times (3+2i).
\]


\item Si $(x,y)\in\Z^2$ v\'erifie $x^2+y^2=p^2$, nous avons
\[
(x+iy)(x-iy)=p^2.
\]
Puisque $p\equiv 3\;(4)$, le nombre $p$ reste premier dans $\Z[i]$.
D'apr\`es le lemme de Gauss (pour $\Z[i]$), $p$ divise l'un des
deux facteurs $x+iy$ ou $x-iy$. Il divise donc les deux car
si $z=pw$ alors $\ol{z}=\ol{pw}=p\ol{w}$, o\`u la barre d\'esigne
le nombre complexe conjugu\'e. Donc $p$ divise $x+iy$. Disons
$x+iy=\alpha p$ pour un $\alpha\in\Z[i]$. Pour les normes, nous
obtenons
\[
p^2=N(x+iy)=N(\alpha) N(p)= N(\alpha)\times p^2.
\]
Ainsi $N(\alpha)=1$ et $\alpha\in \{1,i,-1,-i\}$. Donc 
$x+iy\in\{p,ip,-p,-ip\}$ ce qui signifie que
\[
(x,y)\in\{(p,0), (0,p), (-p,0), (0,-p)\}.
\]

\end{sublist}

\end{list-of-exercises}

\end{document}











