%\documentstyle{frenchar}
\documentstyle{article}




\setlength{\oddsidemargin}{0.7cm}
\setlength{\textwidth}{14cm}
\setlength{\textheight}{23cm}
\setlength{\topmargin}{0.5cm}
\setlength{\headheight}{0cm}
\setlength{\headsep}{0cm}
%\setlength{\footskip}{0cm}
%\setlength{\footheight}{0cm}
%\setlength{\parindent}{1cm}





%spacing and numbering
\newcommand{\el}{\par \mbox{} \par \vspace{-0.5\baselineskip}}
\newcommand{\ts}{\textstyle \mbox{\rule{0cm}{0.8\baselineskip}}}


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

%letterlist
\newcounter{letterlistcter}
\newenvironment{letterlist}{
\begin{list}{{ \alph{letterlistcter})}}{\usecounter{letterlistcter}
\setlength{\itemsep}{0cm}\setlength{\leftmargin}{1.5em}}
}{\end{list}}                                              


\newcommand{\Absatzn}[1]{\el\el\el \noindent 
                         {\bf  #1 }}
\newcommand{\Absatz}[1]{\stepcounter{section}
   \addcontentsline{toc}{section}{\protect\numberline{\thesection}{#1}}
                         \Absatzn{\thesection.\ \protect{#1}}}
\newcommand{\absatzn}[1]{\el \noindent{\bf #1}}
\newcommand{\absatz}[2]{\refstepcounter{subsection}
                        \absatzn{\thesubsection\  #1} \label{#2}}


\newtheorem{lemme}{Lemme}[section]
\newtheorem{proposition}{Proposition}[lemme]
\newtheorem{theoreme}[lemme]{Th\'eor\`eme}
\newtheorem{definition}[lemme]{D\'efinition}
\newtheorem{corollaire}[lemme]{Corollaire}
\newtheorem{lemme-definition}[lemme]{Lemme-D\'efinition}

\newenvironment{demonstration}{\el\noindent 
                          {\bf D\'emonstration. }}{\hfill$\surd$}


\newenvironment{labelledlist}[1]{\el \noindent
                    {\refstepcounter{lemme}\bf #1 \thelemme\   }
                    \begin{letterlist}}{\end{letterlist}}
\newenvironment{remarques}{\begin{labelledlist}{Remarques}}{
                           \end{labelledlist}}
\newenvironment{exemples}{\begin{labelledlist}{Exemples}}{
                           \end{labelledlist}}
\newenvironment{nonexemples}{\begin{labelledlist}{(Non-)exemples}}{
                           \end{labelledlist}}


\newenvironment{labelledtext}[1]{\el \noindent
                    {\refstepcounter{lemme}\bf #1 \thelemme\ }}{ }
\newenvironment{remarque}{\begin{labelledtext}{Remarque}}{
                          \end{labelledtext}}
\newenvironment{exemple}{\begin{labelledtext}{Exemple}}{
                          \end{labelledtext}}


\newenvironment{notation}{\el\noindent {\bf Notation. }}{ }
\newenvironment{Exemples}{\el\noindent {\bf Exemples.}}{ }



%theorems and such without numbers
%Put blank lines before Thms but not after
\newcommand{\theorem}[2]{\el {\bf #1}{\ \nopagebreak \em #2}}
\newcommand{\lemma}[1]{\theorem{Lemma.}{#1}}
\newcommand{\flemma}[1]{\theorem{Lemme.}{#1}}
\newcommand{\prop}[1]{\theorem{Proposition.}{#1}}
\newcommand{\thm}[1]{\theorem{Theorem.}{#1}}
\newcommand{\fthm}[1]{\theorem{Th\'eor\`eme.}{#1}}
\newcommand{\cor}[1]{\theorem{Corollary.}{#1}}
\newcommand{\fcor}[1]{\theorem{Corollaire.}{#1}}
\newcommand{\fproof}{\el {\bf D\'emonstration.}\ }
\newcommand{\example}{\el {\bf Example.}\ }
\newcommand{\fexample}{\el {\bf Exemple.}\ }
\newcommand{\examples}{\el {\bf Examples.}\ }
\newcommand{\varexample}{{\bf Example.\ }}
\newcommand{\remark}{\el {\bf Remark.}\ }
\newcommand{\remarks}{\el {\bf Remarks.}\ }
\newcommand{\fremark}{\el {\bf Remarque.}\ }
\newcommand{\fremarks}{\el {\bf Remarques.}\ }
\renewcommand{\abstract}{{\bf Abstract.}\ }
\newcommand{\fabstract}{{\bf R\'esum\'e.}\ }

%theorems and such with numbers
\newcommand{\Lemma}[2]{\theorem{#1 \ Lemma.}{#2}}
\newcommand{\Prop}[2]{\theorem{#1 \ Proposition.}{#2}}
\newcommand{\Thm}[2]{\theorem{#1 \ Theorem.}{#2}}

%theorems and such numbered as absaetze
\newcommand{\LEmma}[2]{\refstepcounter{subsection}
\theorem{\thesubsection\ Lemma.}{#2}\label{#1}}



% 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}}}
\newcommand{\C}{{\mbox{\bf C}}}
%Comma, forall
\newcommand{\ko}{\: , \;}
\newcommand{\fa}{\forall \,}
%Overline, Underline
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}
\newcommand{\class}[2]{^{#1}\overline{#2}}

%Arithmetic
\newcommand{\mod}{\mbox{\rm mod}}
\newcommand{\ord}{\mbox{\rm ord}}

%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}\,}
\newcommand{\pgcd}{\mbox{PGCD\,}}
\newcommand{\ppcm}{\mbox{PPCM\,}}
\newcommand{\leg}[2]{(\frac{#1}{#2})}

\newcommand{\mul}[1]{(\Z/#1\Z)^*}
%\renewcommand{\arraystretch}{2}
\newcommand{\add}[1]{\Z/#1}
\newcommand{\plus}{\oplus}




%Pictures
\setlength{\unitlength}{0.25cm}
\newcommand{\lblarge}[3]{\put(#1,#2){\makebox(3,2){$ #3 $}}}
\newcommand{\lb}[3]{\put(#1,#2){\makebox(2,2){$ #3 $}}}
\newcommand{\lbt}[3]{\put(#1,#2){\makebox(0,0)[t]{$ #3 $}}}
\newcommand{\lbb}[3]{\put(#1,#2){\makebox(0,0)[b]{$ #3 $}}}
\newcommand{\lbl}[3]{\put(#1,#2){\makebox(0,0)[l]{$ #3 $}}}
\newcommand{\lbtl}[3]{\put(#1,#2){\makebox(0,0)[tl]{$ #3 $}}}
\newcommand{\lbtr}[3]{\put(#1,#2){\makebox(0,0)[tr]{$ #3 $}}}
\newcommand{\lbbl}[3]{\put(#1,#2){\makebox(0,0)[bl]{$ #3 $}}}
\newcommand{\lbbr}[3]{\put(#1,#2){\makebox(0,0)[br]{$ #3 $}}}
\newcommand{\arrow}[5]{\put(#1,#2){\vector(#3,#4){#5}}}
\newcommand{\lin}[5]{\put(#1,#2){\line(#3,#4){#5}}}
\newcommand{\lbold}[3]{\put(#1,#2){\makebox(1,0.5){$ #3 $}}}


\begin{document}
%\setlength{\baselineskip}{0.7cm}
%\input{montreref}
\input{epsf}

%\input{arithint}
\vspace*{1cm}
\begin{center}
{\bf\huge MT 282 \\[0.5cm]
Groupes et Arithm\'etique \\[0.5cm]
Chapitres choisis}\\[1cm]
B.~Keller
\end{center}
\vspace*{2cm}
\tableofcontents
\newpage

%\input{arith01}

\Absatz{Construction de $\Z$ \`a partir de $\N$}
\el
En supposant connues les propri\'et\'es \'el\'ementaires de
l'ensemble $\N$ et de l'addition des entiers naturels,
nous allons donner une construction rigoureuse de $\Z$
et de l'addition des entiers relatifs. Dans cette construction,
$\Z$ appara\^{\i}tra sous forme d'un quotient de $\N\times\N$
par une relation d'\'equivalence. Ce paragraphe est aussi
l'occasion de rappeler les notions de relation d'\'equivalence
et d'ensemble quotient, notions centrales pour le reste
du cours.


\begin{definition} Soit $X$ un ensemble. Une {\em relation sur $X$}
est un ensemble $R\subset X\times X$ de couples d'\'el\'ements
de $X$. On \'ecrit $x R x'$ au lieu de $(x,x')\in R$. Une relation
$R$ est une {\em relation d'\'equivalence} si elle est
\begin{itemize}
\item[a)] r\'eflexive (i.e. pour tout $x\in X$, on a $x R x$)
\item[b)] sym\'etrique (i.e. on a \'equivalence entre 
$x R x'$ et $x' R x$ quels que soient $x,x'\in X$)
\item[c)] transitive (i.e. les conditions $x R x'$ et
$x' R x''$ impliquent que $x R x''$ quels que soient $x,x',x''\in X$)
\end{itemize}
\end{definition}

\begin{exemples} 
\item[1)] Soit $V$ l'ensemble des villes de France. On 
d\'efinit une relation $R$ sur $V$ en d\'eclarant que
$v R v'$ signifie que $v$ et $v'$ se trouvent dans la 
m\^eme r\'egion. Il est facile de v\'erifier qu'il s'agit
d'une relation d'\'equivalence. 

\item[2)] Soit $X=\N\times \N$ et d\'efinissons $R$ par
\[
(x,y) R (x',y')  \Leftrightarrow x+y'= y+x'.
\]
Par exemple, on a $(0,1) R (1,2)$ et $(1,2) R (2,3)$.
La r\'eflexivit\'e et la sym\'etrie de $R$ r\'esultent
de la commutativit\'e de l'addition des entiers positifs.
Montrons que $R$ est transitive. En effet, par d\'efinition,
les conditions $(x,y) R (x',y')$ et $(x',y') R (x'',y'')$
\'equivalent aux \'equations
\begin{eqnarray*}
x+y' & = & y + x' \\
x' + y'' & = & y' + x''
\end{eqnarray*}
En rajoutant la premi\`ere \`a la seconde on obtient
\[
x+y'+x'+y'' = y+x'+y'+x''
\]
ou encore
\[
x+y''+(x'+y') = x'' + y + (x'+y').
\]
Or on sait que la loi d'addition sur $\N$ est {\em r\'eguli\`ere}
c'est-\`a-dire qu'une \'egalit\'e $a+c=b+c$ implique
$a=b$ quels que soient $a,b,c\in\N$. Il s'ensuit que
$x+y''=x''+y$ c'est-\`a-dire que $(x,y) R (x'',y'')$. Notons
que dans cette d\'emonstration, nous avons utilis\'e 
l'associativit\'e, la commutativit\'e et la r\'egularit\'e
des entiers naturels. 
\end{exemples}


\begin{definition} Soit $X$ un ensemble et $R$ une relation
d'\'equivalence sur $X$. Pour $x\in X$, on pose
\[
\mbox{ }^R\ol{x}  =  \{ x'\in X \;| \; x R x' \; \} \subset X
\]
et on appelle {\em classe d'\'equivalence de $x$ par rapport
\`a $R$} cette partie de $X$. Par d\'efinition, l'ensemble
$X/R$ est form\'e des classes $\mbox{ }^R\ol{x}$ d'\'el\'ements
$x\in X$. On appelle $X/R$ {\em le quotient de $X$ par la relation
d'\'equivalence $R$}. On d\'efinit {\em l'application quotient}
(={\em la projection canonique})
$q : X \ra X/R$ par $q(x)=\mbox{ }^R\ol{x}$. Une partie
de $X$ est un {\em syst\`eme de repr\'esentants} pour 
$R$ si elle contient un \'el\'ement de chaque classe
d'\'equivalence et un seul.
\end{definition}

\begin{exemples}
\item[1)] Dans l'exemple des villes de France (voir ci-dessus)
la classe d'\'equivalence d'une ville $v$ est form\'ee de toutes
les villes qui se trouvent dans la m\^eme r\'egion que $v$. En
particulier deux classes $\ol{v}$ et $\ol{v'}$ sont
\'egales ssi $v$ et $v'$ se trouvent dans la m\^eme r\'egion.
Les \'el\'ements de $V/R$ sont des ensembles de villes,
deux villes \'etant regroup\'e dans un m\^eme ensemble
ssi elles se trouvent dans la m\^eme r\'egion. On a donc
une bijection
\[
X/R \iso \{\mbox{r\'egions de France}\}\ko 
\ol{v} \mapsto \mbox{la r\'egion o\`u se trouve v}.
\]
Il existe {\em beaucoup} de syst\`emes de repr\'esentants.
Par exemple, l'ensemble $V_0$ form\'e des capitales des r\'egions
en est un. L'ensemble $V_1$ form\'e des villes les plus
\'eloign\'ees de la capitale dans leur r\'egion en est un autre. 

\item[2)] Dans le cas de l'exemple $X=\N\times \N$ et de la 
relation $R$ introduite ci-dessus on v\'erifie que
$(x,y) R (x',y')$ si et seulement si l'une des deux
conditions suivantes est remplie
\begin{itemize}
\item il existe $d\in\N$ tel que $x'=x+d$ et $y'=y+d$
\item il existe $d\in\N$ tel que $x=x'+d$ et $y=y'+d$.
\end{itemize}
Ainsi, deux \'el\'ements appartiennent \`a une m\^eme
classe d'\'equivalence si on peut passer de l'un \`a
l'autre en ajoutant un m\^eme entier naturel aux
deux coordonn\'ees. Les classes sont donc des
`parties diagonales' du plan $\N\times\N$ :
\[
\epsfbox{classesNN.eps}
\]
Il y a beaucoup de syst\`emes de repr\'esentants.
Par exemple
\[
X_0 = \{0\}\times\N \cup \N\times\{0\}
= \{ \ldots, (0,3), (0,2), (0,1), (0,0), (1,0), (2,0), \ldots \}
\]
en est un. On d\'efinit l'ensemble $\Z_{ax}$ ($\Z$ axiomatique)
comme \'etant l'ensemble quotient  $(\N\times\N) / R$.
\end{exemples}

\begin{lemme}[Propri\'et\'e universelle de $X/R$]
Soit $X$ un ensemble, $R$ une relations d'\'equivalence sur $X$
et $f:X \ra Y$ une application constante sur les 
classes d'\'equivalence par rapport \`a $R$
(c'est-\'a-dire qu'on a $f(x)=f(x')$ \`a chaque fois
que $x R x'$). Alors il existe une application $g: X/R \ra Y$
et une seule telle que $f=g\circ q$. R\'eciproquement,
toute application de la forme $g\circ q$ est constante
sur les classes d'\'equivalence.
\end{lemme}

\begin{center}



\begin{picture}(14,8)(0,0)
%\multiput(0,0)(1,0){15}{\line(0,1){8}}
%\multiput(0,0)(0,1){9}{\line(1,0){14}}

\lb{0}{5}{X}
\lb{6}{0}{X/R}
\lb{12}{5}{Y}

\arrow{2}{5}{4}{-3}{4}
\arrow{8}{2}{4}{3}{4}
\arrow{3}{6}{1}{0}{8}

\lbtr{4}{3.5}{q\;}
\lbtl{10}{3.5}{\;g}
\lb{6}{6.2}{f}

\end{picture}
\end{center}

\begin{remarque} Le lemme signifie que la r\`egle
$g(\ol{x})=f(x)$ d\'efinit une application $g:X/R \ra Y$
si et seulement si on a $f(x)=f(x')$ quels que soient $x,x'\in X$
v\'erifiant $x R x'$. 
\end{remarque}

\begin{demonstration} On pose $g(\ol{x})=f(x)$. Il s'agit
de v\'erifier que $f(x)$ est ind\'ependant du
repr\'esantant $x$ de la classe $\ol{x}$. Or si $x'$ en
est un autre, c'est-\`a-dire que $\ol{x}=\ol{x'}$, 
alors par d\'efinition, on a $x R x'$ et donc $f(x)=f(x')$. 
\end{demonstration}

\begin{exemple}  Il existe une application $g: \Z_{ax} \ra \Z$
et une seule telle que $g(\ol{(x,y)})=x-y$. En effet,
si $(x,y)R(x',y')$ alors $x+y'=y+x'$ et donc $x-y=x'-y'$.
L'application $g$ est bijective : En effet, elle est surjective
car si $n\in\Z$, on a $n=g(\ol{(n,0)})$ si $n\geq 0$
et $n=g(\ol{(0,-n)})$ si $n<0$. Elle est injective car
si on a $x-y=x'-y'$, alors $x+y'=x'+y$ c'est-\`a-dire que
$(x,y) R (x',y')$ et que $\ol{(x,y)}=\ol{(x',y')}$. 
\end{exemple}

\begin{lemme}[Addition sur $\Z_{ax}$] Il existe une
application
\[
\Z_{ax} \times \Z_{ax} \ra \Z_{ax}
\]
et une seule telle que
\[
\ol{(a,b)} + \ol{(c,d)} = \ol{(a+c, b+d)}.
\]
\end{lemme}

\begin{demonstration} Il s'agit de montrer que
$\ol{(a+c, b+d)}=\ol{(a'+c', b'+d')}$ si $(a,b) R (a',b')$
et $(c,d) R (c',d')$. Nous laissons au lecteur le soin
de cette v\'erification.
\end{demonstration}

\begin{definition} Un {\em groupe} est un couple $(G, \star)$
form\'e d'un ensemble $G$ et d'une application 
\[
\star : G\times G \ra G \ko (g,h) \mapsto g\star h
\]
appel\'ee la {\em loi} du groupe telle que
\begin{itemize}
\item[a)] la loi $\star$ est associative
(i.e. on a $(x\star y)\star z= x\star(y\star z)$ quels que
soient $x,y,z\in G$)
\item[b)] la loi $\star$ admet un \'el\'ement neutre
(i.e. il existe $e\in G$ tel que $x\star e = e\star x=x$ quel
que soit $x\in G$)
\item[c)] tout \'el\'ement $x$ de $G$ admet un inverse
$x'$ pour la loi $\star$ (i.e. on a $x\star x'= e = x'\star x$)
\end{itemize}
Un groupe $(G,\star)$ est {\em commutatif} si on a $x\star y = y \star x$
quels que soient $x,y\in G$. 
\end{definition}

\begin{remarques}
\item[1)] Si les conditons a) et b) sont v\'erifi\'ees, alors
l'\'el\'ement neutre $e$ est unique. En effet, soient $e$
et $e'$ deux \'el\'ements neutres. Alors on a
$e=e\star e'$ (car $e'$ est neutre) et $e\star e'=e'$ (car
$e$ est neutre) et donc $e=e'$.

\item[2)] Si les conditions a), b) et c) sont v\'erifi\'ees,
l'\'el\'ement inverse $x'$ de la conditon c) est unique. En 
effet, supposons que $x'$ et $x''$ sont deux \'el\'ements
inverses \`a $x$. Alors on a 
\[
x'=x'\star e=x'\star(x\star x'')= (x'\star x)\star x'' = e\star x''=x''.
\]
On note $x^{-1}$ l'\'element inverse de $x$.
\end{remarques}

\begin{nonexemples}
\item[1)] Le couple $(\N, +)$ v\'erifie a) et b) (pour $e=0$)
mais non pas c) car l'\'equation $n+n'=0$ n'admet pas de
solution $n'\in\N$ si $n>0$.

\item[2)] Le couple $(\Z_{ax}, +)$ est un groupe. En effet,
on v\'erifie facilement l'associativit\'e. L'\'el\'ement
neutre est la classe de $(0,0)$. L'inverse de la classe
de $(a,b)$ est la classe de $(b,a)$ ! En effet, nous avons
\[
\ol{(a,b)}+\ol{(b,a)} = \ol{(a+b, a+b)} = \ol{(0,0)}.
\]
\end{nonexemples}

\begin{lemme}[Propri\'et\'e universelle de $\Z_{ax}$] 
Soit $\iota$ l'application
\[
\iota :\N \ra \Z_{ax}\ko n \ra \ol{(n,0)}.
\]
On a $\iota(n+n')=\iota(n)+\iota(n')$ et 
si $\phi : \N \ra G$ est une autre application de $\N$
vers un groupe $G$ telle que $\phi(n+n')=\phi(n)\star \phi(n')$,
alors il existe une application $\psi: \Z_{ax}\ra G$
et une seule telle que a) $\psi\circ \iota = \phi$
et b)  $\psi(x+x')=\psi(x)\star \psi(x')$ quels que soient
$x,x'\in \Z_{ax}$.
\end{lemme}

\begin{remarque} On peut interpr\'eter ce lemme en disant 
que $\Z_{ax}$ (et donc $\Z$) est {\em le groupe
universel contenant $\N$.}
\end{remarque}

\begin{demonstration}
Il est imm\'ediat que $\iota$ est additive. Supposons 
donn\'ee une application $\phi$ comme dans l'\'enonc\'e.
D\'efinissons $f: \N\times\N \ra G$ par 
$f((a,b))=\phi(a)\star\phi(b)^{-1}$.
Montrons que $f$ induit une application $\Z_{ax}\ra G$,
Supposons que $(a,b) R (a',b')$ et donc que $a+b'=b+a'$. 
Alors pour montrer que
\[
\phi(a)\phi(b)^{-1} = \phi(a') \phi(b')^{-1}
\]
il suffit de montrer que
\[
\phi(a)\phi(b)^{-1} \phi(b) \phi(b') = \phi(a') \phi(b')^{-1}
\phi(b) \phi(b').
\]
En utilisant que $\phi(b)\phi(b')=\phi(b+b')=\phi(b')\phi(b)$
nous sommes ramen\'es \`a montrer que
\[
\phi(a)\phi(b')=\phi(a')\phi(b)
\]
ce qui est clair car $\phi(a)\phi(b')=\phi(a+b')$ et
$\phi(a')\phi(b)=\phi(a'+b)$. 
Montrons l'unicit\'e de $\psi$. En effet, si $\psi$ et
$\psi'$ v\'erifient les hypoth\`eses, nous avons
\[
\psi(\ol{(n,0)})=\psi\circ\iota(n)= \phi(n)=\psi'\circ\iota(n)=
\psi'(\ol{(n,0)}).
\]
En outre, si $x'=\ol{(0,n)}$, alors $\psi(x')$ et $\psi'(x')$
sont tous les deux inverses de $\psi(x)=\psi'(x)$
o\`u $x=\ol{(n,0)}$. Donc $\psi(x')=\psi'(x')$.
Comme les $(0,n)$ et les $(n,0)$, $n\in\N$, forment
un syst\`eme de repr\'esentants des classes 
d'\'equivalence par rapport \`a $R$, il s'ensuit que
$\psi=\psi'$. 
\end{demonstration}




%\input{arith02}

\Absatz{La division euclidienne et ses cons\'equences}
\el
\begin{lemme}[division euclidienne] Soient $a\in\Z$ et $b\in\Z\setminus \{0\}$.
Alors il existe $q\in\Z$ et $r\in\{0,1,\ldots, |b|-1\}$ tels
que
\[
a=qb+r.
\]
En outre, $q$ et $r$ sont uniques.
\end{lemme}

\el
{\bf Exemples.} 
On a $15=2\times 7 + 1$ ce qui est une division euclidienne.
On a aussi $-15=(-2)\times 7 + (-1)$ ce qui {\em n'est pas}
une division euclidienne, car le reste d'une division euclidienne
est positif, par d\'efinition.
Par contre, $-15=(-3)\times 7+6$ est bien une division euclidienne.

\begin{demonstration} On consid\`ere l'ensemble $R$ form\'e des
entiers $a-p\,b$, o\`u $p\in\Z$. Puisque $b$ est non nul, l'ensemble
$R$ contient des nombres positifs. Donc l'intersection $R\cap \N$
est non vide. Elle admet donc un \'el\'ement minimal. Appelons
$r$ cet \'el\'ement et d\'efinissons $q$ par l'\'egalit\'e 
$a-q\,b=r$. Montrons que $r<|b|$. Soit $\eps$ le signe de $b$
($\eps=1$ si $b>0$ et $\eps=-1$ si $b<0$). Si nous avions
$r>|b|$, nous pourrions enlever $\eps \,b$ des deux c\^ot\'es
de l'\'egalit\'e $a-q\,b=r$ pour trouver un nombre
\[
r-\eps\,b=a-(q+\eps)b
\]
qui appartiendrait encore a $R\cap \N$ mais qui serait 
strictement inf\'erieur \`a $r$. Contradiction. On a donc bien
$r\in\{0,1,\ldots, |b|-1\}$.  

Montrons l'unicit\'e. Si nous avons
\[
q\,b+r= a = q'\,b+r',
\]
alors $(q-q')\,b=r-r'$. Puisque $r$ et $r'$ sont positifs
et strictement inf\'erieurs \`a $|b|$, il s'ensuit que
$|q-q'|\,|b| = |r-r'|< |b|$. Comme $|b|\neq 0$, nous 
avons $|q-q'|<1$. Or, $|q-q'|$ est un entier positif et
donc $|q-q'|=0$ et $q=q'$. Par cons\'equent, nous
avons aussi $r=a-q\,b=a-q'\,b=r'$. 
\end{demonstration}

\begin{definition}
Soit $(G,*)$ un groupe. Un {\em sous-groupe} de $(G,*)$ est
une partie $H\subset G$ telle que 
\begin{itemize}
\item[a)] L'\'el\'ement neutre $e$ de $G$ appartient \`a $H$.
\item[b)] On a $h * h'\in H$ quels que soient $h,h'\in H$.
\item[c)] On a $h^{-1}\in H$ quel que soit $h\in H$.
\end{itemize}
\end{definition}

\begin{remarques}
\item Si $H$ est une sous-groupe de $(G,*)$, on d\'efinit
une loi $*_H: H \times H \ra H$ par
\[
h *_H h' = h * h'.
\]
Il est clair que $(H, *_H)$ est un groupe.
\item Quel que soit le groupe $(G,*)$, les parties $G$
et $\{e\}$ sont toujours des sous-groupes. 
\item Pour tout $n\in\Z$, la partie
\[
n\Z=\{ nx \; | \; x\in\Z\}
\]
est un sous-groupe de $(\Z,+)$. D'apr\`es le th\'eor\`eme
ci-dessus, on obtient ainsi {\em tous} les sous-groupes de
$(\Z,+)$.
\end{remarques}

\begin{theoreme}
Tout sous-groupe $H$ de $(\Z, +)$ est de la forme $H=n\Z$
pour un $n\in\Z$ unique au signe pr\`es.
\end{theoreme}

\begin{demonstration}
Si $H=\{0\}$, alors $H= 0\Z$ et il n'y a rien \`a d\'emontrer.
Supposons donc que $H \neq \{0\}$. Alors l'ensemble des
normes $|x|>0$ d'\'el\'ements de $H$ est non-vide.
Soit $n\in H$ tel que $|n|$ est non nul et minimal.
Je dis que $H=n\Z$. En effet, puisque $H$ est un 
sous-groupe qui contient $n$, il contient $n\Z$. 
R\'eciproquement, soit $a\in H$ et soit
$a=qn+r$ la division euclidienne de $a$ par
$n$ (rappelons que $n\neq 0$). Si on avait $r\neq 0$,
alors $r=q-qn$ serait un \'el\'ement de $H$
non nul et de norme strictement inf\'erieure
\`a celle de $n$. Donc nous avons $r=0$ et
$a=qn$ appartient \`a $n\Z$. 

Montrons l'unicit\'e. En effet, si $n\Z=n'\Z$,
nous avons $n= xn'$ pour un $x\in\Z$ et
$n'=x'n$ pour un $x'\in\Z$. Donc $n=xx'n$.
Nous avons soit $n=0$, et alors $n\Z=\{0\}$ et $n'=0$,
soit $n\neq 0$ et alors $1=xx'$ et donc 
$x=\pm 1$ et $n'=\pm n$.
\end{demonstration}

\begin{remarque} Si $H$ et $H'$ sont deux sous-groupes
de $(\Z, +)$, on pose
\[
H+H'=\{ x+x'\; | \; x\in H \mbox{ et } x'\in H'\}.
\]
On v\'erifie aussit\^ot que $H+H'$ est encore un sous-groupe
de $(\Z, +)$. D'apr\`es le th\'eor\`eme, si $a$ et $b$
sont deux entiers, il existe un entier $c$ unique au
signe pr\`es tel que
\[
a\Z + b\Z = c\Z.
\]
Nous allons voir que $c$ est en fait {\em le plus grand commun
diviseur} de $a$ et $b$.
\end{remarque}


\begin{definition}
Soient $a,b\in\Z$. On dit que $a$ est {\em divisible} par
$b$ s'il existe $q\in\Z$ tel que $a=q\,b$. Dans ce cas, on
dit aussi que $a$ est {\em multiple} de $b$, que $b$ {\em divise}
$a$ ou que $b$ est {\em diviseur} de $a$. On \'ecrit
$a|b$. 
\end{definition}

\begin{remarques}
\item Le nombre $15$ est divisible par $1,3,5,15, -1,-3,-5$ et $-15$ !

\item Le nombre $0$ est divisible par tout entier. Par contre
le nombre $1$ n'est divisible que par $1$ et $-1$. En effet,
si on a $1=q b$, alors $1/|b|$ est un entier non nul  et $\leq 1$.
Donc $b=\pm 1$.

\item Supposons $b\neq 0$. Alors la division euclidienne de $a$
par $b$ est bien d\'efinie et $a$ est divisible par $b$ ssi
le reste de la division euclidienne de $a$ par $b$ s'annule.

\end{remarques}

\begin{definition}
Soient $a,b\in\Z$ tels que $(a,b)\neq (0,0)$. Alors le module
d'un diviseur commun \`a $a$ et $b$ est born\'e par
$\max(|a|,|b|)$ et il existe donc un {\em plus grand diviseur
commun} \`a $a$ et $b$. On le note $\pgcd(a,b)$. Les
nombres $a$ et $b$ sont {\em premiers entre eux} si
$\pgcd(a,b)=1$. Si $a=b=0$, on pose $\pgcd(a,b)=0$.
\end{definition}


\begin{lemme}[B\'ezout]
Soient $a,b\in\Z$. Alors
\[
a\,\Z + b\,\Z = \pgcd(a,b) \,\Z.
\]
En particulier, on a \'equivalence entre
\begin{itemize}
\item[i)] Les entiers $a$ et $b$ sont premiers entre eux.
\item[ii)] On a $a\Z + b\Z = \Z$.
\item[iii)] L'\'equation $ax + by =1$ admet une solution $(x,y)\in\Z^2$.
\end{itemize}
\end{lemme}

\begin{remarques}
\item L'\'equation $ax+by=1$ est dite {\em \'equation de B\'ezout}.
Si $(a,b)\neq (0,0)$, elle admet toujours des solutions
$(x,y)\in\Q^2$ mais pas n\'ecessairement dans $\Z^2$.
\item Il s'ensuit du lemme que tout diviseur commun $c$
de $a$ et $b$ divise $\pgcd(a,b)$ (car il divise $ax+by$
quels que soient $x,y\in\Z$).
\end{remarques}

\begin{demonstration}
Supposons que $a\Z+b\Z=c\Z$ avec $c$ positif. 
Comme $a\in c\Z$ et $b\in c\Z$, le nombre $c$ 
est un diviseur commun de $a$ et $b$. Donc
$c\leq \pgcd(a,b)$. De l'autre c\^ot\'e,
$\pgcd(a,b)$ divise $a$ et $b$ et donc
tout \'el\'ement de $a\Z + b\Z$. En particulier,
$\pgcd(a,b)$ divise $c$. Il s'ensuit que
$c=\pgcd(a,b)$. 

Il est ainsi clair que i) est \'equivalent \`a ii).
Il est aussi clair que i) implique iii). R\'eciproquement,
si iii) est v\'erifi\'e et $z\in\Z$, il suffit de multiplier 
l'\'equation $ax+by=1$ par $z$ pour conclure que
$z=a(zx)+b(zy)$ appartient \`a $a\Z+b\Z$ et donc que
$\Z=a\Z+b\Z$.
\end{demonstration}



\begin{lemme}[Gauss] Soient $a,b,c\in\Z$. Si $a$ divise $bc$
et que $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.
\end{lemme}

\begin{demonstration}
D'apr\`es le lemme de B\'ezout, il existe $x,y\in\Z$ tels que
$ax+by=1$. Nous multiplions cette \'galit\'e par $c$ pour 
obtenir
\[
acx+bcy=c.
\]
Puique $a$ divise $acx$ et $bcy$, il doit diviser $axc+bcy=c$.
\end{demonstration}

\begin{definition}
Un nombre premier est un entier $>1$ dont les seuls diviseurs
positifs sont $1$ et lui-m\^eme.
\end{definition}

\begin{remarques}
\item Le nombre $1$ {\em n'est pas premier}.

\item Les nombres $2,3,5 \ldots$ sont premiers.

\item Un nombre premier est un entier positif qui admet exactement
deux diviseurs positifs.
\end{remarques}

\begin{lemme}[Euclide] Soit $p$ un nombre premier et $a,b\in\Z$.
Si $p$ divise $ab$ alors $p$ divise $a$ ou $p$ divise $b$.
\end{lemme}

\begin{demonstration} Si $p$ ne divise pas $a$, alors
$a$ et $p$ sont premiers entre eux, car les seuls diviseurs
de $p$ sont $1$ et lui-m\^eme. D'apr\`es le lemme de Gauss,
$p$ doit alors diviser $b$. De m\^eme, si $p$ ne divise pas $b$,
il doit diviser $a$.
\end{demonstration}



\begin{remarques} \item L'affirmation de ce lemme est {\em fausse}
si on omet l'hypoth\`ese que $p$ est premier. Par exemple
le nombre $3\times 5$ divise le produit $(2\times 3)\times (5\times 7)$
mais il ne divise ni $2\times 3$ ni $5\times 7$.

\item Soient $p$ et $p_1, \ldots, p_r$ des nombres premiers.
Montrons que si $p$ divise $p_1\cdots p_r$, alors $p=p_i$
pour un $i$. En effet, si $r=1$, il n'y a rien a d\'emontrer.
Si $r>1$, et que $p$ divise le produit $p_1\times (p_2\cdots p_r)$,
alors d'apr\`es le lemme d'Euclide, $p$ divise $p_1$ ou 
$p$ divise $p_2\cdots p_r$. Dans le premier cas, nous avons
$p=p_1$ et dans le second $p=p_i$ pour un $i\geq 2$, d'apr\`es
l'hypoth\`ese de r\'ecurrence.
\end{remarques}

\begin{theoreme}[D\'ecomposition en facteurs premiers]
Soit $n\geq 1$ un entier et soit $p_1, p_2 \ldots $ la liste
des nombres premiers (exhaustive et sans r\'ep\'etitions).
Alors il existe des entiers $m_i\in\N$ uniques et 
nuls sauf pour un nombre fini d'entre eux tels que
\[
n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots .
\]
\end{theoreme}

\begin{remarque} Comme presque tous les $m_i$ sont
nuls, presque tous les facteurs dans l'\'ecriture
$p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots$ valent un. 
Il s'agit donc en effet d'un produit avec un nombre {\em fini}
de facteurs.
\end{remarque}



\begin{demonstration} Montrons l'existence de l'\'ecriture
par un raisonnement r\'ecursif : Si $n=1$, on pose
$m_i=0$ pour tous les $i$. Si $n>1$ alors soit $n$
est premier, soit $n=n' n''$ pour deux nombres strictement
inf\'erieurs \`a $n$. Dans le premier cas, il existe
un nombre premier $p_j$ dans la liste et un seul
tel que $n=p_j$. On pose $m_i=0$ pour $i\neq j$ et $m_j=1$.
Dans le second cas, l'hypoth\`ese de r\'ecurrence nous
donne les \'ecritures
\begin{eqnarray*}
n' & = & p_1^{m'_1} p_2^{m'_2} \cdots \\
n'' & = & p_1^{m''_1} p_2^{m''_2} \cdots .
\end{eqnarray*}
En multipliant nous trouvons
\[
n  =  p_1^{m'_1+m''_1} p_2^{m'_2+m''_2} \cdots .
\]
Montrons l'unicit\'e de l'\'ecriture. Supposons donc que
\[
n  =  p_1^{m_1} p_2^{m_2} \cdots 
   =  p_1^{m'_1} p_2^{m'_2} \cdots .
\]
Montrons que $m_1=m'_1$ (la d\'emonstration pour les autres
$m_i$ est la m\^eme). Nous proc\'edons par r\'ecurrence.
Si $m_1=0$, alors $p$ ne divise pas $n$ (sinon il serait
\'egal \`a l'un des $p_i$ d'apr\`es la remarque ci-dessus).
Donc $m'_1=0$. Si $m_1>0$, alors $p_1$ divise $n$. D'apr\`es
la remarque ci-dessus, $p_1$ doit appara\^{\i}tre dans
l'\'ecriture
\[
n =  p_1^{m'_1} p_2^{m'_2} \cdots .
\]
Donc $m'_1>0$. En divisant par $p_1$ nous trouvons
\[
 p_1^{m_1-1} p_2^{m_2} \cdots 
   =  p_1^{m'_1-1} p_2^{m'_2} \cdots .
\]
et par l'hypoth\`ese de r\'ecurrence, il s'ensuit que
$m_1-1=m'_1-1$. Donc $m_1=m'_1$. 
\end{demonstration}




\begin{remarques}
\item Ce th\'eor\`eme a des cons\'equences \'etonnantes. Par exemple,
d'apr\`es l'unicit\'e, l'application
\[
\N\times\N\times\N \ra \N\ko (m_1, m_2, m_3) \mapsto 2^{m_1} \times
3^{m_2} \times 5^{m_3}
\]
est injective ! Donc le cardinal de $\N\times\N\times\N$ est
inf\'erieur \`a celui de $\N$. (Bien s\^ur, on sait par ailleurs
que ces deux cardinaux sont \'egaux). 

\item Si nous avons 
\[
n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots .
\]
comme dans le th\'eor\`eme, alors les diviseurs positifs de
$n$ sont exactement les nombres
\[
n'=p_1^{m'_1} p_2^{m'_2} p_3^{m'_3} \cdots 
\]
o\`u $m'_i\leq m_i$ pour tout $i$. En effet, il est clair
que ces nombres divisent $n$. R\'eciproquement supposons que
$n=n' n''$ et que nous avons les d\'ecompositions
\begin{eqnarray*}
n' & = & p_1^{m'_1} p_2^{m'_2} \cdots \\
n'' & = & p_1^{m''_1} p_2^{m''_2} \cdots .
\end{eqnarray*}
En multipliant nous trouvons
\[
n=p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots 
 =p_1^{m'_1+m''_1} p_2^{m'_2+m''_2} \cdots .\
\]
Par l'unicit\'e, il s'ensuit que $m_i=m'_i+m''_i$ pour tout
$i$. Donc on a bien $m_i\geq m'_i$. 

\item Nous d\'eduisons de b) que le nombre de diviseurs de $n$
est \'egal \`a $(m_1+1)\,(m_2+1)\cdots $.

\item Supposons que nous avons les d\'ecompositions 
\begin{eqnarray*}
n  & = & p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots \\
n' & = & p_1^{m'_1} p_2^{m'_2} p_3^{m'_3} \cdots .
\end{eqnarray*}
Alors il s'ensuit de b), que nous avons
\begin{eqnarray*}
\pgcd(n,n') & = & p_1^{\min(m_1, m'_1)} p_2^{\min(m_2, m'_2)} \cdots \\
\ppcm(n,n') & = & p_1^{\max(m_1, m'_1)} p_2^{\max(m_2, m'_2)} \cdots
\end{eqnarray*}
o\`u $\ppcm(n,n')$ d\'esigne le plus petit commun multiple de
$n$ et $n'$. On en d\'eduit  que
\[
n\times n' = \ppcm(n,n') \times \pgcd(n,n').
\]
\end{remarques}











%\input{arith03}

\Absatz{Congruences}
\el
\begin{definition} Soient $n\geq 1$ un entier et $a,b\in\Z$.
On dit que $a$ est congru \`a $b$ modulo $n$ s'il existe 
un $k\in\Z$ tel que $a=b+k\,n$. On \'ecrit alors
\[
a\equiv b\;(n) \mbox{  ou  }
a\equiv_n b    \mbox{  ou  }
a = b\, \mod \,n.
\]
\end{definition}

\begin{remarque} On a $a\equiv b\;(n)$ si et seulement si
$a$ et $b$ ont le m\^eme reste dans la division euclidienne par
$n$. En effet, si nous avons $a=q n+ r$ et $b=q' n+r$, alors
$a=b +(q-q')\,n$ et $a\equiv b\;(n)$. R\'eciproquement, 
si $a=q\,n+r$ et $b=q'\, n+r'$ et que $a=b+k\,n$, alors
\[
a=b+k\,n=q'\, n +r'+k\,n= (q'+k)\,n +r' = q\,n + r
\]
et par l'unicit\'e de la division euclidienne, il s'ensuit
que $r=r'$ (et $q=q'+k$).
\end{remarque}

\begin{exemple} Nous avons $6\equiv -15\;(7)$ car $6=-15+3\times 7$.
Notons que $-15$ a effectivement le m\^eme reste que $6$
pour la division euclidienne par $7$ car $-15=(-3)\times 7 + 6$.
\end{exemple}

\begin{lemme}\begin{itemize}
\item[a)] La relation $\equiv_n$ est une relation d'\'equivalence.
\item[b)] Si $a\equiv a'\;(n)$ et $b\equiv b'\;(n)$, alors
$a+b\equiv a'+b'\;(n)$ et $a\,b \equiv a'\,b'\;(n)$. 
Dans ce cas, on a aussi $a^m\equiv a'^m\;(n)$ pour tout
$m\in\N$.
\item[c)] Les nombres $0,1,\ldots, n-1$ forment un syst\`eme
de repr\'esentants des classes par rapport \`a $\equiv_n$.
\end{itemize}
\end{lemme}

\begin{demonstration}
a) La relation est r\'eflexive car nous avons $a=a+0\times n$
pour tout $a\in\Z$. Elle est sym\'etrique car si nous avons
$a=b+k\,n$ alors nous avons $b=a+(-k)\,n$. Elle est transitive,
car si nous avons $a=b+k\,n$ et $b=c+l\,n$, alors nous
avons $a=(c+l\,n)+k\,n=c+(l+k)\,n$. 

b) Supposons que $a=a'+k\,n$ et que $b=b'+l\,n$. Alors
$a+b=a'+b'+(k+l)\,n$ et 
\[
a\,b=(a'+k\,n)(b'+l\,n)=a'\,b'+a'ln+knb'+klnn= a'\,b'+(a'l+kb'+kln)\,n.
\]
La derni\`ere affirmation s'ensuit par r\'ecurrence sur $m$.

c) Tout $a\in\Z$ est \'equivalent par $\equiv_n$ \`a 
un et un seul des nombres $0,1,\ldots, n-1$. En effet, cette
affirmation est une reformulation de l'existence et de
l'unicit\'e du reste dans la division euclidienne de $a$ par $n$.
\end{demonstration}

\begin{definition} On pose 
\[
\Z/n\Z \;= \; \Z/\equiv_n.
\]
On note $\mbox{ }^n\ol{a}$ ou $\ol{a}$ (ou m\^eme $a$) la classe
de $a\in\Z$. Les \'el\'ements de $\Z/n\Z$ sont donc
les $\ol{a}$, $a\in\Z$. On munit $\Z/n\Z$ des deux lois
\begin{eqnarray*}
+\;: \Z/n\Z \times \Z/n\Z \longarr{ } \Z/n\Z, & &
       (\ol{a}, \ol{b}) \mapsto \ol{a}+\ol{b}:= \ol{a+b} \\
\cdot\;: \Z/n\Z \times \Z/n\Z \longarr{ } \Z/n\Z, & &
       (\ol{a}, \ol{b}) \mapsto \ol{a}\cdot\ol{b}:= \ol{a\cdot b} 
\end{eqnarray*}
\end{definition}

\begin{remarques}
\item Gr\^ace au lemme ci-dessus les deux lois sont
bien d\'efinies.

\item Par d\'efinition de la notion de `classe d'\'equivalence',
nous avons
\[
\mbox{ }^n\ol{a} = \mbox{ }^n\ol{b} 
\mbox{  si et seulement si  } a\equiv b\;(n).
\]
Par cons\'equent, deux classes $\ol{a}$ et $\ol{b}$ 
sont \'egales ssi les restes de $a$ et $b$ par la division
euclidienne par $n$ sont \'egaux.

\item D'apr\`es le lemme ci-dessus, les classes 
\[
\ol{0}, \ol{1}, \ldots, \ol{n-1}
\]
sont distinctes deux \`a deux et toute classe est \'egale
\`a une d'entre elles. Ces classes constituent donc la
liste (exhaustive et sans r\'ep\'etitions) des \'el\'ements
de $\Z/n\Z$. En particulier, {\em $\Z/n\Z$ est de cardinal $n$.}

\end{remarques}

%\input{arith04}

\Absatz{Crit\`eres de divisibilit\'e}
\el
Soit 
\[
N=1001001001001001001001001.
\]
Le nombre $N$ est-il premier ? Non. Il est divisible par $3$
car la somme de ses chiffres est divisible par $3$. De fa\c{c}on
g\'en\'erale, on sait qu'un nombre est divisible par $3$
ssi la somme de ses chiffres l'est. De m\^eme pour $9$ au
lieu de $3$. On sait aussi qu'un nombre est divisible par
$11$ ssi la somme altern\'ee $c_0-c_1+c_2- \ldots$ de
ses chiffres l'est ($c_0$ est le chiffre des unit\'es,
$c_1$ celui des dizaines, \ldots). La divisibilit\'e par
$7$, par contre, ne semble \^etre reli\'ee ni \`a la
divisibilit\'e par $7$ de la somme ni \`a celle de la 
somme altern\'ee de ses chiffres comme le montrent 
les exemples $7, 14, 21, \ldots$.

En fait, nous allons voir qu'un nombre est divisible par
$7$ si et seulement si c'est le cas pour le nombre
\[
c_0+3c_1+2c_2-c_3-3c_4-2c_5+c_6+3c_7+2c_8-c_9-3c_{10}- \ldots
\]
Par exemple, le nombre $100100100100$ est divisible par $7$.
Plus g\'en\'eralement, tout nombre dont l'\'ecriture
d\'ecimale est $3$-p\'eriodique et comporte un nombre
de chiffres divisible par $6$ est divisible par $7$.

Ces faits trouvent leur explication \`a l'aide de deux
outils : 1) le calcul des congruences et 2) le calcul des
restes de puissances. Le lemme suivant \'elucide le r\^ole
que joue le calcul des congruences :

\begin{lemme} Soit $n\geq 2$ un entier et $a_i, i\in\N$ une
suite d'entiers telle que
\[
a_i\equiv 10^i\;(n) \mbox{ pour tout $i\in\N$.}
\]
Soit $N\in\N$ et soient $c_0, c_1, \ldots, c_s\in \{0,\ldots, 9\}$
les chiffres de son \'ecriture d\'ecimale ($c_0$=unit\'es, \ldots).
Alors nous avons
\[
N \equiv\; a_0 c_0 + a_1 c_1 + a_2 c_2 + \ldots + a_s c_s (n).
\]
En particulier, $N$ est divisible par $n$ si et seulement
si $a_0 c_0 + a_1 c_1 + \ldots + a_s c_s$ est divisible
par $n$. 
\end{lemme}

\begin{demonstration} Par d\'efinition de l'\'ecriture d\'ecimale,
on a 
\[
N = c_0 + c_1 \times 10 + c_2 \times 10^2 + 
        c_3 \times 10^3 + \cdots + c_s \times 10^s.
\]
Puisque $10^i\equiv a_i\;(n)$, les r\`egles du calcul des
congruences nous permettent de conclure que
\[
N \equiv\; c_0 a_0 + c_1 a_1 + c_2 a_2 + c_3 a_3 + \ldots + c_r a_r (n).
\]
\end{demonstration}

\begin{exemple} D\'eduisons le crit\`ere de divisibilit\'e par
$7$ que nous avons \'evoqu\'e plus haut. Pour pouvoir appliquer
le lemme, il nous faut calculer une suite d'entiers
$a_i$ tels que $a_i \equiv 10^i\; (7)$. La suite des
$a_i$ v\'erifie donc les congruences
\begin{eqnarray*}
a_0     & \equiv & 1\; (7) \\
a_{i+1} & \equiv & 3 \, a_i \; (7)
\end{eqnarray*}
(car $10 \equiv 3\;(7)$). Pour $a_0, \ldots a_6$, nous trouvons
\[
1,3,2,-1, -3, -2,1 .
\]
Donc $a_6\equiv a_0\;(7)$ et par r\'ecurrence, on trouve que
$a_i \equiv a_{i+6}\; (7)$ pour tout $i\in\N$. Pour la
suite des $a_i$, on peut donc choisir la suite
$6$-p\'eriodique suivante
\[
1,3,2,-1,-3,-2,1,3,2,-1,-3,-2,1,3,2,-1,-3,-2, \ldots
\]
D'apr\`es le lemme, il s'ensuit que $N$ est divisible par $7$
ssi c'est le cas pour le nombre
\[
c_0+3c_1+2c_2-c_3-3c_4-2c_5+c_6+3c_7+2c_8-c_9-3c_{10}- \ldots
\]
o\`u les $c_i$ sont les chiffres de l'\'ecriture d\'ecimale
de $N$ ($c_0$=unit\'es, $c_1$=dizaines, \ldots).
\end{exemple}





%\input{arith05}

\Absatz{G\'en\'eralisation \`a d'autres syst\`emes de num\'eration}
\el
Le fondement math\'ematique des syst\`emes de num\'eration
est le lemme suivant :
\begin{lemme} Soit $b\geq 2$ un entier. Pour tout entier
$N\in\N$, il existe des entiers uniques $c_i\in\{0,\ldots, b-1\}$,
$i\in\N$, nuls sauf pour un nombre fini d'entre eux, tels que
\[
N = c_0 + c_1 b + c_2 b^2 + \cdots + c_i b^i + \cdots
\]
\end{lemme}

\begin{notation}
Dans la situation du lemme, si $N\neq 0$ et que $c_s$ est le dernier
coefficient non nul, nous \'ecrivons
\[
N=[c_s, c_{s-1}, \ldots, c_1, c_0]_b.
\]
et nous appelons l'expression \`a droite {\em l'\'ecriture
de $N$ en base $b$}. Il nous arrivera d'omettre les crochets
et les virgules comme dans l'exemple suivant
\[
1995_{10}= 11111001011_2 = 133023_8.
\]
Dans les cas de $b=2$, $8$ et $16$, on parle de l'\'ecriture 
{\em binaire}, {\em octale} et {\em hexad\'ecimale}, respectivement.
Si $b$ exc\`ede 10, les `chiffres' de $10$ \`a $b$ sont repr\'esent\'es
par les premi\`eres lettres de l'alphabet. Par exemple, les chiffres
du syst\`eme hexad\'ecimal sont
$0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$. Ainsi on~a 
\[
1995_{10}= 7CB_{16}.
\]
\end{notation}

\begin{demonstration}
On prouve d'abord l'existence par r\'ecurrence sur $n$. Pour
$n=0$ on pose $c_i=0$ pour tout $i\in\N$. Supposons $n>0$.
Effectuons la division euclidienne par $b$
\[
n=qb+r.
\]
D'apr\`es l'hypoth\`ese de r\'ecurrence, le nombre $q$
s'\'ecrit
\[
q=c_0'+c_1' b+ \cdots + c_t' b^t
\]
et donc
\[
n= r+c_0' b+ c_1' b^2 + \cdots + c_t' b^{t+1}
\]
On pose donc $c_0=r$ et $c_i=c'_{i-1}$ pour $i>0$.
Montrons l'unicit\'e. Si nous avons
\[
n=c_0 + c_1 b + c_2 b^2 +\cdots = d_0 + d_1 b + d_2 b^2 +\cdots
\]
alors $c_0=d_0$ car les deux apparaissent comme le reste de la
division euclidienne de $n$ par $b$. Nous enlevons $c_0=d_0$
des deux c\^ot\'es et nous divions par $b$ pour obtenir
\[
(n-c_0)/b= c_1 + c_2 b + \cdots = d_1 + d_2 b + \cdots.
\]
L'unicit\'e s'ensuit par r\'ecurrence sur $n$.
\end{demonstration}

\begin{lemme} 
Soit $n\geq 2$ un entier et $a_i$, $i\in\N$, une suite
d'entiers tels que
\[
b^i\equiv a_i\;(n).
\]
Soit $N\in\N$ et $c_i$, $i\in\N$, les chiffres
de son \'ecriture en base $b$ ($c_0$=unit\'es, \ldots).
Alors on a 
\[
N\equiv a_0 c_0 + a_1 c_1 + a_2 c_2 \cdots \;(n).
\]
En particulier, $N$ est divisible par $n$, si c'est le
cas pour $a_0 c_0 + a_1 c_1 + a_2 c_2 \cdots $.
\end{lemme}

\begin{demonstration} La d\'emonstration est analogue
\`a celle du cas $b=10$.
\end{demonstration}

\begin{exemples}
\item Nous avons $8^i\equiv 1 \;(7)$. Donc un nombre
est divisible par $7$ ssi la somme des chiffres de
son \'ecriture octale est divisible par $7$. 

\item Nous avons $16^i \equiv (-1)^i\;(16)$. Donc un
nombre est divisible par $17$ ssi la somme altern\'ee
des chiffres de son \'ecriture hexad\'ecimale est 
divisible par $17$.
\end{exemples}


%\input{arith06}

\Absatz{L'algorithme d'Euclide-B\'ezout}
\el
Soient $a,b,c \in\Z$ tels que $(a,b)\neq (0,0)$.
L'algorithme suivant sert \`a calculer le $\pgcd(a,b)$ et la
solution g\'en\'erale $(x,y)\in\Z^2$ de l'\'equation de B\'ezout
\[
a\,x+b\,y= c.
\]
L'algorithme se pr\'esente sous forme d'un tableau. 
Dans une premi\`ere \'etape
on remplit les deux premi\`eres lignes comme indiqu\'ees 
dans le tableau ci-dessous. Le coefficient $q_1$ n'est pas d\'efini;
le coefficient $q_2$ est le quotient de la division euclidienne
de $a$ par $b$. 
Les lignes suivantes se calculent 
chacune en fonction des deux pr\'ec\'edentes comme indiqu\'ee
ci-dessous.


\begin{center}
\begin{tabular}{|c|cccc|l} \cline{1-5}
$k$ & $r_k$ & $q_k$ & $x_k$ & $y_k$ &
  \\ 
\cline{1-5}
$1$     & a          & $*$       & $1$       & $0$ & 
 \\
$2$     & b          & $q_2$     & $0$       & $1$ & 
$a=q_2\,b+ r_3$ est une div. eucl.  \\
$3$     & $r_3$      & \ldots     & \ldots     & \ldots &
 \\
$\vdots$ &         &           &           &      &
 \\
$k-1$   & $r_{k-1}$  & $q_{k-1}$ & $x_{k-1}$ & $y_{k-1}$ &
\\
$k$     & $r_k$      & $q_k$     & $x_k$     & $y_k$    &
$r_{k-1}=q_k\,r_k+r_{k+1}$ est une div. eucl. \\
$k+1$   & $r_{k+1}$  & $q_{k+1}$ & $x_{k+1}$ & $y_{k+1}$ &
$x_{k+1}=x_{k-1}-q_k x_k$, $y_{k+1}=y_{k-1}-q_k y_k$ \\
$\vdots$ &         &           &           &        &
  \\
$N$   & $r_N$      & $q_N$     & $x_N$     & $y_N$  &
  \\
$N+1$ & $r_{N+1}=0$  & $*$ & $x_{N+1}$ & $y_{N+1}$ & 
  \\
\cline{1-5}
\end{tabular}
\end{center}
La premi\`ere colonne contient donc les restes des divisions
euclidiennes successives, la deuxi\`eme colonne les quotients
et les deux derni\`eres colonnes des coefficients $x_k$, $y_k$
tels que $a\,x_k+b\,y_k=r_k$ (voir la d\'emonstration ci-dessous).

Les coefficients de la premi\`ere colonne forment une suite
strictement d\'ecroissante de nombres positifs entiers.
Par d\'efinition, $N$ est le plus petit entier avec $r_{N+1}=0$.
%Notons \`a titre de curiosit\'e que si $b=0$ l'algorithme
%s'arr\^ete \`a $N=1$ et $q_2$ n'est pas d\'efini. 

\el
{\bf Th\'eor\`eme.} 
{\em 
On a  $r_N  =  \pgcd(a,b)$. Si $\pgcd(a,b)$ divise $c$,
la solution g\'en\'erale de l'\'equation
\[
ax+by=c
\]
est donn\'ee par 
\begin{eqnarray*}
x & = & \frac{c}{\pgcd(a,b)}x_N+l x_{N+1} \\
y & = & \frac{c}{\pgcd(a,b)}y_N+l y_{N+1}
\end{eqnarray*}
o\`u $l\in\Z$. Si $\pgcd(a,b)$ ne divise pas $c$, l'\'equation
$ax+by=c$ n'admet pas de solution $(x,y)\in\Z^2$. 
}
\el
\noindent{\bf Exemple.} Nous cherchons le $\pgcd(198,75)$ et
toutes les solutions de l'\'equation $198 x + 75 y = \pgcd( 198,75)$.
Nous obtenons le tableau
\begin{center}
\begin{tabular}{|c|cccc|} \cline{1-5}
$k$ & $r_k$ & $q_k$ & $x_k$ & $y_k$  \\ \hline
$1$     & $198$    & $*$   & $1$  & $0$ \\
$2$     & $75$     & $2$   & $0$  & $1$  \\
$3$     & $48$     & $1$   & $1$  & $-2$ \\
$4$     & $27$     & $1$   & $-1$ & $3$ \\
$5$     & $21$     & $1$   & $2$  & $-5$ \\
$6$     & $6$      & $3$   & $-3$ & $8$ \\
$7$     & $3$      & $2$   & $11$ & $-29$ \\
$8$     & $0$      & $*$   & $-25$ & $66$ \\
\hline
\end{tabular}
\end{center}
Ainsi $\pgcd(198,75)=3$ et la solution g\'en\'erale
de l'\'equation $198 x + 75 y =3$ est donn\'ee par
\begin{eqnarray*}
x & = & 11 - 25 l \\
y & = & -29 + 66 l
\end{eqnarray*}
o\`u $l\in\Z$. 

Notons que $25=75/3$ et $66=198/3$. 
Notons aussi que les derni\`eres deux colonnes 
sont des suites altern\'ees et que les mo\-dules de $x_k$, $y_k$
sont strictement croissants pour $k\geq 3$. En particulier,
nous avons $0\leq x_N< -(-25)$ et $-66< y_N\leq 0$. La solution
$(x_N,y_N)$ est la seule avec ces propri\'et\'es.
Les coefficients $q_k$ apparaissent dans l'identit\'e 
\[
\frac{198}{75}= 2 + 
\frac{1}{1+
\frac{\ts 1}{\ts 1+
\frac{\ts 1}{\ts 1+
\frac{\ts 1}{\ts 3+
\frac{\ts 1}{\ts 2}}}}} \;\; .
\]
Voir les exercices
apr\`es la d\'emonstration.


\el
\noindent
{\bf D\'emonstration.} Notons d'abord que l'algorithme s'arr\^ete.
En effet, $r_{k+1}$ est le reste d'une division euclidienne par
$r_k$. Donc $r_{k+1}$ est compris entre $0$ et $r_k-1$. Les $r_k$ forment
donc une suite strictement d\'ecroissante de nombres positifs
entiers. Une telle suite doit aboutir \`a z\'ero apr\`es
un nombre fini d'\'etapes. 

Montrons  que $r_N=\pgcd(a,b)$. Montrons d'abord que nous avons 
\[
\pgcd(r_{k-1}, r_k)=\pgcd(r_k, r_{k+1}).
\]
En effet, par construction, nous avons une \'equation
\[
r_{k-1} = q_k r_k + r_{k+1}.
\]
Elle montre que l'ensemble des diviseurs communs \`a $r_{k-1}$
et $r_k$ est \'egal \`a l'ensemble des diviseurs communs \`a
$r_k$ et $r_{k+1}$. En particulier, les plus grands \'el\'ements
de ces ensembles sont \'egaux. La formule pour $r_N$ s'ensuit par
r\'ecurrence :
\begin{eqnarray*}
\pgcd(a,b)& = & \pgcd(b,r_3)= \ldots   \\
          & = & \pgcd(r_{N-1},r_N)=\pgcd(r_N, r_{N+1})=\pgcd(r_N,0)= r_N.
\end{eqnarray*}


Pour montrer la deuxi\`eme affirmation, nous introduisons les
matrices
\[
S_k=\left[ 
\begin{array}{cc} x_k & x_{k+1} \\ y_k & y_{k+1} \end{array}
\right] \ko k\geq 1.
\]
Nous avons
\[
S_1=\left[
\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}
\right] 
\mbox{   et   }
S_{k+1}= S_k \left[
\begin{array}{cc} 0 & 1 \\ 1 & -q_{k+1} \end{array}
\right].
\]
Par r\'ecurrence, il s'ensuit que 
\[
[ a\;\;b] S_k = [r_k \;\; r_{k+1}] \quad\mbox{et}\quad
\det S_k=-(-1)^k.
\]
En particulier, nous avons $[a\;\; b] S_N=[r_N\;\; 0]$ et la
matrice 
\[
S_N^{-1}=-(-1)^N \left[ 
\begin{array}{cc} y_{N+1} & -x_{N+1} \\ -y_N & x_N \end{array}
\right]
\]
est {\em \`a coefficients entiers}. Donc si nous posons
\[
\left[ \begin{array}{c} u \\ v \end{array} \right]
=
S_N^{-1} \left[ \begin{array}{c} x \\ y \end{array} \right]\ko
\]
alors $u,v$ sont des {\em entiers}. Nous avons
\[
[a \;\; b] \left[ \begin{array}{c} x \\ y \end{array} \right]=
[a \;\; b] S_N S_N^{-1} \left[ \begin{array}{c} x \\ y 
                                          \end{array} \right]=
[r_N\;\; 0] \left[ 
\begin{array}{c} u \\ v \end{array} \right]
\]
de fa\c{c}on que l'\'equation 
\[
[a \;\; b] \left[ \begin{array}{c} x \\ y \end{array} \right]=c
\quad\mbox{(resp. $ax+by=c$)}
\]
est \'equivalente \`a l'\'equation
\[
[r_N \;\; 0] \left[ \begin{array}{c} u \\ v \end{array} \right]=c
\quad\mbox{(resp. $r_N u + 0\,v=c$)}.
\]
Or il est clair que cette derni\`ere \'equation admet des solutions
si et seulement si $r_N$ divise $c$ et que dans ce cas la solution
g\'en\'erale est
\[
\left[
\begin{array}{c} u \\ v \end{array}
\right] =
\left[ 
\begin{array}{c} c/r_N \\ l \end{array}
\right] \ko
\]
o\`u $l\in\Z$. Donc l'\'equation $ax+by=c$ admet des solutions
si et seulement si $r_N$ divise $c$ et dans ce cas
la solution g\'en\'erale est
\[
\left[ 
\begin{array}{c} x \\ y \end{array}
\right]
= S_N \left[
\begin{array}{c} u \\ v \end{array}
\right]
= \left[
\begin{array}{cc} x_N & x_{N+1} \\ y_N & y_{N+1} \end{array}
\right]
\left[ 
\begin{array}{c} c/r_N \\ l \end{array}
\right]
= \left[
\begin{array}{c}
\frac{c}{r_N} x_N + l x_{N+1} \\
\frac{c}{r_N} y_N + l y_{N+1}
\end{array}
\right]. 
\]
\el
\el
\el
{\bf Exercices.} 1) Trouver toutes les solutions $(x,y)\in\Z^2$ des
\'equations suivantes~: a)~$5x+3y=2$, b) $4x+9y=1$, c) $17x+68y=3$,
d) $20x+30y=0$, e) $1789x+1994y=1$ f) $1994x+666y=2$.
\el
2) Avec les notations de l'algorithme d'Euclide-B\'ezout, montrer
que
\[
x_{N+1}= (-1)^N \frac{c}{\pgcd(a,b)} \mbox{   et   }
y_{N+1}= -(-1)^N \frac{a}{\pgcd(a,b)}.
\]
Indication : On pourra utiliser l'identit\'e
\[
\left[
\begin{array}{cc} a & b \\ -y_N & x_N \end{array}
\right] S_N= 
\left[
\begin{array}{cc} r_N & 0 \\ 0 & -(-1)^N \end{array}
\right].
\]
\el
3) Supposons $a>b>0$. Avec les notations de l'algorithme 
d'Euclide-B\'ezout, montrer que
\[
\frac{a}{b}=q_2+
\frac{\ts r_3}{\ts b}= 
q_2+
\frac{\ts 1}{\ts q_3+
\frac{\ts r_4}{\ts r_3}}
=q_2+
\frac{\ts 1}{\ts q_3+
\frac{\ts 1}{\ts q_4+
\frac{\ts r_5}{\ts r_4}}}= \ldots
\]
\el
4) Nous allons caract\'eriser la solution $(x_N,y_N)$ fournie par
l'algorithme d'Euclide-B\'ezout parmi toutes les solutions 
de l'\'equation de B\'ezout. Supposons, pour simplifier,
que $a>b>0$ et que $\pgcd(a,b)=1$. 

a) Montrer qu'il existe une solution $(x_+,y_+)\in\Z^2$ de $ax+by=1$ 
et une seule
telle que $0\leq x_+<b$. Montrer qu'on a
$-a<y_+\leq 0$. 

b) Montrer qu'il existe une solution $(x_-, y_-)\in\Z^2$ 
de $ax+by=1$ 
et une seule 
telle que $-b<x_-\leq 0$. Montrer qu'on a
$0\leq y_+<a$. 

c) Montrer qu'on a $(x_N,y_N)= (x_+,y_+)$ si $N$ est impair
et $(x_N,y_N)=(x_-,y_-)$ si $N$ est pair. Indication : on pourra
commencer par montrer que les suites $-(-1)^k x_k$ et $(-1)^k y_k$
sont strictement croissantes pour $k\geq 3$. 
\el
5) Nous allons estimer le nombre d'\'etapes de 
l'algorithme d'Euclide-B\'ezout.
Pour un couple d'entiers $(a,b)$ avec $a>b\geq 0$ notons $N(a,b)$
le nombre $N$ apparaissant comme nombre d'\'etapes de l'algorithme
d'Euclide-B\'ezout appliqu\'e \`a $(a,b)$.

a) Montrer que $N(a,b)\leq 1+\log_2 a$.

b) Soit $F_0=0$, $F_1=1$ et $F_n=F_{n-1}+F_{n-2}$ pour tout
$n>1$. Par d\'efinition, le nombre $F_n$ est le {\em $n$-i\`eme 
nombre de Fibonacci}. Montrer que $N(F_n, F_{n-1})=n$, 
que $N(a,b)\leq n$ si $a\leq F_n$ et que l'\'egalit\'e
ne se pr\'esente que pour $a=F_n$ et $b=F_{n-1}$. 


%\input{arith07}

\Absatz{Une autre approche de l'\'equation de B\'ezout}
\el
Soient $a,b,c\in\Z$ tels que $(a,b)\neq (0,0)$.
{\em L'\'equation de B\'ezout} est l'\'equation
\[
ax+by=c
\]
o\`u $x,y$ d\'esignent deux entiers relatifs. Si $c\neq 0$
on dit qu'il s'agit d'une {\em \'equation inhomog\`ene 
d'inhomog\'en\'eit\'e $c$}. Dans ce cas, l'\'equation {\em homog\`ene}
associ\'ee est l'\'equation
\[
ax+by=0.
\]
Notons $d=\pgcd(a,b)$.
\begin{theoreme}
\begin{itemize} 
\item[a)] La solution g\'en\'erale de l'\'equation homog\`ene
$ax+by=0$ est donn\'ee par
\[
\begin{array}{ccc}
x_h & = &  l \;\frac{b}{d} \\
y_h & = & -l \;\frac{a}{d}
\end{array}
\;\; l\in\Z.
\]
\item[b)] Si $d$ divise $c$ et que $(x_p,y_p)$ est une
solution (dite ``particuli\`ere'') de l'\'equation
inhomog\`ene $ax+by=c$, alors la solution g\'en\'erale
de l'\'equation inhomog\`ene est donn\'ee par
\[
\begin{array}{ccc}
x & = & x_p+ l \;\frac{b}{d} \\
y & = & y_p- l \;\frac{a}{d}
\end{array}
\]
\end{itemize}
\end{theoreme}

\begin{remarque} La construction de la solution g\'en\'erale
de l'\'equation de B\'ezout se fait donc suivant le m\^eme 
sch\'ema que la construction de la solution d'une \'equation
diff\'erentielle lin\'eaire :
\[
\mbox{sol. g\'en. de l'\'eq. inhomog\`ene} =
\mbox{sol. part. de l'\'eq. inhomog\`ene} + 
\mbox{sol. g\'en. de l'\'eq. homog\`ene}.
\]
\end{remarque}
\begin{demonstration} a) Regardons d'abord le cas o\`u $b=0$.
Alors l'\'equation se r\'eduit \`a $ax+0\;y =0$ o\`u $a\neq 0$
(car $(a,b)\neq(0,0)$). Clairement la solution g\'en\'erale
est donn\'ee par $x=0$, $y=l$, $l\in\Z$. De l'autre c\^ot\'e,
on a $d=|a|$, donc $a/d=\pm 1$ et $b/d=0$. L'affirmation
est donc vraie dans ce cas.

Supposons maintenant $b\neq 0$. L'\'equation $ax+by=0$
\'equivaut \`a 
\[
\frac{a}{d} \; x = - \frac{b}{d}\, y.
\]
Notons que les deux fractions qui apparaissent ici sont
en fait des entiers, car $d=\pgcd(a,b)$ divise $a$ et $b$.
Cette derni\`ere \'equation montre que $b/d$ divise le produit
$x\; a/d$. Or, nous avons $\pgcd(a/d, b/d)=1$. Par le lemme
de Gauss, il s'ensuit que $b/d$ divise $x$. Donc il existe
un $l\in\Z$ tel que $x=l\; b/d$. Nous avons donc
\[
\frac{a}{d} \; l \; \frac{b}{d} = -\frac{b}{d} \, y.
\]
Puisque $b\neq 0$, nous pouvons conclure que $y=-l\; a/d$.

b) Supposons que $(x,y)\in\Z^2$ est une solution de l'\'equation
inhomog\`ene. Si nous formons la diff\'erence des deux
\'equations
\begin{eqnarray*}
ax+by         & = & c \\
a x_p + b y_p & = & c 
\end{eqnarray*}
nous trouvons
\[
a (x-x_p) + b(y-y_p) = 0
\]
c'est-\`a-dire que $(x-x_p, y-y_p)$ est une solution de l'\'equation
homog\`ene. D'apr\`es a), il existe donc un $l\in\Z$ tel que
\begin{eqnarray*}
x-x_p & = & l\; \frac{b}{d} \\
y-y_p & = & -l\; \frac{a}{d}
\end{eqnarray*}
L'affirmation en r\'esulte.
\end{demonstration}

%\input{arith08}

\Absatz{Interpr\'etation g\'eom\'etrique}
\el
Nous consid\'erons le plan $\R^2$ et nous appelons
{\em points entiers} les points $(x,y)\in\R^2$ \`a 
coordonn\'ees enti\`eres $x,y\in\Z$. Soient $a,b,c\in\Z$
tels que $(a,b)\neq(0,0)$. Notons $D=D(a,b,c)$
la droite dans $\R^2$ form\'ee des points $(\xi,\eta)\in\R^2$
tels que $a\xi+b\eta=c$. Alors {\em l'ensemble des solutions
$(x,y)\in\Z^2$ de l'\'equation de B\'ezout $ax+by=c$
s'identifie \`a l'ensemble des points entiers de la
droite $D$.} 
\[
\epsfbox{droites.eps}
\]
D'apr\`es les th\'eor\`emes cit\'es ci-dessus, deux cas seulement
sont possibles
\begin{itemize}
\item soit la droite $D$ ne contient aucun point entier
\item soit la droite $D$ contient une infinit\'e de points entiers.
\end{itemize}
Dans le deuxi\`eme cas, l'ensemble des points entiers est 
obtenu en rajoutant un multiple entier d'un vecteur $v=(x_h,y_h)$
\`a un point entier $p=(x_p,y_p)$ fix\'e de la droite. 
Le vecteur $(x_h, y_h)$ peut \^etre identifi\'e avec 
un point entier de distance minimale \`a l'origine sur
la droite $D(a,b,0)$. Notons que cette droite contient 
exactement deux tels points (\`a savoir $v$
et $-v$). 

%\input{arith09}

\Absatz{Le lemme chinois en termes de congruences}

\begin{lemme}[lemme chinois] Soient $n_1, n_2\geq 2$ deux entiers
premiers entre eux et $u_1 n_1 + u_2 n_2= 1$ une \'equation
de B\'ezout. Soient $a_1, a_2\in\Z$ et  $a\in\Z$ tel que
$a\equiv a_1 u_2 n_2 + a_1 u_1 n_1 (n_1 n_2)$. Alors
pour $x\in\Z$ on a l'\'equivalence
\[
\left.
\begin{array}{ccc}
x & \equiv & a_1\; (n_1) \\ 
x & \equiv & a_2\; (n_2) 
\end{array}
\right\} 
\;
\Longleftrightarrow
\;
x \equiv a\;(n_1 n_2).
\]
\end{lemme}

\begin{remarque} On peut r\'einterpr\'eter le lemme en disant
que la solution g\'en\'erale $x\in\Z$ du syst\`eme de congruences
\`a gauche est donn\'ee par
\[
x=a+k n_1 n_2\ko k\in\Z.
\]
\end{remarque}

\begin{demonstration}
V\'erifions d'abord que $a$ est bien une solution du 
syst\`eme de congruences. En effet, d'apr\`es l'hypoth\`ese,
nous avons
\[
a= a_1 u_2 n_2 + a_2 u_1 n_1 + k n_1 n_2
\]
pour un $k\in\Z$ et donc
\[
a \equiv a_1 u_2 n_2 \equiv a_1 (u_2 n_2 + u_1 n_1) \equiv a_1 \;(n_1)
\]
et de m\^eme
\[
a\equiv a_2 u_1 n_1 \equiv a_2 (u_1 n_1 + u_2 n_2) \equiv a_2 \; (n_2).
\]
Montrons maintenant l'\'equivalence. Supposons que $x\equiv
a \; (n_1 n_2)$. Alors $x=a+k n_1 n_2$ pour un $k\in\Z$
et donc $x\equiv a \equiv a_1\;(n_1)$ et 
$x \equiv a \equiv a_2\;(n_2)$. R\'eciproquement, supposons
que $x$ v\'erifie $x\equiv a_1\;(n_1)$ et $x\equiv a_2 \;(n_2)$.
Alors nous avons $(x-a) \equiv 0\;(n_1)$ et $(x-a)\equiv 0\;(n_2)$.
Donc $x-a$ est divisible par $n_1$ et par $n_2$. Puisque
les deux sont premiers entre eux, il s'ensuit (lemme de Gauss)
que $x-a$ est divisible par $n_1 n_2$, c'est-\`a-dire
que $x\equiv a \;(n_1 n_2)$. 
\end{demonstration}

\begin{exemple}
Consid\'erons le syst\`eme
\begin{eqnarray*}
x & \equiv & 1\;(17) \\
x & \equiv & 2\;(28) \\
x & \equiv & 3\;(31) 
\end{eqnarray*}
Nous avons l'\'equation de B\'ezout $5\times 17 - 3 \times 28=1$.
Le syst\`eme form\'e des deux premi\`eres \'equations
est donc \'equivalent \`a la congruence $x\equiv a\;(17\times 28)$
o\`u 
$a=1 \times (-3\times 28) + 2\times (5\times 17)= 86$.
Le syst\`eme des trois \'equations se r\'eduit donc \`a
\begin{eqnarray*}
x & \equiv & 86 \; (476) \\
x & \equiv & 3 \; (31).
\end{eqnarray*}
Nous avons l'\'equation de B\'ezout 
$(-14)\times 476  +  215\times 31=1$.
Donc le syst\`eme est \'equivalent \`a la congruence 
$x\equiv b\;(476\times 31)$ o\`u 
$b= 86\times (215\times 31) +3 \times (-14\times 476)= 553198$.
Si nous r\'eduisons $b$ modulo $476\times 31= 14756$, nous
trouvons que le syst\`eme des trois \'equations est
\'equivalent \`a la congruence
\[
x \equiv 7226 \; (14756);
\]
Nous invitons le lecteur \`a v\'erifier que $7226$ donne
les restes $1$, $2$ et $3$ dans la division par $17$, $28$ et $31$.
\end{exemple}



%\input{arith10}

\Absatz{Syst\`emes de congruences}
\el
Soient $r$ et $n_1, \ldots, n_r$  des entiers
$\geq 2$ et $a_1, \ldots, a_r$ des entiers quelconques.
Consid\'erons le syst\`eme 
\begin{eqnarray*}
x & \equiv & a_1 \; (n_1) \\
x & \equiv & a_2 \; (n_2) \\
  & \vdots &               \\
x & \equiv & a_r \; (n_r).
\end{eqnarray*}
Supposons que $x=a$ et $x=a'$ sont deux solutions.
Alors la diff\'erence $a-a'$ est divisible par tous les
$n_i$ et donc par leur plus petit commun multiple
$n=\ppcm(n_1, \ldots, n_r)$. Donc {\em s'il existe une
solution}, sa classe modulo $n$ est unique.

Il peut ne pas exister de solution comme le montre l'exemple
du syst\`eme
\begin{eqnarray*}
x & \equiv & 1 \; (6) \\
x & \equiv & 2 \; (8) \\
\end{eqnarray*}
ou encore celui du syst\`eme
\begin{eqnarray*}
x & \equiv & 1 \;(2) \\
x & \equiv & 0 \;(2) .
\end{eqnarray*}
Notons que nous n'avons pas exclu ce genre de 
contradictions banales. 

L'application syst\'ematique du lemme chinois nous permettra
de r\'eduire tout syst\`eme de congruences soit \`a un
syst\`eme contradictoire soit \`a une seule congruence
modulo le plus petit commun multiple des modules. 
Nous ne d\'eveloppons pas ici la m\'ethode dans le
cas g\'en\'eral mais nous limitons \`a la d\'ecrire 
dans un exemple simple. 

Consid\'erons le syst\`eme
\begin{eqnarray*}
x & \equiv & 3 \; (18) \\
x & \equiv & c \; (12).
\end{eqnarray*}
Il s'agit de d\'eterminer tous les entiers $c$ pour lesquels
le syt\`eme admet des solutions et de calculer les solutions
dans ce cas. Constatons tout d'abord que les nombres
$18$ et $12$ ne sont pas premiers entre eux de fa\c{c}on
que le lemme chinois ne s'applique pas imm\'ediatement.
Pour r\'esoudre le probl\`eme, 
nous allons dans une premi\`ere \'etape 
{\em augmenter} le nombre d'\'equations pour
obtenir des modules qui sont des puissances de nombres
premiers. Nous avons ainsi $18=2\times 3^2$ et d'apr\`es
le lemme chinois la premi\`ere congruence est \'equivalente
au syst\`eme
\begin{eqnarray*}
x & \equiv  & 1 \; (2) \\
x & \equiv  & 3 \; (9) .
\end{eqnarray*}
De m\^eme, puisque nous avons $12=3\times 4$, la seconde
congruence est \'equivalente au syst\`eme
\begin{eqnarray*}
x & \equiv & c \; (3) \\
x & \equiv & c \; (4).
\end{eqnarray*}
Nous avons ainsi trouv\'e un syst\`eme de quatre congruences
qui est \'equivalent au syst\`eme de d\'epart. Nous le
r\'e\'ecrivons dans un ordre o\`u les puissances de chaque
nombre premier sont regroup\'ees ensemble et les puissances
les plus \'elev\'ees apparaissent en premier lieu :
\begin{eqnarray}
x & \equiv & c \; (4)  \label{one}\\
x & \equiv & 1 \; (2)  \label{two}\\
x & \equiv & 3 \; (9)  \label{three}\\
x & \equiv & c \; (3)  \label{four}
\end{eqnarray}
Rappelons-nous que si nous avons $a\equiv b\;(n)$ alors
nous avons aussi $a\equiv b \;(d)$ pour tout diviseur $d$
de $n$ (en effet, si $n=q\,d$ et $a=b+k\,n$ alors
$a=b+(k\,q)\,d$). L'\'equation (\ref{one}) implique donc
que $x \equiv c \;(2)$ de fa\c{c}on que les \'equations
(\ref{one}) et (\ref{two}) sont contradictoires sauf
si $c\equiv 1\;(2)$. De m\^eme, les \'equations
(\ref{three}) et (\ref{four}) sont contradictoires sauf
si $c\equiv 0\;(3)$. Nous avons donc les conditions
\begin{eqnarray*}
c & \equiv & 1 \; (2) \\
c & \equiv & 0 \; (3) 
\end{eqnarray*}
qui sont n\'ecessaires pour qu'une solution existe.
R\'eciproquement, ces conditions sont aussi suffisantes
car si elles sont v\'erifi\'ees, la congruence
(\ref{two}) est une cons\'equence de (\ref{one}), et
(\ref{four}) est une cons\'equence de (\ref{three})
de fa\c{c}on que le syst\`eme tout entier est \'equivalent
\`a un syst\`eme de deux congruences
\begin{eqnarray*}
x & \equiv & c \; (4) \\
x & \equiv & 3 \; (9)
\end{eqnarray*}
Nous avons l'\'equation de B\'ezout $-2\times 4 + 9 =1$.
Donc, d'apr\`es le lemme chinois, ce syst\`eme est
\'equivalent \`a la congruence $x \equiv c\times 9 + 3 \times (-8)
\;(36)$ ou encore $x \equiv 3c+12 \;(36)$. En conclusion,
{\em le syst\`eme de d\'epart admet une solution si et
seulement si $c\equiv 3\;(6)$ et dans ce cas l'ensemble
des solutions est l'ensemble des entiers $x$ tels que
$x\equiv 3c+12\;(36)$. }

%\input{arith11}

\Absatz{Classes de congruence inversibles}
\el
\begin{definition} Soit $n\geq 2$ un entier. Une classe de
congruence $\ol{a}\in\Z/n\Z$ est {\em inversible} s'il existe
une classe $\ol{b}$ telle que $\ol{a} \ol{b} =\ol{1}$.
On note $(\Z/n\Z)^*$ l'ensemble des classes inversibles.
\end{definition}


\begin{lemme} Muni de la multiplication naturelle, l'ensemble
des classes inversibles est un groupe d'\'el\'ement 
neutre $\ol{1}$.
\end{lemme}

\begin{remarque} Le lemme implique que si la classe
$\ol{a}$ est inversible, alors la classe $\ol{b}$ telle que
$\ol{a}\ol{b}=\ol{1}$ est unique. On l'appelle la {\em classe
inverse de $\ol{a}$}. 
\end{remarque}


\begin{demonstration} Il s'agit d'abord de v\'erifier que la
loi de multiplication est bien d\'efinie, c'est-\`a-dire
que le produit de deux classes inversibles est encore inversible.
En effet, si $\ol{a}\ol{b}=\ol{1}$ et $\ol{a'} \ol{b'} = \ol{1}$,
alors $(\ol{a} \ol{a'}) ( \ol{b'}\ol{b})=\ol{1}$. La loi
est associative car la multiplication de $\Z/n\Z$ est
associative. Elle admet l'\'el\'ement $\ol{1}$ pour \'el\'ement
neutre. Finalement, par d\'efinition, tout \'el\'ement
de $(\Z/n\Z)^*$ admet un inverse.
\end{demonstration}

\begin{lemme} Une classe $\ol{a}$ est inversible ssi
$a$ et $n$ sont premiers entre eux.
\end{lemme}

\begin{demonstration} En effet, la classe $a$ est inversible,
ssi l'\'equation $ab=1+kn$ admet des solutions $b,k\in\Z$.
Or cette \'equation est une variante de l'\'equation
de B\'ezout $a b + (-n) k =1$ aux inconnues $b$, $k$. 
L'affirmation en r\'esulte.
\end{demonstration}

\begin{lemme} Supposons que la classe $\ol{x}$ est inversible.
Alors la  congruence $a\equiv b\; (n)$ est \'equivalente
\`a $ax\equiv bx \;(n)$.
\end{lemme}

\begin{remarque} L'affirmation du lemme est fausse si
la classe $\ol{x}$ n'est pas inversible.
\end{remarque}

\begin{demonstration} Supposons que $\ol{x}\ol{y}=\ol{1}$.
Alors $x y \equiv 1\; (n)$ et donc la congruence
$ax y \equiv bx y\;(n)$ implique $a\equiv b\;(n)$.
\end{demonstration}


%\input{arith12}
\Absatz{Anneaux, groupes et lemme chinois}

\begin{definition} Un {\em anneau} est un triplet
$(A,+,\;\cdot)$ form\'e d'un ensemble $A$ et deux
deux applications
\[
+\;: A\times A \ra A \ko (a,b) \mapsto a+b \\
\quad\mbox{ et } \quad
\cdot\; : A \times A \ra A \ko (a,b) \mapsto ab
\]
appel\'ees {\em l'addition} et la {\em multiplication} de $A$ et
qui v\'erifient les axiomes suivants
\begin{itemize}
\item[(1)] Le couple $(A,+)$ est un groupe commutatif.
On note $0_A$ ou $0$ son \'el\'ement neutre.
\item[(2)] La multiplication $\cdot$ est associative et
admet un \'el\'ement neutre not\'e $1_A$ ou $1$.
\item[(3)] L'addition et la multiplication v\'erifient
les r\`egles de distributivit\'e
\begin{eqnarray*}
a(b+c) & = & ab + ac \\
(a+b) c & = & ac + bc
\end{eqnarray*}
quels que soient $a,b,c$ \'el\'ements de $A$. 
\end{itemize}
Un anneau est {\em commutatif} si sa multiplication est
commutative.
\end{definition}

\begin{Exemples} Les ensembles $\Z$, $\Q$, $\R$ et $\C$
munis de leurs op\'erations d'addition et de multiplication 
habituelles sont des anneaux commutatifs. L'anneau $M_2(\R)$
des matrices
\[
\left[\begin{array}{cc} a & b \\ c & d \end{array} \right]
\]
avec l'addition et la multiplication des matrices est un
anneau non-commutatif. En effet, si on pose
\[
A= \left[\begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right] \;
\ko
B= \left[\begin{array}{cc} 0 & 0 \\ 1 & 0 \end{array} \right]
\]
on a $AB\neq BA$.
\end{Exemples}

\begin{definition} Soit $A=(A, + , \; \cdot)$ un anneau.
Un \'el\'ement $a\in A$ est {\em inversible} s'il existe 
un \'el\'ement $b\in A$ tel que $ab=1_A=ba$. On note
$A^*$ l'ensemble des \'el\'ements inversibles de $A$.
L'anneau $A$ est un {\em corps} si $A^*=A\setminus \{0\}$,
c'est-\`a-dire  que tout \'el\'ement
non nul de $A$ est inversible (et que $A\neq \{0_A\}$).
\end{definition}

\begin{Exemples} Pour le cas de l'anneau $A=\Z/n\Z$, cette
d\'efinition est celle de la section pr\'ec\'edente.
Les anneaux $\Q$, $\R$ et $\C$ sont des corps. 

{\em L'anneau $\Z/n\Z$ est un corps si et seulement 
si $n$ est premier}.
Soit $p$ un nombre premier. Alors $(\Z/p\Z)^*$ est form\'e
des $p-1$ classes $\ol{1}, \ol{2}, \ldots, \ol{p-1}$.
Soit $n$ un entier $\geq 1$. Alors 
$(\Z/p^n\Z)$ est le {\em compl\'ementaire} dans $\Z/p^n \Z$
des $p^{n-1}$ classes $\ol{p}, \ol{2p}, \ldots, \ol{(p^{n-1}-1)p}$.
Donc
\[
|(\Z/p\Z)^*| = p-1 \mbox{  et  }
|(\Z/p^n\Z)^*| = p^n - p^{n-1}= p^{n-1}(p-1).
\]
\end{Exemples}

\begin{remarque}
Si l'\'el\'ement $0_A$ est inversible dans l'anneau $A$,
alors nous avons $0_A = 1_A$ et $A=\{0_A\}=\{1_A\}$. 
En effet, supposons que $0\; b= 1$. Nous 
affirmons que $0 b = 0$; en
effet, il suffit de rajouter $-0\;b$ des deux c\^ot\'es
de l\'equation $0 \; b= (0+0)\;b= 0\; b + 0\; b$.
\end{remarque}


\begin{lemme} Soit $A=(A,+,\;\cdot)$ un anneau.
Alors si deux \'el\'ements sont inversibles,
leur produit l'est encore. L'ensemble $A^*$ muni
de la multiplication d\'eduite de celle de $A$ est un groupe
d'\'el\'ement neutre $1_A$.
\end{lemme}

\begin{remarque} Il s'ensuit que l'inverse d'un \'el\'ement
inversible d'un anneau est unique (car l'inverse d'un \'el\'ement
d'un groupe est unique).
\end{remarque}

\begin{demonstration} Supposons que $a$ et $b$ sont inversibles
et que $aa'=1=a'a$ et $bb'=1=b'b$. Alors nous avons
$(ab)(b' a')=1=(b' a')(a b)$ de fa\c{c}on que $ab$ est inversible.
L'associativit\'e de la multiplication est cons\'equence 
de la m\^eme propri\'et\'e pour la multiplication dans
un anneau et de m\^eme l'existence d'un \'el\'ement
neutre. L'existence des inverses r\'esulte de la d\'efinition
de $A^*$.
\end{demonstration}

\begin{lemme-definition} Soient $(A_1, +, \cdot)$ et $(A_2, +, \cdot)$
deux anneaux. L'ensemble $A_1 \times A_2$ muni des lois d\'efinies par
\begin{eqnarray*}
(a_1, a_2) + (a_1', a_2')=(a_1+a_1', a_2'+a_2') \\
(a_1, a_2)\cdot (a_1', a_2')=(a_1 a_1', a_2 a_2')
\end{eqnarray*}
est un anneau appel\'e {\em l'anneau produit} de $A_1$ par $A_2$.
L'\'el\'ement neutre pour l'addition de $A_1\times A_2$ est
le couple $(0, 0)$ et celui pour la multiplication le couple
$(1,1)$.
\end{lemme-definition}

\begin{remarque} En appliquant plusieurs fois ce r\'esultat
nous obtenons un grand nombre de nouveaux exemples d'anneaux.
Par exemple, tous les anneaux suivants sont de cardinal 24
\[
\Z/24\Z   \ko 
\Z/3\Z \times \Z/8 \Z \ko 
\Z/8\Z \times \Z/3\Z  \ko
\Z/2\Z \times \Z/4\Z \times \Z/3\Z.
\]
Nous allons voir que certains de ces anneaux 
sont ``isomorphes'', c'est-\`a-dire qu'ils ne se distinguent
pas de fa\c{c}on essentielle.
\end{remarque}


\begin{demonstration}
Il s'agit de v\'erifier les trois groupes d'axiomes pour les
lois d\'efinies sur $A_1\times A_2$. A titre d'exemple, v\'erifions
que la multiplication est associative. En effet,
en utilisant la d\'efinition de la multiplication sur $A_1\times A_2$
et l'accociativit\'e de la multiplication dans
$A_1$ et $A_2$, nous avons
\begin{eqnarray*}
((a_1, a_2) \cdot (a_1', a_2')) \cdot (a_1'', a_2'') & = &
(a_1 a_1', a_2 a_2') \cdot (a_1'', a_2'') = 
                            ((a_1 a_1') a_1'', (a_2 a_2') a_2'') \\
 & = & (a_1 (a_1' a_1''), a_2 (a_2' a_2'')) =
                          (a_1, a_2)\cdot (a_1' a_1'', a_2' a_2'') \\
 & = & (a_1, a_2) \cdot ((a_1', a_2') \cdot (a_1'', a_2'')).
\end{eqnarray*}
Nous laissons au lecteur le soin d'\'ecrire les d\'emonstrations
des autres propri\'et\'es.
\end{demonstration}


\begin{lemme-definition} Soient $(G_1, \star)$ et
$(G_2, \star)$ deux groupes. L'ensemble $G_1\times G_2$
muni de la loi 
\[
(g_1, g_2)\star (g_1', g_2')= (g_1 \star g_1', g_2 g_2')
\]
est un groupe d'\'el\'ement neutre le couple
$(e, e)$.
\end{lemme-definition}

\begin{demonstration} La d\'emonstration est analogue \`a
celle du lemme-d\'efinition pr\'ec\'edent. 
\end{demonstration}

\begin{lemme}
Soient $(A_1, +, \cdot)$ et $(A_2, +, \cdot)$ deux anneaux.
Alors nous avons l'\'egalit\'e
\[
(A_1 \times A_2)^\star = A_1^\star \times A_2^\star.
\]
En outre la loi de groupe sur $(A_1\times A_2)^\star$
est celle du groupe produit $A_1^\star \times A_2^\star$.
\end{lemme}

\begin{demonstration}
Soit $(a_1, a_2)$ un couple d'\'el\'ements inversibles.
Soient $a_1'$ et $a_2'$ les inverses de $a_1$ et $a_2$.
Alors nous avons
\[
(a_1', a_2')\cdot (a_1, a_2)= (1,1) = (a_1, a_2) \cdot (a_1', a_2')
\]
ce qui signifie que $(a_1, a_2)$ est inversible dans
$A_1\times A_2$ d'inverse $(a_1', a_2')$. Ainsi 
l'ensemble $A_1^\star\times A_2^\star$ est inclus dans
$(A_1\times A_2)^\star$. R\'eciproquement, soit
$(a_1, a_2)$ un \'el\'ement inversible de $A_1\times A_2$
et soit $(a_1', a_2')$ son inverse. Alors on v\'erifie
aussit\^ot que $a_1'$ est inverse \`a $a_1$ dans $A_1$
et que $a_2'$ est inverse \`a $a_2$ dans $A_2$.
La derni\`ere affirmation est une cons\'equence imm\'ediate
des d\'efinitions.
\end{demonstration}


\begin{definition} Soient $(A, +,\cdot)$ et $(B, +, \cdot)$
deux anneaux. Une application $f: A \ra B$ est un 
{\em homomorphisme d'anneaux} si elle v\'erifie
\begin{eqnarray*}
f(a+a') & = & f(a) + f(a') \\
f(a \cdot a') & = & f(a) \cdot f(a') \\
f(1_A) & = & 1_B
\end{eqnarray*}
quels que soient $a,a'\in A$.
C'est un {\em isomorphisme d'anneaux} si en plus, elle
est bijective. Les anneaux $A$ et $B$ sont {\em isomorphes}
s'il existe un isomorphisme de $A$ vers $B$.
\end{definition}

\begin{exemple} Soient $A_1$ et $A_2$ deux anneaux.
Consid\'erons l'application
\[
f : A_1 \times A_2 \ra A_2 \times A_1\ko
(a_1, a_2) \mapsto (a_2, a_2).
\]
Alors on v\'erifie que $f$ est un isomorphisme. 
\end{exemple}

\begin{lemme}
Soient $A$ et $B$ deux anneaux et $f:A \ra B$ un isomorphisme.
Soit $g: B \ra A$ l'application r\'eciproque de $f$.
Alors $g$ est un homomorphisme et m\^eme un isomorphisme.
\end{lemme}

\begin{demonstration}
En effet, soient $b, b'$ des \'el\'ements de $B$. Pour
v\'erifier qu'on a \'egalit\'e entre $g(b\,b')$ et
$g(b) \,g(b')$ il suffit de voir que les images par
$f$ de ces deux \'el\'ements co\"{\i}ncident. Or
nous avons
\[
f(g(b\,b'))=b\;b'= f(g(b))\, f(g(b'))= f(g(b)\,g(b')).
\]
De m\^eme on v\'erifie que $g(b+b')=g(b)+g(b')$. Finalement,
l'\'egalit\'e $f(1_A)=1_B$ entra\^{\i}ne que
$1_A= g(1_B)$.
\end{demonstration}

\begin{definition}
Soit $G$ et $H$ deux groupes. Une application $f: G \ra H$
est un {\em homomorhisme de groupes} si elle v\'erifie
\[
f(g_1 \star g_2) = f(g_1) \star f(g_2)
\]
quels que soient $g_1, g_2\in G$. C'est un {\em isomorphisme}
si en plus elle est bijective. Les groupes $G$ et $H$ 
sont {\em isomorphes} s'il existe un isomorphisme de
$G$ vers $H$.
\end{definition}

\begin{remarques}
\item On peut s'\'etonner de ne pas trouver l'axiome
$f(e_G)=f(e_H)$ dans cette d\'efinition. Or cet axiome
est une {\em cons\'equence} de la d\'efinition. En
effet, nous avons
\[
f(e_G) = f(e_G \star e_G)= f(e_G) \star f(e_G).
\]
Si nous multiplions cette \'egalit\'e des deux c\^ot\'es
\`a gauche par l'inverse de $f(e_G)$ dans $H$, nous 
trouvons $e_H= f(e_G)$. Notons que cette d\'emonstration
utilise l'existence des inverses et qu'elle n'a donc
pas d'analogue pour les lois de multiplication des anneaux.

\item Si $f:G \ra H$ est un isomorphisme de groupes et que
$g: H \ra G$ est l'application r\'eciproque \`a $f$, alors
$g$ est un homomorphisme de groupes et m\^eme un isomorphisme.
Nous laissons au lecteur le soin d'adapter au cadre des groupes 
la d\'emonstration donn\'ee ci-dessus pour les anneaux.

\end{remarques}

\begin{lemme} \label{anneaux-groupes}
Soient $A$ et $B$ deux anneaux et
$f: A \ra B$ un homomorphime d'anneaux. Alors nous 
avons $f(A^\star)\subset B^\star$ et l'application
\[
f^\star: A^\star \ra B^\star, a \mapsto f(a)
\]
est un homomorphisme de groupes. C'est un isomorphisme
de groupes si $f$ est un isomorphisme d'anneaux.
\end{lemme}

\begin{demonstration}
Supposons que $a\in A$ 
est inversible d'inverse $a'$. Alors $f(a')$ est inverse
\`a $f(a)$. En effet, nous avons
\[
f(a) f(a')= f(a a')=f(1_A)= 1_B = f(a') f(a).
\]
Ainsi, l'application $f$ nous fournit bien une application 
entre les groupes des \'el\'ements inversibles
\[
f^\star :A^\star \ra B^\star \ko a \mapsto f(a).
\]
Il est imm\'ediat de constater que cette application est
un homomorphisme de groupes. Supposons maintenant que 
$f$ est un isomorphisme d'anneaux et soit $g:B \ra A$
son application  r\'eciproque. Alors $g$ est un homomorphisme
et donc $g(B^\star)$ est contenu dans $A^\star$. Ceci
montre que $a\in A$ est inversible si et seulement
si $f(a)$ est inversible dans $B$. Donc dans ce cas
$f^*$ est bijective et c'est donc un isomorphisme de
groupes.
\end{demonstration}

\begin{lemme}[Lemme chinois en termes d'anneaux r\'esiduels]
Soient $r$ et $s$ deux entiers $\geq 2$ et premiers entre eux.
Alors l'application
\[
\Phi : \Z/rs\Z \ra \Z/r\Z \times \Z/s\Z \ko
\class{rs}{a} \mapsto (\class{r}{a}, \class{s}{a})
\]
est un isomorphisme d'anneaux.
\end{lemme}

\begin{remarque}
Ainsi nous voyons que tous les anneaux suivants sont isomorphes
\[
\Z/24\Z \ko
\Z/3\Z \times \Z/8\Z \ko
\Z/8\Z \times \Z/3\Z.
\]
Nous verrons plus tard que ces anneaux {\em ne sont pas}
isomorphes \`a $\Z/6\Z\times \Z/4\Z$. 
\end{remarque}

\begin{demonstration}
V\'erifions que $\Phi$ est un homomorphisme. En effet
pour $a,b\in\Z$, nous avons
\begin{eqnarray*}
\Phi(\class{rs}{a} + \class{rs}{b}) & = &
                       \Phi(\class{rs}{a+b}) =
                               (\class{r}{a+b}, \class{s}{a+b}) \\
 & = & (\class{r}{a}+\class{r}{b}, \class{s}{a}+\class{s}{b}) \\
 & = & (\class{r}{a}, \class{s}{a}) + (\class{r}{b}, \class{s}{b}).
\end{eqnarray*}
De m\^eme, on v\'erifie que $\Phi$ est compatible \`a la
multiplication. V\'erifions que $\Phi$ est injective.
En effet, si $\Phi(\class{rs}{a})=\Phi(\class{rs}{b})$, alors
nous avons $(\class{r}{a}, \class{s}{a})=(\class{r}{b}, \class{s}{b})$
et donc
\begin{eqnarray*}
a & \equiv & b\; (r) \\
a & \equiv & b \; (s) .
\end{eqnarray*}
Ainsi la diff\'erence $a-b$ est divisible par $r$ est $s$
et donc par le produit $r\,s$, puisque $r$ et $s$ sont premiers
entre eux. Donc les classes $\class{rs}{a}$ et $\class{rs}{b}$
sont \'egales. V\'erifions que $\Phi$ est surjective. 
En effet soient $a_1, a_2\in \Z$. Alors nous cherchons $a\in \Z$
tel que $(\class{r}{a}, \class{s}{a})=(\class{r}{a_1}, \class{s}{a_2})$.
De fa\c{c}on \'equivalente, nous cherchons $a\in\Z$ solution du
syst\`eme
\begin{eqnarray*}
a & \equiv & a_1 \;(r)\\
a & \equiv & a_2 \;(s) 
\end{eqnarray*}
Or, puisque $r$ et $s$ sont premiers entre eux, d'apr\`es le
lemme chinois pour les congruences, il existe une solution
$a\in\Z$.
\end{demonstration}

\begin{remarque} Les anneaux $\Z/rs\Z$ et $\Z/r\Z \times \Z/s\Z$
ont m\^eme cardinal (\'egal \`a $r\,s$). Dans la d\'emonstration,
il aurait donc suffi de montrer soit la surjectivit\'e soit
l'injectivit\'e de l'application $\Phi$ pour conclure qu'elle
est en fait bijective. Nous avons donn\'e les deux d\'emonstrations
pour mieux \'etablir le lien avec le lemme chinois en
termes de congruences.
\end{remarque}

\begin{corollaire} \label{groupes-mult-iso}
Soient $r,s$ des entier $\geq 2$ et
premiers entre eux. Alors l'application 
\[
\Phi^* : (\Z/rs\Z)^\star \ra (\Z/r\Z)^\star \times (\Z/s\Z)^\star \ko
\class{rs}{a} \mapsto (\class{r}{a}, \class{s}{a})
\]
est un isomorphisme de groupes. En particulier, elle est
bijective et le deux groupes sont donc du m\^eme ordre.
\end{corollaire}

\begin{demonstration} Le corollaire r\'esulte du lemme
pr\'ec\'edent et du lemme (\ref{anneaux-groupes}).
\end{demonstration}


\begin{definition} Soit $n$ un entier $\geq 2$. On d\'efinit
$\phi(n)$ comme le cardinal du groupe des \'el\'ements
inversibles de l'anneaux $\Z/n\Z$. La fonction 
$\phi$ est {\em l'indicatrice d'Euler}.
\end{definition}

\begin{corollaire} Si $r$ et $s$ sont deux entiers $\geq 2$
et premiers entre eux on a 
\[
\phi(rs)=\phi(r)\, \phi(s).
\]
\end{corollaire}

\begin{demonstration} Ceci r\'esulte aussit\^ot de la 
d\'efinition de $\phi(rs)$ et du corollaire (\ref{groupes-mult-iso}).
\end{demonstration}

\begin{remarque} Le corollaire pr\'ec\'edent nous permet
de calculer la valeur de $\phi(n)$ pour tout entier dont
nous connaissons la d\'ecompositions en facteurs premiers.
En effet, si nous avons
\[
n= p_1^{e_1} \, p_2 ^{e_2} \, \ldots \, p_r^{e_r}
\]
alors en applicant le corollaire plusieurs fois nous trouvons
\[
\phi(n) = \phi(p_1^{e_1}\, \phi(p_2^{e_2}) \,\ldots \, \phi(p_r^{e_r}).
\]
Mais d'apr\`es \ref{???}, nous savons que pour un nombre premier
$p$ nous avons
\[
\phi(p^k)= p^k-p^{k-1}.
\]
Donc 
\[
\phi(n)=(p_1^{e_1}-p_1^{e_1-1}) (p_2^{e_2} - p_2^{e_2-1}) \ldots
        (p_r^{e_r} - p_r{e_r-1}).
\]
Par exemple,
\[
\phi(36)=\phi(4 \times 9) = \phi(4) \, \phi(9)
= (4-2)\times (9-3) = 12
\]
et 
\[
\phi(1995)= \phi(3\times 5\times 7 \times 19) = 864.
\]
\end{remarque}
















%\input{arith13}
\Absatz{Notion d'ordre d'un \'el\'ement d'un groupe}

\begin{lemme}
Soit $(G,\star)$ un groupe et $g$ un \'el\'ement de $G$. Alors il
existe une application
\[
\exp_g : \Z \ra G
\]
et une seule telle que
\begin{eqnarray*}
\exp_g(1)  & = & g \\
\exp_g(k+l) & = & \exp_g(k) \star \exp_g(l)
\end{eqnarray*}
quels que soient $k,l \in\Z$. 
\end{lemme}

\begin{demonstration}
Nous admettons ce r\'esultat.
\end{demonstration}

\begin{remarques}
\item La seconde condition de la d\'efinition signifie que $\exp_g$
est un homomorphisme de groupes de $\Z$ vers $G$. 
\item Supposons que $(G,\cdot)$ est un groupe dont la loi
est not\'ee multiplicativement. Alors pour tout $n$ entier
positif, nous avons
\begin{eqnarray*}
\exp_g(n) & = & \underbrace{g\cdot g \cdots g}_{n}= g^n \\
\exp_g(-n) & = & \exp_g(n)^{-1}= (g^{-1})^n.
\end{eqnarray*}
Nous \'ecrirons $g^n$ pour $exp_g(n)$ pour tout $n$ entier.

\item Supposons que $(A, +)$ est un groupe dont la loi
est not\'ee additivement. Alors pour tout $n$ entier positif,
nous avons
\begin{eqnarray*}
\exp_a(n) & = & \underbrace{a + a +\cdots + a}_{n} = n\,a \\
\exp_a(-n) & = & - \exp_a(n) = -n\, a.
\end{eqnarray*}
Nous \'ecrirons $n\, a$ pour $\exp_a(n)$ pour tout $n$ entier.
\end{remarques}




\begin{corollaire} 
\begin{itemize} 
\item[a)] Soit $(G,\cdot)$ un groupe dont la loi est
not\'ee multiplicativement et $g$ un \'el\'ement
de $G$. Pour $k,l\in\Z$, on a les \'egalit\'es suivantes
\begin{eqnarray*}
g^1 & = & g \\
g^{k+l} & = & g^k \star g^l \\
g^0 & = & e_G \\
(g^k)^l & = & g^{kl}
\end{eqnarray*}
\item[b)] Soit $(A,+)$ un groupe commutatif dont la loi est not\'ee
additivement et $a$ un \'el\'ement de $A$.
Pour $k,l\in\Z$ on a les \'egalit\'es suivantes
\begin{eqnarray*}
1\,a & = & a \\
(k+l) \, a & = & k\, a + l\, a \\
0 \, a & = & 0_A \\
k \, (l\, a) & = & (kl)\, a
\end{eqnarray*}
\end{itemize}
\end{corollaire}

\begin{demonstration} Les deux parties sont des traductions
dans la nouvelle notation de certaines propri\'et\'es de 
la fonction $\exp$. Montrons-les dans les notations de a). 
Les premi\`eres deux \'egalit\'es ne font que traduire
dans la nouvelle notation les propri\'et\'es de la d\'efinition
de $\exp_g$. La troisi\`eme propri\'et\'e r\'esulte du fait
que $\exp_g$ est un homomorphisme.
Pour la derni\`ere propri\'et\'e, fixons $k\in\Z$
et consid\'erons l'application
\[
f: \Z \ra G, \ko l \mapsto g^{kl}.
\]
Nous avons clairement $f(1)=g^k$ et 
\[
f(l+l')=g^{k(l+l')}= g^{kl+kl'} = g^{kl} \star g^{kl'} = f(l)\star f(l').
\]
Par l'unicit\'e de l'application $\exp_{g^k}$ nous pouvons
conclure que $f(l)=\exp_{g^k}(l)$ pour tout $l\in \Z$
et donc que $f(l)=(g^k)^l$ pour tout $l\in\Z$.
\end{demonstration}



\begin{definition}
Soit $(G,\star)$ un groupe et $g$ un \'el\'ement de $G$.
{\em L'ordre de $g$} est le plus petit entier $n\geq 1$
tel que $\exp_g(n)=e_G$ s'il existe un tel entier. Sinon,
l'ordre de $g$ est infini. On note $\ord_G(g)$ ou
$\ord\,(g)$ l'ordre de $g$ dans $G$.
\end{definition}

\begin{remarques}
\item Supposons que $(G,\cdot)$ est un groupe dont la loi
est not\'ee multiplicativement et soit $g\in G$. Alors nous avons
\[
\ord_G\,(g)=\inf\{ n\in\N \; | \; n\geq 1\mbox{  et  } g^n=e\}.
\]
Supposons que $(A,+)$ est un groupe commutatif dont la loi
est not\'ee additivement et soit $a\in A$. Alors nous avons
\[
\ord_G\,(a)=\inf\{ n\in\N\; | \; n\geq 1\mbox{  et  } n a = 0_A\}.
\]
\item 
Soit $(G,\cdot)$ un groupe dont la loi est not\'ee multiplicativement
(pour all\'eger les notations). 
Supposons que $g\in G$ est d'ordre fini $n$. Alors nous 
avons
\[
g^{k+n}= g^k\cdot g^n = g^k \cdot e = g^k
\]
pour tout entier $k$ et $n$ est le plus petit entier $\geq 1$
avec cette propri\'et\'e. Autrement dit, {\em la suite
des puissances de $g$
\[
g^0=e\ko g \ko g^2 \ko \ldots, g^k, \ldots
\]
est p\'eriodique de p\'eriode $n$.} Nous avons aussi
\[
g^{a+kn}= g^a g^{kn}= g^a (g^n)^k = g^a e^k = g^a
\]
pour tout entier $a\in\Z$ et tout entier $k\in\Z$. Autrement
dit {\em la valeur de $g^{a}$ ne d\'epend que de la classe
de congruence de $a$ modulo $n$.}
\end{remarques}

\begin{lemme} \label{ordre-dans-Zn-additif}
Soit $n$ un entier $\geq 2$ et soit $\ol{a}$
une classe modulo $n$ consid\'er\'ee comme \'el\'ement
du groupe $(A,+)=(\Z/n\Z, +)$. Alors
\[
\ord_{\sZ/n\sZ} (\ol{a}) = \frac{\ppcm(a,n)}{a} = \frac{n}{\pgcd(a,n)}.
\]
\end{lemme}

\begin{demonstration}
Nous avons $k\ol{a}=\ol{0}$ ssi $ka$ est un multiple de $n$,
c'est-\`a-dire un multiple commun \`a $a$ et $n$. 
Donc $ka$ doit \^etre un multiple de $\ppcm(a,n)$ et
$k$ un multiple de $\ppcm(a,n)/a$. Compte tenu de l'\'egalit\'e
\[
\ppcm(a,n) = \frac{a\,n}{\pgcd(a,n)}
\]
nous obtenons aussi la seconde \'egalit\'e.
\end{demonstration}

\begin{remarque} Il {\em n'existe pas} de formule analogue
pour l'ordre d'un \'el\'ement $\ol{x}$ dans le groupe
multiplicatif $(\Z/n\Z)^*$. Cependant nous verrons que 
cet ordre est toujours un diviseur de $\phi(n)$, l'ordre
du groupe $(\Z/n\Z)^*$.
\end{remarque}

\begin{lemme} \label{sous-groupe-el-infini}
Soit $(G,\star)$ un groupe et $g$ \'el\'ement
de $G$. Alors $g$ est d'ordre infini ssi l'application
\[
\exp_g: \Z \ra G 
\]
est injective. En particulier, tous les \'el\'ements
d'un groupe fini sont d'ordre fini.
\end{lemme}

\begin{demonstration} 
Si l'application $\exp_g$ est injective
nous avons $\exp_g(n)\neq \exp_g(0)$ pour tout $n>0$. 
Puisque $\exp_g(0)=e$, nous avons donc $\exp_g(n)\neq e$
pour tout $n>0$ et $g$ est d'ordre infini.

R\'eciproquement supposons $g$ d'ordre infini. Soient
$k\leq l$ des entiers tels que $\exp_g(k)=\exp_g(l)$. Alors
nous avons $\exp_g(l-k)=e$. Puisque $l-k\geq 0$
et que $g$ est d'ordre infini, il s'ensuit que $k=l$
et donc que $\exp_g$ est injective. 
\end{demonstration}

\begin{lemme} \label{Zn-iso-puiss-g} \label{sous-groupe-el-fini}
Soit $(G,*)$ un groupe et $g\in G$ un \'el\'ement
d'ordre fini $n$. Alors l'application
\[
\Z/n\Z \ra G\ko \ol{a} \mapsto \exp_g(a)
\]
est bien d\'efinie et injective. En particulier,
l'ensemble des \'el\'ements de la forme
$\exp_g(a)$, $a\in\Z$, est de cardinal $n$.
\end{lemme}

\begin{demonstration}
Supposons pour all\'eger les notations que la loi de $G$ est not\'ee
multiplicativement. Nous avons donc 
\[
exp_g(a)=g^a \mbox{ et } g^n=e
\]
pour tout $a\in\Z$. Donc
\[
exp_g(a+kn)= g^{a+kn} = g^a g^{kn} = g^a (g^n)^k = g^a e^k = g^a.
\]
L'application est donc bien d\'efinie. Supposons que $a\leq b$
sont deux entiers dont les classes ont m\^eme image. Alors nous avons
$g^a=g^b$ et donc $g^{b-a}=e$. Pour montrer que $n$ divise $b-a$,
effectuons la division euclidienne $b-a=qn+r$ de $b-a$ par $n$.
Par d\'efinition, nous avons $0 \leq r \leq (n-1)$. De l'autre
c\^ot\'e, nous avons $e=g^{b-a}= g^r$. Puisque $g$ est d'ordre
$n$, il s'ensuit que $n$ divise $b-a$ et donc que $\ol{a}=\ol{b}$. 
\end{demonstration}



\begin{theoreme}[Lagrange] \label{lagrange} Soit $(G,*)$ un groupe fini.
L'ordre de tout \'el\'ement de $G$ divise l'ordre de $G$.
\end{theoreme}

\begin{exemple} \label{exemple-lagrange}
Consid\'erons le groupe $G=(\Z/11\Z)^*$. L'ordre de $G$ est
de $10$. Voici les ordres des \'el\'ements de $G$ :
\begin{center}
\begin{tabular}{|c|cccccccccc|} \hline
\rule[-2mm]{0mm}{7mm}
$g$ & $\ol{1}$ & $\ol{2}$ & $\ol{3}$ & $\ol{4}$ & $\ol{5}$ &
       $\ol{6}$ & $\ol{7}$ & $\ol{8}$ & $\ol{9}$ & $\ol{10}$ \\ \hline
\rule[-2mm]{0mm}{7mm}
$\ord\,(g)$ & $1$ & $10$ & $5$ & $5$ & $5$ & $10$ & $10$ & $10$ & $5$
& $2$ \\ \hline
\end{tabular}
\end{center}
Notons que le nombre d'\'el\'ements d'ordre $10$ est de
$4=\phi(10)$, le nombre d'\'el\'ements d'ordre $5$
est de  $4=\phi(5)$ et le nombre d'\'el\'ments d'ordre 
$2$ est de $1=\phi(2)$. Nous verrons que ce n'est pas
un hasard (\ref{nombre-delements-dordre-d}). 
Nous verrons aussi comment calculer facilement
ce tableau (exemples \ref{calcul-ordre})
\end{exemple}


\begin{demonstration} Pour all\'eger les notations, supposons
que la loi de $G$ est not\'ee multiplicativement. Soit $g\in G$.
La d\'emonstration se fait en plusieurs \'etapes :

{\em Premi\`ere \'etape :  la relation d\'efinie par
\[
x \equiv x' \; (g) \Longleftrightarrow x = x' \,g^k 
                                       \mbox{  pour un  } k\in\Z\ko
\]
est une relation d'\'equivalence.}
Nous laissons cette v\'erification au lecteur.
Notons $\ol{x}$ la classe d'\'equivalence d'un \'el\'ement $x$.
Par d\'efinition, la classe de $x$ est form\'ee de tous
les \'el\'ements de la forme $x\,g^k$, $k\in \Z$.

{\em Seconde \'etape : le cardinal de la classe de $e$ est l'ordre de
$g$.} En effet, la classe de $e$ est form\'ee de tous les \'el\'ements
de la forme $g^k$, $k\in\Z$. C'est donc l'image de l'application
$\exp_g: \Z \ra G$. Nous avons vu au lemme (\ref{sous-groupe-el-fini}) qu'elle
est en bijection avec $\Z/n\Z$ o\`u $n$ est l'ordre de $g$.

{\em Troisi\`eme  \'etape : 
toutes les classes d'\'equivalence ont m\^eme cardinal
que la classe de $e$.}
En effet, si $x$ est un \'el\'ement de $G$, nous avons des bijections
inverses l'une de l'autre entre $\ol{e}$ et $\ol{x}$ donn\'ees par
les applications $y \mapsto xy$ resp. $z \mapsto x^{-1} z$. 

{\em Quatri\`eme \'etape : le cardinal de la classe de $e$ divise
l'ordre de $G$.} En effet, nous savons que $G$ est la r\'eunion
disjointe des classes d'\'equivalence. L'ordre de $G$ est 
donc la somme des cardinaux des classes. Or toutes les
classes ont m\^eme cardinal que $\ol{e}$. L'ordre de $G$
est donc \'egal au cardinal de la classe de $e$ multipli\'e
par le nombre de classes d'\'equivalence. 

{\em Conclusion} : l'ordre de $g$, qui est \'egal
au cardinal de la classe de $e$ (seconde \'etape), divise
l'ordre de $G$ (troisi\`eme \'etape). 
\end{demonstration} 

\begin{corollaire}[Th\'eor\`eme d'Euler] \label{euler}
Soit $n$ un entier $\geq 2$ et
$a$ un entier premier avec $n$. Alors on a
\[
a^{\phi(n)} \equiv 1 \; (n),
\]
o\`u $\phi$ est l'indicatrice d'Euler.
\end{corollaire}

\begin{demonstration} Comme $a$ est premier avec $n$, la classe $g=\ol{a}$
appartient au groupe $G=(\Z/n\Z)^*$. L'affirmation r\'esulte du th\'eor\`eme
de Lagrange car $\phi(n)$ est l'ordre du groupe $(\Z/n\Z)^*$ par d\'efinition.
\end{demonstration}

\begin{corollaire}[Petit Th\'eor\`eme de Fermat] \label{fermat}
Si $p$ est un nombre premier
et $a$ un entier qui n'est pas divisible par $p$, on a
\[
a^{p-1}\equiv 1\;(p).
\]
\end{corollaire}
\begin{demonstration} On applique le th\'eor\`eme d'Euler en utilisant que
$\phi(p)=p-1$ pour un nombre premier. 
\end{demonstration}


\begin{remarque}
Les th\'eor\`emes de Fermat (petit) et d'Euler permettent
de calculer tr\`es rapidement certains restes de puissances.
Dans les exemples suivants, on cherche le reste $r$ de la
division euclidienne de $a$ par $b$ :
\end{remarque}

\begin{exemples}
\item $a=67^{100}$, $b=101$ : le nombre $101$ est premier
et $67$ n'est pas divisible par $101$. D'apr\`es le petit
th\'eor\`eme de Fermat, on a $67^{100} \equiv 1 \;(101)$
et donc $r=1$.

\item $a=1995^{540}$, $b=541$ : le nombre $541$ est premier
et $1995$ n'est pas divisible par $541$. D'apr\`es le
petit th\'eor\`eme de Fermat, on a $1995^{540}\equiv 1\; (541)$
et donc $r=1$. 

\item $a=25^{24}$, $b=72$ : nous avons
$\phi(72)= \phi(8\times 9) = \phi(8) \phi(9)= 4\times 6= 24$.
Les nombres $72$ et $25$ sont premiers entre eux. Nous pouvons
donc appliquer le th\'eor\`eme d'Euler pour conclure
que $25^{24}\equiv 1\; (72)$. Donc $r=1$.

\item $a=51^{24}$, $b=72$ : nous avons $\phi(72)=24$
(voir le num\'ero pr\'ec\'edent). Or, {\em les nombres $51$ et
$72$ ne sont pas premiers entre eux et nous ne pouvons pas
appliquer le th\'eor\`eme d'Euler.} Cependant, soit $x = 51^{24}$.
D'apr\`es le lemme chinois, pour conna\^{\i}tre la classe de
$x$ modulo $72$, il suffit de conna\^{\i}tre les restes de
$x$ modulo $8$ et modulo $9$. Or
\begin{eqnarray*}
x  & \equiv & 51^{24}  \equiv 3^{24} \equiv 1 \;\;(8) \\
x  & \equiv & 51^{24} \equiv 6^{24} \equiv 0 \;\;(9).
\end{eqnarray*}
Ici, nous avons appliqu\'e le th\'eor\`eme d'Euler
\`a $3$ et $8$ ($\phi(8)=4$) et nous avons utilis\'e le fait
que $6^2\equiv 0 \;(9)$. Le lemme chinois nous permet de
conclure que $x \equiv 9\;(72)$ et le reste recherch\'e
est donc $r=9$.

\end{exemples}








%\input{arith14}
\Absatz{Algorithme de calcul rapide des puissances}
\el
Soit $G$ un groupe dont la loi est
not\'ee multiplicativement. Soit $g$ un \'el\'ement de $G$
et $n$ un entier $\geq 2$. Pour calculer $g^n$, on utilise
l'algorithme suivant qui consiste \`a construire
r\'ecursivement des suites 
$x_k, y_k, q_k$, $k\geq 1$, o\`u $x_k, y_k \in G$
et $q_k \in \N$ :
\begin{itemize}
\item[1)] Initialisation : on pose $x_1=g$, $y_1=e$, $q_k=n$.
\item[2)] Passage \`a l'\'etape $k$ : on pose $x_k=x_{k-1}^2$,
on prend pour $q_k$ le quotient de la division de $q_{k-1}$
par $2$ et on pose
\[
y_k= \left\{ 
\begin{array}{cc} y_{k-1} & \mbox{si $q_{k-1}$ est pair} \\
                  x_{k-1} y_{k-1}  & \mbox{si $q_{k-1}$ est impair}
\end{array}
\right.
\]
\item[3)] Arr\^et : quand $q_k=1$, l'algorithme s'arr\^ete
et la puissance recherch\'ee est $g^n=x_k y_k$. 
\end{itemize}
Dans la pratique, on organise les suites $x_k, y_k, q_k$ dans
un tableau. Voir les exemples ci-dessous.

\begin{Exemples} Calculons $2^{50}$ dans $(\Z/101\Z)^*$ :
\begin{center}
\begin{tabular}{|r|rrr|} \hline
$k$ & $x_k$ & $y_k$ & $q_k$ \\ \hline
1 & 2 & 1 & 50 \\ 
2 & 4 & 1 & 25 \\
3 & 16 & 4 & 12 \\
4 & 54 & 4 & 6 \\
5 & 88 & 4 & 3 \\
6 & 68 & 49 & 1 \\ \hline
  &    & 100 &  \\ \hline
\end{tabular}
\end{center}
Nous trouvons donc que $2^{50} \equiv -1 \; (101)$.
La premi\`ere colonne ne d\'epend que de $g=2$ et nous pouvons
la r\'eutiliser. Dans le tableau suivant, nous utilisons deux
fois la m\^eme premi\`ere colonne pour calculer $3^{50}$ et
$3^{20}$ dans $(\Z/101\Z)^*$.
\begin{center}
\begin{tabular}{|r|rr|rr|} \hline
$x_k$ & $y_k$ & $q_k$ &  $y_k$ & $q_k$ \\ \hline
3 & 1 & 50 & 1 & 20 \\ 
9 & 1 & 25 & 1 & 10 \\ 
81 & 9 & 12 & 1 & 5 \\
97 & 9 & 6 & 81 & 2 \\
16 & 9 & 3 & 81 & 1 \\
54 & 43 & 1 &   &   \\ \hline
   & 100 &  & 84 &  \\ \hline
\end{tabular}
\end{center}
\end{Exemples}

\begin{lemme} L'algorithme d\'ecrit ci-dessus est correct.
\end{lemme}

\begin{demonstration} Nous allons montrer par r\'ecurrence que nous avons
$x_k^{q_k}\,y_k=g^n$. Ceci entra\^{\i}nera l'affirmation car pour $q_k=e$,
cette \'egalit\'e se sp\'ecialise en $x_k y_k=g^n$. 

A l'\'etape $k=1$, l'affirmation est vraie par d\'efinition de l'initialisation
de l'algo\-rith\-me. Supposons qu'elle est vraie pour l'\'etape $k-1$ et montrons-la
pour l'\'etape $k$. Soit $q_{k-1}= 2\, q_k+r_k$ la division euclidienne de 
$q_{k-1}$ par $2$. Par l'hypoth\`ese de r\'ecurrence, nous avons
\[
x_{k-1}^{q_{k-1}} y_{k-1}=g^n.
\]
Si nous substituons le r\'esultat de la division euclidienne pour $q_{k-1}$,
nous trouvons
\[
g^n= x_{k-1}^{2\, q_k +r_k}y_{k-1} = (x_{k-1}^2)^{q_k} (x_{k-1}^{r_k}) y_{k-1}
= x_k^{q_k} y_k.
\]
Pour la derni\`ere \'egalit\'e, nous avons utilis\'e la d\'efinition de
$x_k$ et $y_k$ (le nombre $q_{k-1}$ est pair ssi $r_k=0$). 
\end{demonstration}


\Absatz{Calcul de l'ordre d'un \'el\'ement}
\el
Soit $n$ un entier. Un diviseur positif $d$ de $n$ est 
{\em maximal} s'il est de la forme $n/p$ o\`u $p$ est un
diviseur premier de $n$.
Soit $G$ un groupe fini dont la loi est not\'ee multiplicativement. Soit $g$ un \'el\'ement de $G$. Soit $n$ un entier positif.

\begin{lemme} \label{calcul-des-ordres}
\begin{itemize}
\item[a)] On a $g^n=e$ si et seulement si $n$ est un multiple de 
l'ordre de $g$.
\item[b)] L'\'el\'ement $g$ est d'ordre $n$ si et seulement si
$g^n=e$ et $g^d\neq e$ pour tout diviseur maximal de $n$.
\item[c)] Si $g$ est d'ordre $n$ et $d$ divise $n$, alors
$g^d$ est d'ordre $n/d$.
\item[d)] Plus g\'en\'eralement, si $g$ est d'ordre $n$ et
$a$ un entier quelconque, alors $g^a$ est d'ordre $n/\pgcd(a,n)$.
\end{itemize}
\end{lemme}

\begin{demonstration} a) Ceci est clair d'apr\`es le lemme
\ref{Zn-iso-puiss-g} qui affirme que l'application $\Z/\ord(g)\Z \ra G$,
$\ol{k} \mapsto g^k$ est injective.

b) La condition est clairement n\'ecessaire. Supposons r\'eciproquement
qu'elle est v\'erifi\'e. Alors $n$ est multiple de l'ordre de
$g$ d'apr\`es a), mais aucun diviseur propre de $n$ n'est multiple
de l'ordre de $g$. 
(tout diviseur propre divise un diviseur maximal de $n$).
Donc $n=\ord(g)$.

c) Nous avons $(g^d)^k=g^{dk}$ ce qui donne imm\'ediatement 
l'affirmation. 

d) D'apr\`es le lemme \ref{Zn-iso-puiss-g}, nous avons $g^k=e$ ssi
$\ol{k}=\ol{0}$ dans $\Z/n\Z$. Donc l'ordre de $g^a$ est \'egal
\`a l'ordre de $\ol{a}$ dans $\Z/n\Z$. Ce dernier est \'egal
\`a $n/\pgcd(a,n)$ d'apr\`es le lemme \ref{ordre-dans-Zn-additif}. 
\end{demonstration}

\begin{remarque} 
Pour d\'eterminer l'ordre de $g$, on calcule les puissances
$g^d$ pour les diviseurs maximaux $d$ de $n$. Si on a
$g^d\neq e$ pour tout diviseur maximal, alors $g$ est
d'ordre $n$ (et $G$ est cyclique engendr\'e par $g$ voir
ci-dessous). Sinon, on a $g^d=e$ pour un diviseur maximal $d$ de $n$
et on recommence avec $n$ remplac\'e par $d$. Dans le calcul
des puissances $g^{d'}$ pour les diviseurs maximaux $d'$ de $d$
on pourra cependant omettre tous ceux qui divisent 
un diviseur maximal $d''$ de $n$ pour lequel $g^{d''}\neq e$.
Voir l'exemple suivant.
\end{remarque}

\begin{labelledlist}{Exemples \label{calcul-ordre}} 
\item 
Calculons l'ordre de $2$ dans $(\Z/113\Z)^*$.
Ce groupe est d'ordre $n=112=7\times 16$. Les diviseurs maximaux
de $n$ sont $16$ et $56$. Calculons donc $2^{56}$ et $2^{16}$.
\begin{center}
\begin{tabular}{|r|rr|rr|}\hline
$x_k$ & $y_k$ & $q_k$ & $y_k$ & $q_k$ \\ \hline
2 & 1 & 56 & 1 & 16  \\ 
4 & 1 & 28 & 1 & 8  \\
16 & 1 & 14 & 1 & 4 \\
30 & 1 & 7  & 1 & 2 \\
109 & 30 & 3 & 1 & 1 \\
16 & 106 & 1 &   &   \\ \hline
   &   1 &   & 109 &  \\ \hline
\end{tabular}
\end{center}
Ainsi $2^{16}\neq e$ et $2^{56}=e$. Les diviseurs maximaux de
$56$ sont $8$ et $28$. Puisque $2^{16}\neq e$ nous avons
$2^8\neq e$ et il suffit de calculer $2^{28}$. On trouve
$2^{28}=1$. Les diviseurs maximaux de $28$ sont $4$ et $14$.
Puisque $2^{8}\neq 1$, nous avons $2^4\neq 1$ et il suffit
de calculer $2^{14}$. On trouve $2^{14}=-1$ et 
{\em l'ordre de $2$ dans $(\Z/113\Z)^*$ est donc de~$28$.}

\item D\'eterminons les ordres des \'el\'ements de
$(\Z/11\Z)^*$. Calculons l'ordre de $2$. Nous avons
$2^{10}\equiv 1\;(11)$ par le petit th\'eor\`eme de Fermat.
Les diviseurs maximaux de $10$ sont $2$ et $5$. Nous avons
\[
2^2=4\ko 2^5 \equiv 2\times 4\times 4 \equiv -1 \;(11).
\]
Donc $2$ est d'ordre $10$ et tout \'el\'ement de $(\Z/11\Z)^*$
est une puissance de $2$ d'apr\`es le lemme (\ref{Zn-iso-puiss-g}).
Calculons ces puissances
\begin{center}
\begin{tabular}{|c|cccccccccc|} \hline
\rule[-2mm]{0mm}{7mm}
$k$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ &
       $6$ & $7$ & $8$ & $9$  \\ \hline
\rule[-2mm]{0mm}{7mm}
$2^k$ & $1$ & $2$ & $4$ & $8$ & $5$ & $10$ & $9$ & $7$ & $3$
& $6$ \\ \hline
\end{tabular}
\end{center}
Maintenant, on calcule facilement les ordres de tous les 
\'el\'ements \`a l'aide des parties b) et c) du lemme.
Par exemple, on a
\begin{eqnarray*}
\ord(3) & = & \ord(2^8) = \frac{10}{\pgcd(10,8)} = 5 \\
\ord(4) & = & \ord(2^2) = \frac{10}{2} = 5.
\end{eqnarray*}
On trouve la table suivante (voir \ref{exemple-lagrange})
\begin{center}
\begin{tabular}{|c|cccccccccc|} \hline
\rule[-2mm]{0mm}{7mm}
$g$ & $\ol{1}$ & $\ol{2}$ & $\ol{3}$ & $\ol{4}$ & $\ol{5}$ &
       $\ol{6}$ & $\ol{7}$ & $\ol{8}$ & $\ol{9}$ & $\ol{10}$ \\ \hline
\rule[-2mm]{0mm}{7mm}
$\ord\,(g)$ & $1$ & $10$ & $5$ & $5$ & $5$ & $10$ & $10$ & $10$ & $5$
& $2$ \\ \hline
\end{tabular}
\end{center}

\end{labelledlist}

%\input{arith15}
\Absatz{Groupes cycliques}
\el
\begin{definition} Soit $(G,*)$ un groupe. 
Un {\em sous-groupe} de $G$ est
une partie $H$ de $G$ v\'erifiant les trois conditions
suivantes
\begin{itemize}
\item $e_G\in H$,
\item $h\star k \in H$ pour tous les $h,k\in H$,
\item $h^{-1}\in H$ pour tous les $h\in H$.
\end{itemize}
\end{definition}

\begin{exemples} 
\item Les parties $\{e_G\}$ et $G$ de $G$ sont
toujours des sous-groupes. L'intersection de toute famille
de sous-groupes est un sous-groupe.
\item Pour tout $n\in\Z$, la partie
$n\Z$ est un sous-groupe de $(\Z,+)$. R\'eciproquement,
 tout sous-groupe de $\Z$ est de cette forme : en effet,
soit $S\subset \Z$ un sous-groupe. Si $S=\{0\}$, alors
$S=0\Z$ et il n'y a rien \`a d\'emontrer. Sinon, la
partie $S$ contient un entier non nul et donc 
un entier non nul positif (car $x$ appartient \`a $S$
si $-x$ appartient \`a $S$). Soit $n$ le plus petit
des entiers strictements positifs contenus dans $S$.
Alors on a clairement $n\Z \subset S$. R\'eciproquement,
si $x$ appartient \`a $S$ et que $x=q\,n+r$ est la
division euclidienne de $x$ par $n$, alors $r=x-q\, n$
appartient \`a $S$ et est positif et inf\'erieur \`a $n$.
Donc $r=0$ et $x\in n\Z$. 
\item 
Si $n$ est un entier $\geq 2$ et $d$ un diviseur de $n$,
alors $d \Z/n\Z = \{ \ol{dx} \;| \; x\in\Z\}$ est un sous-groupe
de $(\Z/n\Z,+)$ et tout sous-groupe de $\Z/n\Z$ est de cette
forme : en effet, si $A\subset \Z/n\Z$ est un sous-groupe
alors $\tilde{A}\subset \Z$ est un sous-groupe qui contient
$n\Z$. Donc $\tilde{A}=d\Z$ pour un entier $d$. La
condition $n\Z \subset d\Z$ montre que $n$ est un multiple
de $d$. 
\end{exemples}

\begin{definition} Soit $G$ un groupe et $X$ une partie
de $G$. On note $<X>$ et on appelle {\em sous-groupe engendr\'e
par $X$} la partie de $G$ form\'ee de tous les produits
d'\'el\'ements de $X$ et de leurs inverses (par convention
on pose $<X>=\{e_G\}$ si $X$ est vide).
\end{definition}

\begin{remarque} Il s'agit bien d'un sous-groupe.
\end{remarque}

\begin{exemple} Soit $G$ un groupe (dont la loi est not\'ee
multiplicativement) et $g$ un \'el\'ement de $G$. Alors 
le sous-groupe engendr\'e par la partie $X=\{g\}$ est 
\'egale \`a $\{ g^k\; | \; k\in\Z\}$. Ce sous-groupe est
isomorphe \`a $\Z$ si $g$ est d'ordre infini et
isomorphe \`a $\Z/n\Z$ si $g$ est d'ordre fini $n$
d'apr\`es les lemmes (\ref{sous-groupe-el-infini})
et (\ref{sous-groupe-el-fini}).
\end{exemple}

\begin{definition} Un groupe est {\em cyclique} 
s'il contient un \'el\'ement qui l'engendre : un 
{\em g\'en\'erateur}.
\end{definition}

\begin{remarque} D'apr\`es l'exemple pr\'ec\'edent, un groupe
cyclique est soit isomorphe \`a $\Z$ soit \`a $\Z/n\Z$ pour
un entier $n\geq 1$. R\'eciproquement, un groupe isomorphe
\`a $\Z$ ou $\Z/n\Z$ est cyclique (engendr\'e par l'image
de $1$ resp.~$\ol{1}$ par un isomorphisme choisi). 
Un groupe fini d'ordre $n$ est
cyclique si et seulement si il contient un \'el\'ement
d'ordre $n$. 
\end{remarque}

\begin{theoreme} \label{zpz-cyclique} Soit $p$ un nombre premier. Alors le
groupe $(\Z/p\Z)^*$ est cyclique.
\end{theoreme}

\begin{demonstration} Le th\'eor\`eme sera d\'emontr\'e
plus tard (\ref{dem-cyclique}).
\end{demonstration}

\begin{remarque} Le th\'eor\`eme ne donne pas de g\'en\'erateur
de ce groupe et c'est un probl\`eme ouvert de construire un
`g\'en\'erateur universel et explicite'. On ignore par exemple 
si la classe de $2$ engendre $(\Z/p\Z)^*$ pour une infinit\'e de nombres
premiers $p$ ou non. 
\end{remarque}

\Absatz{Racines de l'unit\'e}
\el
\begin{definition} Soit $G$ un groupe et $l$ un entier $\geq 1$.
Nous appellerons racine $l$-i\`emes de l'unit\'e dans $G$
les solutions $g\in G$ de l'\'equation $g^l=e$.
\end{definition}

\begin{remarque} Les racines $l$-i\`emes de l'unit\'e sont
exactement les \'el\'ements de $G$ dont l'ordre est un 
diviseur de $l$.
\end{remarque}

\begin{lemme} \label{racines-liemes} 
Soit $G$ un groupe cyclique d'ordre fini $n$ et
$g$ un g\'en\'erateur de $G$. Soit $l$ un entier 
$\geq 2$ et $R$ l'ensemble des solutions de l'\'equation
\[
x^l=e
\]
dans $G$.
\begin{itemize}
\item[a)] Si $l$ divise $n$, on a 
\[
R=\{ g^{k\,(n/l)} \; | \; k=0, 1, \ldots , l-1\}.
\]
\item[b)] Si $l$ est premier avec $n$, on a
\[
R=\{ e\}.
\]
\item[c)] Dans le cas g\'en\'eral, posons $l'=\pgcd(n,l)$. Alors 
\[
R= \{ g^{k\,(n/l')} \; | \; k=0, 1, \ldots, l'-1\}.
\]
\end{itemize}
\end{lemme}

\begin{exemple} On cherche les solutions de l'\'equation $x^5=1$
dans $\Z/2011\Z$. Si $x\in \Z/2011\Z$ est solution de cette
\'equation, alors $x x^4=1$ et donc $x$ est inversible 
(d'inverse $x^4$). Ainsi, il revient au m\^eme de chercher
les solutions de cette \'equation dans $(\Z/2011\Z)^*$.
Or le nombre $p=2011$ est premier et le groupe $G=(\Z/2011\Z)^*$
est donc cyclique (\ref{zpz-cyclique}). En outre $5$ 
divise l'ordre de $G$ qui est 2010. L'\'equation admet
donc exactement $5$ solutions et ces solutions sont de
la forme
\[
g^0\ko h=g^{402}\ko h^2=g^{804}\ko h^3=g^{1206}\ko h^4=g^{1608} \ko
\]
o\`u $g$ est un g\'en\'erateur de $(\Z/p\Z)^*$. 
Il reste \`a trouver un g\'en\'erateur et \`a calculer
ces puissances. Si on calcule les puissances maximales
de $2$, on trouve que $2^{2010/5}=1$. Donc $2$ n'est pas
un g\'en\'erateur. Par contre, les puissances maximales
de $3$ sont toutes diff\'erentes de $1$ et $3$ engendre
donc $(\Z/2011\Z)^*$. Si on calcule $h=3^{402}$,
on trouve $h=1328$. L'ensemble des solutions de l'\'equation
$x^5=1$ est donc form\'e de 
\[
1\ko h=1328\ko h^2=1948 \ko h^3=798 \ko h^4= 1958.
\]
\end{exemple}

\begin{demonstration}
Comme $G$ est cyclique, toute solution $x$ de $x^l=e$ est
de la forme $x=g^a$ pour un $a\in\Z$. Dans le cas de a),
on a donc $al \equiv 0\;(n)$ d'apr\`es le 
lemme (\ref{sous-groupe-el-fini}).
Cela signifie que $a$ est multiple de $n/l$.

Dans le cas de b), la congruence $al \equiv 0\;(n)$
implique $a\equiv 0\; (n)$ car $l$ est inversible
modulo $n$. 

Finalement, dans le cas de c), \'ecrivons $l=l' l''$
o\`u $l''$ et $n$ sont premiers entre eux. Alors
la congruence $al'l''\equiv 0\;(n)$ est \'equivalente
\`a $a l'\equiv 0\; (n)$ qui, elle, exprime que $a$
est multiple de $n/l'$. 
\end{demonstration}

\begin{lemme} \label{nombre-delements-dordre-d}
Soit $G$ un groupe cyclique d'ordre $n<\infty$ et
$g$ un g\'en\'erateur de $G$. Soit $d$ un diviseur de $n$.
Alors l'ensemble des \'el\'ements d'ordre $d$ de $G$ est 
form\'e des puissances 
\[
g^{k\,n/d}
\]
o\`u $k$ parcourt les classes inversibles modulo $d$. Ces \'el\'ements
sont deux \`a deux distincts. En particulier, le nombre d'\'el\'ements
d'ordre $d$ dans $G$ est \'egal \`a $\phi(d)$, le nombre de g\'en\'erateurs
de $G$ est \'egal \`a $\phi(n)$ et on a
\[
n= \sum_{d| n} \phi(d).
\]
\end{lemme}

\begin{exemple} Le nombre $p=2011$ est premier et le
groupe $G=(\Z/p\Z)^*$ est donc cyclique (th\'eor\`eme 
\ref{zpz-cyclique}) d'ordre $2010= 2\times 3\times 5 \times 67$.
Ce groupe contient donc $\phi(2010)= 2\times 4 \times 66= 528$
g\'en\'erateurs.
\end{exemple}

\begin{demonstration} Soit $x=g^a$ un \'el\'ement d'ordre
$d$ de $G$. Alors d'apr\`es le th\'eor\`eme  \ref{racines-liemes},
nous avons $a=k\, n/d$ pour un $k\in\Z$. Si $f$ est un facteur
commun \`a $k$ et $d$, alors on a $(g^a)^{(d/f)}=e$. Puisque
$g^a$ est d'ordre $d$, il s'ensuit $f=\pm 1$. Les \'el\'ements
de l'affirmation sont deux \`a deux distincts d'apr\`es
le lemme (\ref{sous-groupe-el-fini}). La derni\`ere affirmation
s'ensuit parce que $G$ est la r\'eunion disjointe de ses
parties form\'ees des \'el\'ements d'ordre $d$, o\`u $d$
parcourt les diviseurs $d$ de $n$, d'apr\`es le
th\'eor\`eme de Lagrange (\ref{lagrange}).
\end{demonstration}

 


%\input{arith16}
\Absatz{Structure du groupe des classes inversibles modulo un nombre premier}
\el\noindent
Nous d\'emontrerons dans cette section le th\'eor\`eme (\ref{zpz-cyclique})
qui affirme que le groupe $(\Z/p\Z)^*$ est cyclique lorsque
$p$ est premier. Nous aurons besoin du 


\begin{lemme} \label{racines-dans-un-corps}
Soit $p$ un nombre premier. Si
\[
P(X)=a_n X^n + a_{n-1} X^{n-1} + \ldots + a_1 X + a_0
\]
est un polyn\^ome de degr\'e $n$ \`a coefficients $a_i$ dans $\Z/p\Z$,
alors l'\'equation $P(x)=0$ admet au plus $n$ solutions $x$ dans $\Z/p\Z$.
\end{lemme}

\begin{remarque} On appelle {\em racines} de $P(X)$ les solutions $x$ de $P(x)=0$.
\end{remarque}

\begin{demonstration}
Nous proc\'edons par r\'ecurrence sur $n$. Si $n=1$, l'\'equation
$P(x)=0$ devient $a_1 x + a_0=0$. Elle admet $x=-a_0/a_1$ pour
unique solution (le coefficient $a_1$ est non nul car $P(X)$ est de degr\'e $1$).
Supposons l'affirmation d\'emontr\'ee pour des polyn\^omes de degr\'e
$<n$ et soit $P(X)$ de degr\'e $n$. Supposons que $P(x)=0$. 
Comme pour des polyn\^omes \`a coefficients r\'eels (ou \`a coefficients
dans tout autre corps) nous pouvons \'ecrire 
la division euclidienne du polyn\^ome $P(X)$ par le polyn\^ome $(X-x)$ 
\[
P(X)=(X-x)\, Q(X) + R(X)\ko
\]
o\`u $Q(X)$ est un polyn\^ome de degr\'e $n-1$ (le quotient) et 
$R(X)$ un polyn\^ome de degr\'e $<1$ (le reste) car $X-x$ est de degr\'e $1$. 
Donc $R(X)=c_0$ pour un
$c_0\in\Z/p\Z$. 
Si nous rempla\c{c}ons $X$ par $x$ dans l'\'equation
de la division euclidienne nous trouvons
\[
0=0\times Q(x) + c_0
\]
et donc $c_0=0$. Ainsi, nous avons $P(X)=Q(X)\,(X-x)$. Si $P(X)$ s'annule
en $y$, alors on a $Q(y)=0$ ou $y-x=0$ car $\Z/p\Z$ est un corps. Ainsi
toute solution $y\neq x$ de $P(X)=0$ est solution de $Q(X)=0$ et
par l'hypoth\`ese de r\'ecurrence on conclut que $P(X)$ admet au plus
$n-1$ racines diff\'erentes de $x$, c'est-\`a-dire $n$ racines au total.
\end{demonstration}

\begin{lemme} Soit $G$ un groupe d'ordre fini $n$ et tel que l'\'equation $x^d=e$
admet au plus $d$ solutions dans $G$ pour tout diviseur $d$ de $n$.
Alors $G$ est cyclique.
\end{lemme}

\begin{demonstration} Pour un diviseur $d$ de $n$, notons $\psi(d)$
le nombre d'\'el\'ements d'ordre $d$ de $G$. Supposons que $d$ est 
un diviseur de $n$ et qu'il existe dans $G$ un \'el\'ement $g$ d'ordre
$d$. Consid\'erons le sous-groupe $<g>$ engendr\'e par cet \'el\'ement.
Il est cyclique d'ordre $d$ et chacun de ses \'el\'ements est solution
de l'\'equation $x^d=e$ dans $G$. Ainsi, d'apr\`es l'hypoth\`ese sur
$G$, toute solution de $x^d=e$ dans $G$ se trouve en fait dans le
sous-groupe $<g>$. En particulier, tout \'el\'ement d'ordre $d$ de $G$
se trouve dans ce sous-groupe. Or nous savons qu'un groupe cyclique
contient exactement $\phi(d)$ \'el\'ements d'ordre $d$ (lemme 
\ref{nombre-delements-dordre-d}). 
Ainsi, le groupe
$G$ contient exactement $\phi(d)$ \'el\'ements d'ordre $d$. Nous avons
donc $\psi(d)=\phi(d)$ si $\psi(d)>0$ et $\psi(d)=0$ sinon. De toute
fa\c{c}on, nous avons $\psi(d)\leq \phi(d)$. Par cons\'equent, nous avons
\[
n= \sum_{d | n} \psi(d) \leq \sum_{d | n} \phi(d) =n\ko
\]
o\`u la derni\`ere \'egalit\'e provient du lemme (\ref{nombre-delements-dordre-d}).
Nous avons donc $\psi(d)=\phi(d)$ pour tout
diviseur $d$ de $n$ et en particulier, le groupe $G$ contient $\phi(n)$
\'el\'ements d'ordre $n$. Il nous aurait suffi d'un seul pour
conclure que $G$ est cyclique d'ordre $n$.
\end{demonstration}


\begin{corollaire} (=Th\'eor\`eme \ref{zpz-cyclique}) \label{dem-cyclique}
Si $p$ est premier, le groupe $(\Z/p\Z)^*$ est
cyclique. 
\end{corollaire}

\begin{demonstration} En effet, appliquons le lemme pr\'ec\'edent
\`a $G=(\Z/p\Z)^*$. D'apr\`es le lemme (\ref{racines-dans-un-corps}), l'\'equation
$X^d -1 =0$ admet au plus $d$ solutions pour tout diviseur $d$
de $n$ (et m\^eme pour tout $d\in\N$). 
\end{demonstration}

\Absatz{Structure du groupe des classes inversibles modulo une puissance d'un
nombre premier}

\begin{lemme} \label{coeff-bin-p-divisible} 
Soit $p$ un nombre premier et $1\leq k \leq p-1$. Alors
le coefficient binomial $C^k_p$ est divisible par $p$.
\end{lemme}


\begin{demonstration} En effet, nous avons
\[
C^k_p = \frac{p !}{k! \, (p-k)!} = \frac{p\, (p-1)\, (p-2) \, \ldots \,(p-k+1)}{1\times 2\times 3\times \ldots \times k}.
\]
Puisque $0<k<p$, le num\'erateur comporte un facteur $p$, 
mais le d\'enominateur n'en comporte pas. 
\end{demonstration}



\begin{theoreme} \label{structure-inversibles-p-puissance}
\begin{itemize}
\item[a)] Soit $p$ un nombre premier $>2$ et $k$ un entier $\geq 1$.
Alors le groupe $G=(\Z/p^k\Z)^*$ est cyclique d'ordre $(p-1)\,p^{k-1}$.
La classe de $1+p$ est un \'el\'ement d'ordre $p^{k-1}$ dans $G$. 
\item[b)] Le groupe $(\Z/2\Z)^*$ est trivial, le groupe $(\Z/4\Z)^*$
est cyclique d'ordre $2$ et pour $k\geq 2$, le groupe $(\Z/2^k\Z)^*$
est isomorphe \`a $\Z/2\Z \times \Z/2^{k-2}\Z$. Dans ce dernier
cas, l'\'el\'ement $5$ est d'ordre $2^{k-2}$ dans $(\Z/2^k\Z)^*$ et
tout \'el\'ement de ce groupe est de la forme $\pm 5^a$, $a\in\Z$.
\end{itemize}
\end{theoreme}

\begin{demonstration} Posons $G=(\Z/p^k\Z)^*$ resp. $G=(\Z/2^k\Z)^*$.

a) {\em Premi\`ere \'etape : pour $e\geq 0$, nous
avons
\[
(1+p)^{(p^e)} \equiv 1+ p^{e+1} \; (p^{e+2}).
\]
}
Proc\'edons par r\'ecurrence sur $e$. Pour $e=0$ l'affirmation est
trivialement vraie. Supposons la d\'emontr\'ee pour $e$. Nous avons donc
\[
(1+p)^{(p^e)} = 1 + p^{e+1}(1 + x p)
\]
pour un $x\in \Z$. Alors
\begin{eqnarray*}
(1+p)^{p^{e+1}} & = & ((1+p)^{(p^e)})^p = (1 + p^{e+1}(1+xp))^p \\
                & = & 1+ p\, p^{e+1}(1+xp) + (\sum_{k=2}^{p-1} C^k_p
p^{k(e+1)}(1+xp)^k) + p^{p(e+1)}(1+xp)^{p}.
\end{eqnarray*}
Si nous r\'eduisons modulo $p^{e+3}$ nous trouvons $1+p^{e+2}$
car les $C^k_p$ sont divisibles par $p$ et $p(e+1)\geq 3$
puisque $p\geq 3$. 

Notons $\phi: (\Z/p^k\Z)^* \ra (\Z/p\Z)^*$ l'application
qui \`a $x$ associe sa classe modulo $p$. Clairement, $\phi$
est un homomorphisme de groupe. Notons $H$ le {\em noyau}
de $\phi$, c'est-\`a-dire l'ensemble de $x\in G$ tels
que $\phi(x)=e$. C'est clairement un sous-groupe.

{\em Seconde \'etape : L'\'el\'ement $1+p$ est un g\'en\'erateur
de $H$. En particulier, il est d'ordre $p^{k-1}$.}
Clairement, $H$ est form\'e 
des \'el\'ements $1+x$ o\`u $x$ est divisible par $p$
(dans $\Z/p^k\Z$). Donc $H$ est d'ordre $p^{k-1}$. 
L'\'el\'ement $1+p$ appartient \`a $H$. Son ordre est donc
une puissance de $p$. D'apr\`es la premi\`ere partie 
c'est $p^{k-1}$. 

{\em Troisi\`eme \'etape : construction d'un \'el\'ement d'ordre
$p-1$.} Soit $x_0$ un g\'en\'erateur de $(\Z/p\Z)^*$ et
$x_1\in G$ un \'el\'ement tel que $\phi(x_1)=x_0$. Si on
a $x_1^k=e$ alors on a $\phi(x_1)^k=e$ et l'ordre de $x_1$
est donc un multiple de l'ordre de $x_0$. Par cons\'equent,
l'ordre de $x_1$ est de la forme $(p-1)\, p^l$ pour un 
$l\in \N$. Posons $x=x_1^{p^l}$. Alors $x$ est d'ordre $p-1$
d'apr\`es le lemme \ref{calcul-des-ordres}.

{\em Quatri\`eme \'etape : l'affirmation.} Avec les notations
introduites ci-dessus, consid\'erons l'\'el\'ement $x\, (1+p)$.
Il est d'ordre $(p-1)\,p^{k-1}$ d'apr\`es le lemme ci-dessous.

b) {\em Premi\`ere \'etape : pour $e\geq 0$, nous
avons
\[
5^{(2^e)} \equiv 1+ 2^{e+2} \; (2^{e+3}).
\]
} 
Proc\'edons par r\'ecurrence. Pour $e=0$, l'affirmation est
trivialement vraie. Supposons-la d\'emontr\'ee pour $e$.
Alors nous avons
\begin{eqnarray*}
5^{(2^{e+1})} & = & (1+2^{e+2}(1+2\,x))^2 \\
              & = & 1 + 2\times 2^{e+2}(1+2\,x) + 2^{2\,e+4}(1+2\,x)^2.
\end{eqnarray*}
Si nous r\'eduisons modulo $2^{e+4}$, nous trouvons bien $1+2^{e+3}$.


Notons $\phi: (\Z/2^k\Z)^* \ra (\Z/4\Z)^*$ l'application
qui \`a $x$ associe sa classe modulo $4$. Clairement, $\phi$
est un homomorphisme de groupe. Notons $H$ le {\em noyau}
de $\phi$, c'est-\`a-dire l'ensemble de $x\in G$ tels
que $\phi(x)=e$. C'est clairement un sous-groupe.

{\em Seconde \'etape : L'\'el\'ement $5$ est un g\'en\'erateur
de $H$. En particulier, il est d'ordre $2^{k-2}$.}
Clairement, $H$ est form\'e 
des \'el\'ements $1+x$ o\`u $x$ est divisible par $4$
(dans $\Z/2^k\Z$). Donc $H$ est d'ordre $2^{k-2}$. 
L'\'el\'ement $5$ appartient \`a $H$. Son ordre est donc
une puissance de $2$. D'apr\`es la premi\`ere partie 
c'est $2^{k-2}$. 

{\em Troisi\`eme \'etape : l'affirmation.} 
Consid\'erons l'application
\[
f: \Z/2\Z \times \Z/2^{k-2}\Z \ra (\Z/2^k\Z)^* \ko
(\ol{a},\ol{b}) \mapsto (-1)^a\,5^b.
\]
On v\'erifie ais\'ement que c'est un homomorphisme de
groupe. En outre, $f$ est surjectif (quel que soit $x\in G$,
on a $x\in H$ ou $-x\in H$). Comme les deux
groupes sont d'ordre $2^{k-1}$, il s'ensuit que
$f$ est bijectif. Donc $f$ est un isomorphisme. 

\end{demonstration}

\begin{lemme} \label{ordre-du-produit}
Soit $G$ un groupe not\'e multiplicativement
et soient $g,h$ deux \'el\'ements d'ordre fini $a,b$ de $G$ tels que
$gh=hg$ et $a$, $b$ sont premiers entre eux. Alors $gh$ est
d'ordre $ab$.
\end{lemme}

\begin{demonstration} En effet, pour $k\in\Z$, nous avons
$(gh)^k=g^k\,h^k=e$ si et seulement si $g^k=h^{-k}$. 
L'ordre de l'\'el\'ement $g^k=h^{-k}$ est donc un diviseur
commun \`a $\ord g$ et $\ord h$. Comme ces nombres sont
premiers entre eux, l'ordre de $g^k=h^{-k}$ est \'egal \`a 
$1$ et $g^k=h^{-k}=e$. Cela
veut dire que $k$ est multiple de $a$ et de $-b$. Puisque
les deux sont premiers entre eux, $k$ doit \^etre 
multiple du produit $ab$. R\'eciproquement, nous avons
$(gh)^{ab}= (g^a)^b \, (h^b)^a=e$.
\end{demonstration}

\begin{remarque} En combinaison avec le lemme chinois, le
th\'eor\`eme \ref{structure-inversibles-p-puissance} permet
de d\'eterminer la structure du groupe $(\Z/n\Z)^*$ pour tout
entier $n$ dont on conna\^{\i}t la d\'ecomposition en produit
de facteurs premiers. Par exemple, consid\'erons 
$n=3\times 5^3\times 7^2$. Alors, par le th\'eor\`eme chinois,
nous avons un isomorphisme 
\[
(\Z/n\Z)^* \iso (\Z/3\Z)^* \times (\Z/5^3\Z)^* \times (\Z/7^2\Z)^*.
\]
Le th\'eor\`eme \ref{structure-inversibles-p-puissance} donne
des isomorphismes $(\Z/3\Z)^*\iso \Z/2\Z$, 
$(\Z/5^3\Z)\iso \Z/100\Z$, $\Z/7^2\Z\iso \Z/42\Z$. Donc
on a 
\[
(\Z/n\Z)^* \iso \Z/2\Z \times \Z/100\Z \times \Z/42\Z.
\]
Cela montre par exemple que le nombre de solutions de l'\'equation
$x^4=1$ dans $\Z/n\Z$ est \'egal \`a $2\times 4\times 2=16$.
Nous laissons au lecteur le soin de calculer
explicitement ces 16 solutions.
\end{remarque}












%\input{arith17}
\newpage
\Absatz{L'indicatrice de Carmichael}

\begin{definition} Soit $n$ un entier $\geq 2$. On d\'efinit 
$\lambda(n)$ comme le maximum des ordres des \'el\'ements
du groupe $(\Z/n\Z)^*$. On appelle {\em indicatrice de Carmichael}
l'expression $\lambda(n)$. 
\end{definition}

\begin{exemple} Si $p$ est premier, on a $\lambda(p)=\phi(p)=p-1$
car le groupe $(\Z/p\Z)^*$ est cyclique d'ordre $p-1$. 
\end{exemple}

\begin{lemme}[Th\'eor\`eme de Carmichael] 
On a $a^{\lambda(n)}\equiv 1\; (n)$ pour tout entier
$a$ premier \`a $n$. R\'eciproquement, si $m$ v\'erifie $a^m\equiv 1\;(n)$
pour tout entier $a$ premier \`a $n$, alors $m$ est multiple de $\lambda(n)$.
\end{lemme}

\begin{demonstration} Soit $a\in(\Z/n\Z)^*$ un \'el\'ement d'ordre 
$u=\lambda(n)$ et $b\in(\Z/n\Z)^*$ un \'el\'ement d'ordre $v$.
Nous allons montrer que $(\Z/n\Z)^*$ contient un \'el\'ement
dont l'ordre est $\ppcm(u,v)$. Il s'ensuivra que $\lambda(n)=\ppcm(u,v)$
et donc que $v$ divise $\lambda(n)$. 

Pour cela, \'ecrivons $\ppcm(u,v)=u'v'$, o\`u $u'$ divise $u$,
$v'$ divise $v$ et $u'$, $v'$ sont premiers entre eux. Alors
$a^{u/u'}$ est d'ordre $u'$, $b^{v/v'}$ est d'ordre $v'$ et
donc leur produit est d'ordre $u'v'=\ppcm(u,v)$ d'apr\`es le
lemme \ref{ordre-du-produit}. 

La deuxi\`eme affirmation est claire.
\end{demonstration}

\begin{lemme} 
\begin{itemize}
\item[a)] On a $\lambda(2)=1$, $\lambda(4)=2$ et $\lambda(2^k)=2^{k-2}$
pour tout $k\geq 3$. 
\item[b)] Si $p$ est un nombre premier impair, on a $\lambda(p^k)= \phi(p^k)=
(p-1)p^{k-1}$. 
\item[c)] Si $n=rs$ o\`u $r$ et $s$ sont premiers entre eux, on a
$\lambda(n)=\ppcm(\lambda(r),\lambda(s))$.
\end{itemize}
\end{lemme}

\begin{remarque} Ce lemme permet de calculer l'indicatrice de 
Carmichael de tout nombre dont on conna\^{\i}t la d\'ecomposition
en facteurs premiers. Par exemple, on a
\[
\lambda(561)= \lambda(3\times 11\times 17) = \ppcm(2, 10, 16 )= 80.
\]
En particulier, comme $80$ divise $560$, nous avons
\[
a^{560}\equiv 1 \; (561)
\]
pour tout $a$ premier \`a 561 (comme dans le petit th\'eor\`eme
de Fermat). Un nombre $n$ tel que $a^{n-1} \equiv 1\;(n)$ pour tout
entier $a$ premier \`a $p$ s'appelle un {\em nombre de Carmichael}.
Voici le tableau des premiers $17$ nombres de Carmichael non premiers.
\begin{center}
\begin{tabular}{|r|r|r|r|} \hline
\multicolumn{1}{|c|}{ $i$} & 
\multicolumn{1}{c|}{ $n$} & 
\multicolumn{1}{c|}{d\'ecomposition} & 
\multicolumn{1}{c|}{ $\lambda(n)$} \\ \hline 
$1$ & $561$ & $3\times11\times17$  & $80$ \\
$2$ & $1105$ & $5\times13\times17$  & $48$ \\
$3$ & $1729$ & $7\times13\times19$  & $36$ \\
$4$ & $2465$ & $5\times17\times29$  & $112$ \\
$5$ & $2821$ & $7\times13\times31$  & $60$ \\
$6$ & $6601$ & $7\times23\times41$  & $1320$ \\
$7$ & $8911$ & $7\times19\times67$  & $198$ \\
$8$ & $10585$ & $5\times29\times73$  & $504$ \\
$9$ & $15841$ & $7\times31\times73$  & $360$ \\
$10$ & $29341$ & $13\times37\times61$  & $180$ \\
$11$ & $41041$ & $7\times11\times13\times41$  & $120$ \\
$12$ & $46657$ & $13\times37\times97$  & $288$ \\
$13$ & $52633$ & $7\times73\times103$  & $1224$ \\
$14$ & $62745$ & $3\times5\times47\times89$  & $2024$ \\
$15$ & $63973$ & $7\times13\times19\times37$  & $36$ \\
$16$ & $75361$ & $11\times13\times17\times31$  & $240$ \\
$17$ & $101101$ & $7\times11\times13\times101$  & $300$ \\ \hline
\end{tabular}
\end{center}


\end{remarque}

\begin{demonstration} Les parties a) et b) r\'esultent du 
th\'eor\`eme \ref{structure-inversibles-p-puissance}. 
Pour c), nous avons l'isomorphisme de groupes
\[
(\Z/n\Z)^* \iso (\Z/r\Z)^* \times (\Z/s\Z)^*
\]
donn\'e par le lemme chinois. L'ordre d'un couple
$(a,b)\in(\Z/r\Z)^*\times(\Z/s\Z)^*$ est clairement \'egal 
au $\ppcm$ des ordres des deux composantes. Ceci implique
que l'ordre maximal d'un couple sera le $\ppcm$ des ordres
maximaux atteints dans chaque composante. 
\end{demonstration}



\Absatz{R\'esidus quadratiques}
\el\noindent
\begin{definition} Soit $n\geq 2$ un entier. Une classe
$a\in (\Z/n\Z)^*$ est un {\em r\'esidu quadratique} modulo $n$ si
$a= b^2$ pour une classe $b$. Dans le cas
contraire, la classe $a$ est un {\em non-r\'esidu quadratique}.
\end{definition}

\begin{Exemples} Dressons les listes des r\'esidus quadratiques
modulo quelques nombres premiers 
\begin{eqnarray*}
2 & : & 1 \\
3 & : & 1 \\
5 & : & 1, 4 \\
7 & : & 1, 2, 4 \\
11 & : & 1,3,4,5,9 \\
13 & : & 1,3,4,9,10,12 \\
17 & : & 1,2,4,8,9,13,15,16 \\
19 & : & 1,4,5,6,7,9,11,16,17 \\
23 & : & 1,2,3,4,6,8,9,12,13,16,18\\
29 & : & 1,4,5,6,7,9,13,16,20,22,23,24,25,28
\end{eqnarray*}
Notons qu'il y a $(p-1)/2$ r\'esidus quadratiques pour 
chacun de ces nombres premiers et que $-1$ est un r\'esidu
quadratique pour $5,13,29$.
\end{Exemples}


\begin{lemme} \label{lemme-prelim}
Soit $p=2\,l+1$ un nombre premier impair.
\begin{itemize}
\item[a)] Parmi les $2l$ \'el\'ements de $(\Z/p\Z)^*$ la
moiti\'e exactement sont des r\'esidus quadratiques.
\item[a)] Pour tout $a\in(\Z/p\Z)^*$ on a $a^l\equiv \pm 1\; (p)$. 
On $a^l\equiv 1\; (p)$ si et seulement si $a$ est un 
r\'esidu quadratique modulo $p$.
\item[b)] La classe de $-1$ est un r\'esidu quadratique modulo $p$ si
et seulement si $p\equiv 1\;(4)$.  
\end{itemize}
\end{lemme}

\begin{exemple} Le nombre $2011$ est premier et congru \`a $3$ modulo $4$.
Donc $-1$ n'est pas r\'esidu quadratique modulo $2011$. Par contre,
\`a l'aide de l'algorithme de calcul rapide 
des puissances, on v\'erifie ais\'ement que $1848^{1005} \equiv 1\; (2011)$.
Donc $1848$ est un r\'esidu quadratique modulo $2011$. 
\end{exemple}


\begin{demonstration} a) Nous savons que $(\Z/p\Z)^*$ est isomorphe
\`a $\Z/2l\Z$. Or ce dernier groupe contient exactement $l$ classes
multiples de $2$. 

b) Nous avons $(a^l)^2\equiv a^{p-1} \equiv 1\;(p)$
d'apr\`es le petit th\'eor\`eme de Fermat (\ref{fermat}). 
Donc $a^l \equiv \pm 1\;(p)$ (car l'\'equation $x^2=1$ admet
exactement $2$ solutions dans $\Z/p\Z$, d'apr\`es \ref{racines-liemes}).

Si $a=b^2$, 
alors $a^k=b^{2\,k}= b^{p-1}=1$ modulo $p$, par le petit
th\'eor\`eme de Fermat. R\'eciproquement, si
$a^l= 1$ modulo $p$, alors si $g$ est un g\'en\'erateur de 
$(\Z/p\Z)^*$, nous avons $a=g^{2\,k}$ pour un $k\in\Z$
d'apr\`es le lemme (\ref{racines-liemes}). Donc $a$
est un carr\'e. 

c) D'apr\`es a), la classe de $-1$ est un r\'esidu quadratique
ssi $(-1)^l \equiv 1\; (p)$, c'est-\`a-dire que $l$ est pair ou
encore que $p=2l+1$ v\'erifie $p\equiv 1\;(4)$.

\end{demonstration}




\begin{theoreme}[Conjecture d'Euler] Soit $a$ un entier non nul et
$p$ un nombre premier impair. Le fait que $a$ soit r\'esidu quadratique
modulo $p$ ou non ne d\'epend que de la classe de $p$ modulo $4a$.
\end{theoreme}

\begin{remarque} La conjecture, due \`a Euler, fut d\'emontr\'ee pour
la premi\`ere fois par C.~F.~Gauss en 1796 sous le nom de
`th\'eor\`eme d'or'. Nous allons donner la d\'emonstration
dans une section ult\'erieure.
\end{remarque}

\begin{Exemples} Nous avons d\'ej\`a vu que $-1$ est un 
carr\'e modulo $p$
si et seulement si $p$ est congru \`a $1$ modulo $4$, ou encore
modulo $-4=4(-1)$. 

D'apr\`es le th\'eor\`eme, le fait que $2$ soit un carr\'e modulo
$p$ ne d\'epend que de la classe de $p$ modulo $8$. Or $2$ est
non r\'esidu quadratique pour $3$ et $5$, il est r\'esidu quadratique 
pour $7$ ($4^2=2$) et pour $17$ ($6^2=2$). Donc {\em $2$ est un
carr\'e modulo $p$ ssi $p\equiv\pm 1 \;(8)$}.

Nous verrons plus tard que le calcul des classes de nombres premiers
$p$ modulo lesquels $a$ est un r\'esidu quadratique peut toujours
se ramener \`a $a=2$ et $a=-1$. 
\end{Exemples}



\Absatz{Le symbole de Legendre}

\begin{definition} Soit $p$ un nombre premier et
$a$ un entier. On pose
\[
\left(\frac{a}{p}\right) = \left\{
\begin{array}{cl} 0 & \mbox{si $p$ divise $a$} \\
1 & \mbox{si $a$ est r\'esidu quadratique modulo $p$} \\
-1 & \mbox{si $a$ est non \'residu quadratique modulo $p$}
\end{array}
\right.
\]
On appelle {\em symbole de Legendre} l'expression $\leg{a}{p}$.
\end{definition}

\begin{remarque} Par d\'efinition, le symbole de Legendre $\leg{a}{p}$
ne d\'epend que de la classe de $a$ modulo $p$. 

Pour un nombre premier impair, onn a $\leg{-1}{p}=1$ ssi $p$ 
est congru \`a $1$ modulo $4$ et $\leg{2}{p}=1$ ssi $p$ est congru
\`a $\pm 1$ modulo $8$. Si on tient \`a des formules explicites, on peut \'ecrire
\[
\leg{-1}{p}= (-1)^{\frac{p-1}{2}} \quad \leg{2}{p}= (-1)^{\frac{p^2-1}{8}}.
\]
\end{remarque}

\begin{lemme} \label{lemme-trivial}
Soit $p=2\,l+1$ un nombre premier impair.
\begin{itemize}
\item[a)] On a $\leg{a}{p}\equiv (-1)^l \; (p)$.
\item[b)] On a $\leg{ab}{p}= \leg{a}{p} \leg{b}{p}$ pour tous entiers $a,b$ et
$\leg{a^2\, b}{p}=\leg{b}{p}$ si $a$ n'est pas divisible par $p$.
\end{itemize}
\end{lemme}


\begin{demonstration} a) r\'esulte du lemme \ref{lemme-prelim} a) et b) de a).
\end{demonstration}

\begin{definition} Pour deux entiers $a$, $b$, on pose
\[
\theta(a,b)=\left\{
\begin{array}{cl} -1 & \mbox{si $a\equiv 3\;(4)$ et $b\equiv 3\;(4)$} \\
1 & \mbox{sinon}
\end{array}
\right.
\]
\end{definition}

\begin{remarque} On peut v\'erifier ais\'ement que pour $a$ et $b$ impairs, on a 
\[
\theta(a,b)= (-1)^{\frac{a-1}{2} \frac{b-1}{2}}.
\]
\end{remarque}

\begin{theoreme}[Loi de r\'eciprocit\'e quadratique] 
Si $p$ et $q$ sont deux nombres premiers impairs distincts, on a
\[
\leg{p}{q} \leg{q}{p}= \theta(p,q).
\]
\end{theoreme}

\begin{remarque} Le th\'eor\`eme est \'equivalent \`a la 
conjecture d'Euler.
Il signifie que $\leg{p}{q}=\leg{q}{p}$ si $p$ ou $q$ est congru \`a
$1$ modulo $4$, et $\leg{p}{q}=-\leg{q}{p}$ dans le cas contraire.
\end{remarque}

\begin{demonstration}
On a toujours $p-q=4a$ ou $p+q=4a$ pour un $a\in \Z$. Supposons d'abord que
$p-q=4a$. Alors on a
\[
\leg{p}{q}=\leg{q+4a}{q}= \leg{4a}{q}=\leg{a}{q}.
\]
o\`u nous avons utilis\'e le lemme \ref{lemme-trivial}. De l'autre c\^ot\'e,
nous avons
\[
\leg{q}{p}=\leg{p-4a}{p}=\leg{-4a}{p}=\leg{-1}{p} \leg{a}{p}.
\]
Or, d'apr\`es la conjecture d'Euler, nous avons $\leg{a}{p}=\leg{a}{q}$.
Puisque $p$ et $q$ ont m\^eme reste par $4$, il s'ensuit que $\theta(p,q)=\leg{-1}{p}$
ce qui termine la d\'emonstration dans ce cas.

Supposons maintenant que $p+q=4a$. Alors nous avons
\[
\leg{p}{q}=\leg{4a-q}{q}= \leg{4a}{q}= \leg{a}{q}
\]
et de m\^eme
\[
\leg{q}{p}=\leg{4a-p}{p}= \leg{4a}{p}= \leg{a}{p}.
\]
Donc d'apr\`es la conjecture d'Euler, nous avons $\leg{p}{q}=\leg{q}{p}$.
\end{demonstration}




\el\noindent
{\bf R\'esum\'e des propri\'et\'es du symbole de Legendre.\ }
{\em 
Les r\`egles suivantes permettent de calculer tout
symbole de Legendre ($p$ et $q$ sont des nombres premiers impairs
distincts; $a,a',b$ sont des entiers)
\begin{itemize} 
\item[(1)] Modularit\'e : 
\[
\leg{a}{p}=\leg{a'}{p}
\]
si $a \equiv a'\;(p)$.
\item[(2)] Multiplicativit\'e : 
\[
\leg{ab}{p}=\leg{a}{p}\leg{b}{p}.
\]
\item[(3)] R\'eciprocit\'e : 
\[
\leg{p}{q}= \left\{ 
\begin{array}{cl}
-\leg{q}{p} & \mbox{si $p\equiv 3\;(4)$ et $q\equiv 3\;(4)$} \\
\leg{q}{p}  & \mbox{sinon}
\end{array}
\right.
\]
\item[(4)] Valeurs particuli\`eres : 
\[
\leg{-1}{p}  =  \left\{ 
\begin{array}{cl} 
  1 & \mbox{si $p\equiv 1\;(4)$} \\
 -1 & \mbox{si $p\equiv 3\;(4)$}
\end{array} \right. \ko \quad\quad
\leg{2}{p}  =  \left\{
\begin{array}{cl} 1 & \mbox{si $p\equiv \pm 1\;(8)$} \\
                   -1 & \mbox{sinon}
\end{array} \right. .
\]
\end{itemize}
}



\begin{exemple} Nous montrons comment les r\`egles ci-dessus
permettent de calculer $\leg{541}{2011}$~:
\begin{eqnarray*}
\leg{541}{2011} & = & \leg{2011}{541} \quad
            \mbox{ (r\'eciprocit\'e, $541\equiv 1\;(4)$)}) \\
                & = & \leg{388}{541} \quad
            \mbox{(modularit\'e, $2011 \equiv 388\;(541)$)} \\
                & = & \leg{2}{541}^2 \,\leg{97}{541} \quad
            \mbox{(multiplicativit\'e, $388=2^2\times 97$)} \\
                & = & \leg{541}{97} \quad
            \mbox{(r\'eciprocit\'e, $541\equiv 1\;(4)$)} \\
                & = & \leg{56}{97} \quad
            \mbox{(modularit\'e, $541\equiv 56\;(97)$)} \\
                & = & \leg{7}{97}\,\leg{2}{97}^3 \quad
            \mbox{(multiplicativit\'e)} \\
                & = & \leg{97}{7}\,\leg{2}{97}^3 \quad
            \mbox{(\'reciprocit\'e, $97\equiv 1\;(4)$)} \\
                & = & \leg{-1}{7}\, \leg{2}{97}^3 \quad
            \mbox{(modularit\'e)} \\
                & = & -1 \quad
            \mbox{(valeurs particuli\`eres, $\leg{-1}{7}=-1$, 
                   $\leg{2}{97}= 1$)}
\end{eqnarray*}

\end{exemple}






%\input{arith18}
\Absatz{D\'emonstration de la conjecture d'Euler}

\begin{lemme} \label{lemme-cle}
Soit $p=2\,l+1$ un nombre premier impair et $a$ un
entier qui n'est pas divisible par $p$. Pour $1\leq k \leq l$,
soit $r_k$ le reste de la division de $ka$ par $p$ 
et soit $\nu$ le nombre de restes $r_k>l$. Alors 
\[
a^l \equiv (-1)^\nu \; (p)
\]
et en particulier, $a$ est un r\'esidu quadratique modulo $p$ si
et seulement si $\nu$ est pair.
\end{lemme}

\begin{demonstration} Si $a\,i\equiv \pm a\,j\;(p)$, alors
comme $a$ est inversible modulo $p$, nous avons $i\equiv \pm j\; (p)$
ce qui est impossible si $i$ et $j$ sont compris entre $1$ et $l$. 
Donc si nous posons 
\[
s_i=\left\{ 
\begin{array}{cc} 
r_i & \mbox{si $1 \leq r_i \leq l$} \\
p-r_i & \mbox{si $l < r_i$} 
\end{array}
\right.
\]
les $s_i$ sont deux \`a deux distincts et compris entre $1$ et $l$.
Puisque ils sont au nombre de $l$, tout entier entre $1$ et $l$
est \'egal \`a un $s_j$. Nous avons
\[
r_1 r_2 \cdots r_l \equiv (-1)^\nu s_1 s_2 \cdots s_l \equiv (-1)^\nu l\,! \; (p).
\]
De l'autre c\^ot\'e, nous avons
\[
r_1 r_2 \cdots r_l \equiv l\, !\, \, a^l\; (p).
\]
Puisque $l\,!$ est inversible modulo $p$, nous obtenons l'affirmation.
La derni\`ere partie r\'esulte du lemme pr\'ec\'edent.
\end{demonstration}

\begin{exemple} Prenons $p=11$ et donc $l=5$. Dans le dessin suivant, nous calculons
$\nu$ pour $a$ variant entre $-5$ et $5$. Par exemple, la ligne qui commence
par le nombre $2$ comporte $l=5$ points aux abscisses $2,4,6,8,10$.
Le nombre de points qui se trouvent dans des intervalles `sous-lign\'es'
est \'egal \`a $\nu$. Donc $\nu=3$ et $2$ est un non-r\'esidu quadratique
modulo $11$. Les r\'esidus quadratiques modulo 13 sont $-2,1,3,4,5$.


\setlength{\unitlength}{0.2cm}
\begin{center}
\begin{picture}(66,24)(0,-12)
\lin{0}{0}{1}{0}{66}
\multiput(0,-11)(11,0){7}{\line(0,1){22}}
\multiput(0,0.2)(22,0){3}{\line(1,0){11}}
\multiput(0,-0.2)(22,0){3}{\line(1,0){11}}
\multiput(13,2)(2,0){5}{\makebox(0,0)[t]{$\bullet$}}
\multiput(15,4)(4,0){5}{\makebox(0,0)[t]{$\bullet$}}
\multiput(17,6)(6,0){5}{\makebox(0,0)[t]{$\bullet$}}
\multiput(19,8)(8,0){5}{\makebox(0,0)[t]{$\bullet$}}
\multiput(21,10)(10,0){5}{\makebox(0,0)[t]{$\bullet$}}

\multiput(53,-2)(-2,0){5}{\makebox(0,0)[t]{$\bullet$}}
\multiput(51,-4)(-4,0){5}{\makebox(0,0)[t]{$\bullet$}}
\multiput(49,-6)(-6,0){5}{\makebox(0,0)[t]{$\bullet$}}
\multiput(47,-8)(-8,0){5}{\makebox(0,0)[t]{$\bullet$}}
\multiput(45,-10)(-10,0){5}{\makebox(0,0)[t]{$\bullet$}}

\lbtr{10.5}{-0.7}{-22}
\lbbl{11.5}{0.7}{0}

\lbtr{32.5}{-0.7}{-11}
\lbbl{33.5}{0.7}{11}

\lbtr{54.5}{-0.7}{0}
\lbbl{55.5}{0.7}{22}

\lbl{1}{2}{{1}}
\lbl{1}{4}{2}
\lbl{1}{6}{{3}}
\lbl{1}{8}{{4}}
\lbl{1}{10}{{5}}

\lbl{1}{-2}{-1}
\lbl{1}{-4}{{-2}}
\lbl{1}{-6}{-3}
\lbl{1}{-8}{-4}
\lbl{1}{-10}{-5}

\end{picture}
\end{center}
\end{exemple}

\begin{theoreme}[Conjecture d'Euler] Soit $a$ un entier non nul et
$p$ un nombre premier impair. Le fait que $a$ soit r\'esidu quadratique
modulo $p$ ou non ne d\'epend que de la classe de $p$ modulo $4a$.
\end{theoreme}


\begin{demonstration} D'apr\`es le lemme \ref{lemme-cle} et l'exemple
qui le suit, il s'agit de compter le nombre $\nu$ de points
$ka$, $1\leq k \leq l$, qui se trouvent dans l'un quelconque des intervalles
$I_i=[ip/2, (i+1)p/2]$, o\`u $i$ est impair et compris entre $1$ et
$a$. En effet, le dernier point, $la=(p-1) a/2$, se trouve dans 
l'intervalle $[(a-1)p/2, ap/2]$. Supposons que $p'=p+4a$ et que
$\nu'$ est le nombre de points correspondant (peu importe si $p'$
n'est pas premier). Alors le nombre d'intervalles $I'_i$
reste le m\^eme ($=a$), mais le nombre de points $ka$ augmente de
$l'-l=2a$. Je dis que chacun des $a$ intervalles $I'_i$
comporte $2$ points $ka$ de plus que l'intervalle $I_i$ 
correspondant. Ceci impliquera que $\nu'-\nu$ est pair et
donc que $(-1)^{\nu'}=(-1)^\nu$. Comparons en effet l'intervalle
$I_i$ \`a l'intervalle $I'_i$ : nous avons
\begin{eqnarray*}
I_i & = & [i\, \frac{p}{2}, (i+1)\, \frac{p}{2}] \\
I'_i & = & [i\, (\frac{p}{2}+2a), (i+1)\, (\frac{p}{2}+2a)] \\
     & = & [ i\, \frac{p}{2}+2ia, (i+1)\, \frac{p}{2}+2ia] 
\cup [ (i+1)\,\frac{p}{2}+2ia, (i+1)\,\frac{p}{2}+2ia+2a].
\end{eqnarray*}
L'intervalle $I'_i$ est donc obtenu \`a partir de $I_i$
par deux op\'erations : d\'ecalage de $2ia$ et rajout
d'un intervalle disjoint de longueur $2a$ dont les 
extr\'emit\'es ne sont pas multiples de $a$. Or le d\'ecalage
d'un multiple de $a$ laisse invariant le nombre de points
$ka$ contenus dans l'intervalle, et le rajout d'un intervalle
disjoint de longueur $2a$ dont les extr\'emit\'es ne sont
pas multiples de $a$ rajoute $2$ points $ka$ car tout
intervalle de longueur $2a$ dont les extr\'emit\'es ne sont
pas des multiples de $a$ comporte exactement $2$ points
$ka$ (par mise \`a l'\'echelle, on peut supposer
que $a=1$ : tout intervalle de longueur $2$ dont les
extr\'emit\'es ne sont pas enti\`eres comporte exactement $2$
points entiers.)
\end{demonstration}










\Absatz{Bibliographie}
\el\noindent
Les livres suivants peuvent servir \`a {\em approfondir} 
les connaissances sur certains sujets trait\'es  en cours. 
Le livre de Weiss \cite{weiss} est r\'edig\'e de fa\c{c}on 
\'el\'ementaire et son contenu est relativement proche de celui du cours.
Le livre de Gindikin \cite{gindikin} 
contient des biographies de math\'ematiciens
et physiciens de la renaissance \`a nos jours et donne des
explications \'el\'ementaires mais compl\`etes d'un grand
nombre de r\'esultats qu'ils ont obtenus. Le chapitre sur
Gauss est un tr\'esor de perles d'arithm\'etique. 
Le cours de Michel Demazure \cite{demazure} contient enti\`erement
le programme de ce cours et le d\'epasse de loin. Il s'adresse
\`a un public un peu plus avanc\'e. 
Le livre d'Artin \cite{artin} est tr\`es complet, 
bien r\'edig\'e et peut servir du DEUG jusqu'\`a la ma\^{\i}trise.

Les chiffres en gras se reportent \`a la biblioth\`eque
de Math\'ematiques du second cycle, Tour 56, rez de chauss\'ee.


\begin{thebibliography}{bbd}

\bibitem{koulikov} L.~Koulikov, {\em Alg\`ebre et th\'eorie des
nombres}, Chap. XI et XII, Moscou Ed. Mir, 1982. {\bf 10~KOU~82}.

\bibitem{cahen} Paul-Jean Cahen, Touibi Ch\'edly,
{\em Arithm\'etique et Alg\`ebre}, Scientifika, 1992.
{\bf 03.5~CAH~92}.

\bibitem{demazure} Michel Demazure, {\em Cours d'alg\`ebre},
Notes d'un cours \`a l'Ecole Polytechnique en Majeure Alg\`ebre
et Informatique, Polycopi\'e \`a para\^{\i}tre sous forme
de livre chez Cassini Editeurs.

\bibitem{faraut} Jacques Faraut, {\em Arithm\'etique : Cours, 
exercices et travaux pratiques sur micro-ordinateur},
Ellipse, 1990. {\bf 77.5~P~FAR~90}.

\bibitem{gindikin} Simon Gindikin, {\em Horloges, pendules
et m\'ecanique c\'eleste}, Diderot Editeur, 1995.

\bibitem{seroul} Raymond S\'eroul, {\em math--info, Informatique pour
math\'ematiciens, Chap.~2}, Inter\'editions, 1995. 

\bibitem{weiss}
Edwin Weiss, {\em A first course in algebra and number theory},
Academic Press, 1971. {\bf 10~WEI~71}.

\bibitem{childs} 
Lindsay Childs, {\em A concrete introduction to higher algebra},
Undergraduate texts in Mathematics, Springer, 1979. 
{\bf 10~CHI~79}.

\bibitem{artin} Michael Artin, {\em Algebra}, Prentice Hall, 1991.
{\bf 10~ART~91}.

\end{thebibliography}

\end{document}












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