Various clarifications and rewritings.

1 files changed, 143 insertions, 49 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index 6d0d3d2..bf9ca7a 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -393,7 +393,9 @@ d'entiers est défini, mais parfois surprenant (quel est le ppcm de
 tous les nombres premiers ?).
 
 Remarque : pour deux nombres, on a $\ppcm(m,m') \times \pgcd(m,m') =
-|mm'|$.
+|mm'|$ (ceci découle, en comparant les décompositions en facteurs
+premiers, du fait que $\min(u,v) + \max(u,v) = u+v$ pour tous
+$u,v\in\mathbb{N}$).
 
 %
 \subsection{Relation de Bézout}
@@ -507,8 +509,16 @@ Soit $m$ un entier fixé pour le moment :
 
 Si $x$ et $x'$ sont entiers, on dit que $x$ et $x'$ sont
 \textbf{congrus} modulo $m$, noté $x \equiv x' \pmod{m}$, lorsque
-$x-x'$ est multiple de $m$.  Relation réflexive, symétrique,
-transitive.
+$x-x'$ est multiple de $m$ (ou, si on préfère, $x \equiv x' \pmod{m}$
+signifie qu'il existe $k \in \mathbb{Z}$ tel que $x' = x + km$).
+Cette relation est réflexive (on a $x \equiv x \pmod{m}$), symétrique
+(si $x \equiv y \pmod{m}$ alors $y \equiv x \pmod{m}$) et transitive
+(si $x \equiv y \pmod{m}$ et $y \equiv z \pmod{m}$ alors $x \equiv z
+\pmod{m}$) --- on dit qu'il s'agit d'une \emph{relation
+  d'équivalence}.
+
+Lorsque $m$ est clair d'après le contexte, on écrit parfois simplement
+$x\equiv x'$ pour $x\equiv x'\pmod{m}$.
 
 Dire $x \equiv 0 \pmod{m}$ signifie simplement que $x$ est multiple
 de $m$.
@@ -519,17 +529,35 @@ variable : si $m|m'$ alors $x \equiv x' \pmod{m'}$ implique $x\equiv
 x' \pmod{m}$ (la congruence modulo $m'$ est \emph{plus fine} que
 modulo $m$).
 
-Représentants : si $m \geq 1$ alors chaque entier est congru
-modulo $m$ à l'un des nombres $0,1,2,\ldots,(m-1)$ (le reste de sa
-division euclidienne par $m$ !).
-
-Exemple de $\mathbb{Z}/2\mathbb{Z}$ avec pair=$\bar 0$ et impair=$\bar
-1$.
+La \emph{classe de congruence} modulo $m$ (ou : classe d'équivalence
+pour la congruence modulo $m$) d'un entier $x$ est l'ensemble $\{x +
+km \colon k\in\mathbb{Z}\}$ de tous les entiers congrus à $x$
+modulo $m$ (ce sont les valeurs d'une suite arithmétique de
+raison $m$).  On la note $(\bar x)_{\mathrm{mod}\,m}$ ou parfois
+simplement $\bar x$ si $m$ est clair dans le contexte.
 
-On veut définir $\mathbb{Z}/m\mathbb{Z} = \{\bar 0, \bar 1, \bar 2,
-\ldots, \overline{m-1}\}$ de façon analogue : pour ajouter $\bar x$ et
-$\bar y$, on consière $\bar x + \bar y = \overline{x+y}$ et $\bar x\,
-\bar y = \overline{xy}$.  Reste à savoir ce que la barre veut dire !
+Représentants : si $m \geq 1$ alors chaque entier est congru
+modulo $m$ à \emph{un et un seul} des nombres $0,1,2,\ldots,(m-1)$ (le
+reste de sa division euclidienne par $m$ !).  On dira que ce sont les
+\emph{représentants standards} des classes de congruence modulo $m$.
+
+Pour $m\geq 1$, il y a donc exactement $m$ classes de congruence
+modulo $m$ (à savoir $\bar 0, \bar 1,\ldots, \overline{m-1}$).  On
+notera $\mathbb{Z}/m\mathbb{Z}$ l'ensemble de ces classes (cf. plus
+bas).
+
+Exemple : $\mathbb{Z}/2\mathbb{Z}$ avec $\bar 0$ = classe des nombres
+pairs et $\bar 1$ = classe des nombres impairs.  Remarque : on peut
+savoir si $x+y$ ou $xy$ est pair ou impair en sachant si $x$ et $y$ le
+sont --- c'est la compatibilité aux opérations vue plus haut --- ce
+qui permet de définir une addition et une multiplication sur
+$\mathbb{Z}/2\mathbb{Z}$.
+
+On veut définir une addition et une multiplication
+$\mathbb{Z}/m\mathbb{Z} = \{\bar 0, \bar 1, \bar 2, \ldots,
+\overline{m-1}\}$ de façon analogue : pour ajouter $\bar x$ et $\bar
+y$, on consière $\bar x + \bar y = \overline{x+y}$ et $\bar x\, \bar y
+= \overline{xy}$.
 
 %
 \subsection{Généralité sur les quotients}
