diff options
| -rw-r--r-- | rappels-maths.tex | 192 |
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} |