@@ -582,6 +610,12 @@ encore des choses tout à fait arbitraires).
 
 \medbreak
 
+Il faut bien comprendre que, si $x,y$ sont deux entiers, alors $\bar x
+= \bar y$ dans $\mathbb{Z}/m\mathbb{Z}$ signifie exactement la même
+chose que $x \equiv y \pmod{m}$.
+
+\medbreak
+
 Et si $m\leq 1$ ?
 \begin{itemize}
 \item On a $\mathbb{Z}/1\mathbb{Z} = \{\bar 0\}$, et les opérations
@@ -815,46 +849,96 @@ Contre-exemple : la multiplication sur les entiers (ou même sur les
 entiers non nuls) \emph{ne forme pas} un groupe, faute d'inverses pour
 les entiers autres que $\pm 1$.
 
+\smallbreak
+
 Généralement, un groupe est noté soit de façon multiplicative (on
 écrit $xy$ au lieu de $x\star y$ et $1$ au lieu de $e$, et dans ce cas
 on note $x^m$ l'élément $x\star x\star \cdots x$ avec $m$ fois $x$ et
 $x^{-1}$ le symétrique de $x$, alors appelé « inverse »), soit de
 façon additive (on écrit $x+y$ au lieu de $x\star y$ et $0$ au lieu
-de $e$, et dans ce cas on note $mx$ l'élément $x + x + + \cdots + x$
+de $e$, et dans ce cas on note $mx$ l'élément $x + x + \cdots + x$
 avec $m$ fois $x$, et $-x$ le symétrique de $x$, alors appelé
 « opposé »).  Très souvent on utilise une de ces deux notations de
-façon implicite.  La notation additive est en principe réservée aux
-groupes abéliens (mais on n'en rencontrera pas de non-abéliens dans ce
-cours).
+façon implicite.
 
-\smallbreak
+Attention : il ne faut pas s'imaginer qu'il existe une différence
+mathématique entre « groupes multiplicatifs » et « groupes
+  additifs » : un groupe est un groupe, il se trouve simplement que
+pour certains d'entre eux on a plutôt l'habitude de noter
+multiplicativement et pour certains plutôt additivement.  (La notation
+additive est en principe réservée aux groupes abéliens mais on n'en
+rencontrera pas de non-abéliens dans ce cours.)
+
+\medbreak
 
 Un \textbf{morphisme} de groupe $\psi\colon G \to G'$ est une
 application qui préserve la composition ($\psi(x\star y) = \psi(x)
-\star \psi(y)$), et du coupb forcément aussi l'élément neutre
-($\psi(e) = e$) et les symétriques (le symétrique de $\psi(x)$ est
-l'image du symétrique de $x$).  Un \textbf{isomorphisme} de groupes
-est un morphisme bijectif ; moralement : les groupes $G$ et $G'$ sont
-abstraitement « le même » (mais éventuellement notés ou étiquetés
-différemment).  Attention !  On aura souvent affaire, par exemple, à
-un morphisme entre un groupe noté additivement et un groupe noté
-multiplicativement : dans ce cas, cela signifie $\psi(x+y) =
-\psi(x)\,\psi(y)$.  Exemple : l'exponentielle (de base $e$, disons)
-constitue un isomorphisme entre le groupe additif des réels et le
-groupe multiplicatif des réels strictement positifs.
+\star \psi(y)$), et du coup forcément aussi l'élément neutre ($\psi(e)
+= e$) et les symétriques (le symétrique de $\psi(x)$ est l'image du
+symétrique de $x$).
+
+Un \textbf{isomorphisme} de groupes est un morphisme bijectif ;
+moralement : les groupes $G$ et $G'$ sont abstraitement « le même »
+(mais éventuellement notés ou étiquetés différemment).  Attention !
+On aura souvent affaire, par exemple, à un morphisme entre un groupe
+noté additivement et un groupe noté multiplicativement : dans ce cas,
+cela signifie $\psi(x+y) = \psi(x)\,\psi(y)$.  Exemple :
+l'exponentielle (de base $e$, disons) constitue un isomorphisme entre
+le groupe additif des réels et le groupe multiplicatif des réels
+strictement positifs.
+
+De façon générale, si $g$ est un élément d'un groupe $G$, on a un
+morphisme de groupes $\psi \colon \mathbb{Z} \to G$ défini par
+$\psi(i) = g^i$ en notation multiplicative (ou, ce qui revient au même
+en notation additive : $\psi(i) = i g$).  L'\emph{image} de ce
+morphisme, c'est-à-dire l'ensemble de tous les $\psi(i)$ pour $i$
+parcourant $\mathbb{Z}$, s'appelle le \emph{sous-groupe engendré
+  par $g$ dans $G$} (cf. plus bas).
+
+Si on a $g^m = 1$ (on va voir que ceci signifie que $m$ est un
+multiple de l'ordre de $g$, cf. plus bas), alors le morphisme $\psi
+\colon \mathbb{Z} \to G, i \mapsto g^i$ défini ci-dessus vérifie :
+$\psi(i) = \psi(j)$ si $i \equiv j\pmod{m}$ (en effet, $j = i+km$ pour
+un certain $k \in \mathbb{Z}$, donc $g^j = g^i \cdot (g^m)^k = g^i$) ;
+par conséquent, on peut définir un nouveau morphisme de groupes
+$\bar\psi \colon \mathbb{Z}/m\mathbb{Z} \to G$ qui envoie $\bar\imath
+\in \mathbb{Z}/m\mathbb{Z}$ sur $g^i \in G$.  On peut donc faire comme
+si on pouvait élever $g$ à une puissance dans
+$\mathbb{Z}/m\mathbb{Z}$.  Ce morphisme sera extrêmement important
+dans la suite.
+
+\medbreak
 
 L'\textbf{ordre d'un groupe} est simplement son cardinal, lorsque
-celui-ci est fini.  L'\textbf{ordre d'un élément} $g$ dans un groupe
-fini est le plus petit $m\geq 1$ tel que $g^m = 1$ (en notation
-multiplicative ; en notation additive, cela s'écrirait : $mg = 0$,
-i.e., un multiple de $g$) ; c'est aussi le nombre de puissances
-distinctes (en notation additive : de multiples distincts) de
-l'élément $g$.  Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi
-$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$, et donc $g^i
-= g^j$ si $i \equiv j \pmod{m}$.
-
-Attention : le fait d'avoir $g^m = 1$ signifie (exactement) que
-l'ordre de $g$ \emph{divise} $m$, pas forcément qu'il est égal à $m$.
+celui-ci est fini.
+
+L'\textbf{ordre d'un élément} $g$ dans un groupe fini est le plus
+petit $m\geq 1$ tel que $g^m = 1$ (en notation multiplicative ; en
+notation additive, cela s'écrirait : $mg = 0$).  Autrement dit, c'est
+le plus petit $m$ tel qu'en composant $m$ fois l'élément $g$ on
+retombe sur l'élément neutre.
+
+Si $m$ est l'ordre de $g$, alors le morphisme $\bar\psi \colon
+\mathbb{Z}/m\mathbb{Z} \to G$ est \emph{injectif}, c'est-à-dire que
+les $\bar\psi(\bar\imath)$ sont tous distincts quand $\bar\imath$
+parcourt $\mathbb{Z}/m\mathbb{Z}$ (en effet, si $\bar\psi(\bar\imath)
+= \bar\psi(\bar\jmath)$ avec $\bar\imath\neq\bar\jmath$, on peut
+supposer $0 \leq i < j < m$ et alors $g^{j-i} = 1$, ce qui contredit
+la minimalité de $m$).  Autrement dit, $\bar\psi$ définit un
+isomorphisme entre $\mathbb{Z}/m\mathbb{Z}$ et le groupe $\{g^i \colon
+i\in \mathbb{Z}\}$ des puissances de $g$.
+
+En particulier, l'ordre d'un élément $g$ est le nombre $\#\{g^i \colon
+i\in \mathbb{Z}\}$ de puissances distinctes de cet élément.
+
+Par ailleurs, si on a $g^n = 1$, cela signifie que l'ordre de $g$
+\emph{divise} $n$ (en effet, $\bar\psi(\bar n)=\bar\psi(\bar 0)$
+signifie $\bar n=\bar 0$ dans $\mathbb{Z}/m\mathbb{Z}$ où $m$ est
+l'ordre de $g$, c'est-à-dire que $n$ est \emph{multiple} de $m$).  Il
+y a donc équivalence entre : $g^n = 1$ et $n$ est multiple de l'ordre
+de $g$.
+
+\medbreak
 
 Un \textbf{sous-groupe} $H$ d'un groupe $G$ est un sous-ensemble de
 $G$ qui est lui-même un groupe pour la même opération et le même
@@ -869,12 +953,14 @@ Le sous-groupe engendré par une partie $E$ d'un groupe $G$ est le plus
 petit sous-groupe contenant $E$ (c'est-à-dire l'intersection de tous
 les sous-groupes de $G$ contenant $E$).  On utilisera cette notion
 seulement dans le cas suivant : le \emph{sous-groupe engendré par un
-  unique élément} $g$ de $G$ : c'est l'ensemble des puissances de $g$
-(en notation additive : multiples).  L'ordre $m$ de ce sous-groupe est
-l'ordre de $g$.  Ce sous-groupe est isomorphe à
-$\mathbb{Z}/m\mathbb{Z}$, avec $\bar k \mapsto g^k$.
+  unique élément} $g$ de $G$ : c'est l'ensemble $\{g^i \colon i\in
+\mathbb{Z}\}$ des puissances de $g$.  Comme on l'a vu ci-dessus,
+l'ordre $m = \#\{g^i \colon i\in \mathbb{Z}\}$ de ce sous-groupe est
+égal à l'ordre de $g$ (ce qui justifie le fait d'utiliser le même mot
+« ordre » pour les deux notions), et ce sous-groupe est isomorphe à
+$\mathbb{Z}/m\mathbb{Z}$, par l'isomorphisme $\bar\imath \mapsto g^i$.
 
-\smallbreak
+\medbreak
 
 \textbf{Théorème de Lagrange :} Dans un groupe fini, l'ordre de tout
 sous-groupe divise l'ordre du groupe.  En particulier, l'ordre d'un
@@ -894,13 +980,18 @@ si et seulement si l'ordre de $g$ est égal à l'ordre de $G$.
 
 Le groupe \emph{additif} $\mathbb{Z}/m\mathbb{Z}$ est cyclique, avec
 pour générateur $1$ (mais ce n'est pas le seul possible !
-cf. ci-dessous).  Réciproquement, tout groupe cyclique est isomorphe à
-$\mathbb{Z}/m\mathbb{Z}$, avec $m$ l'ordre d'un générateur $g$ (qui
-est donc aussi l'ordre du groupe et ne dépend pas du générateur).
+cf. ci-dessous).  Réciproquement, on a vu que tout groupe cyclique est
+isomorphe à $\mathbb{Z}/m\mathbb{Z}$, avec $m$ l'ordre d'un
+générateur $g$ (qui est donc aussi l'ordre du groupe et ne dépend pas
+du générateur), l'isomorphisme $\mathbb{Z}/m\mathbb{Z} \to G$ étant
+donné par $\bar\imath \mapsto g^i$.
+
 D'où une autre définition possible : un groupe cyclique $G$ [de
   générateur $g$] est un groupe isomorphe à $\mathbb{Z}/m\mathbb{Z}$
 [avec $1$ correspondant à $g$].
 
+\smallbreak
+
 Quels sont tous les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme
 groupe additif !) ?  Réponse : ce sont précisément les classes modulo
 $m$ des entiers premiers à $m$, c'est-à-dire les inversibles de
@@ -944,7 +1035,10 @@ question de savoir s'il y en a).  Il ne faut pas confondre !
 \medbreak
 
 De façon générale, l'ordre additif de $\bar a$ dans
-$\mathbb{Z}/m\mathbb{Z}$ vaut exactement $m/\pgcd(a,m)$.
+$\mathbb{Z}/m\mathbb{Z}$ vaut exactement $m/\pgcd(a,m)$.  (Et
+réciproquement, les éléments de $\mathbb{Z}/m\mathbb{Z}$ dont l'ordre
+divise $d$, pour $d$ un diviseur de $m$, sont les [classes des]
+multiples de $m/d$.)
 
 %
 \subsection{Théorème d'Euler}