From f41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4 Mon Sep 17 00:00:00 2001 From: david Date: Wed, 21 Oct 2009 18:17:11 +0000 Subject: Rework the part on Z/mZ. --- rappels-maths.tex | 131 ++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 83 insertions(+), 48 deletions(-) diff --git a/rappels-maths.tex b/rappels-maths.tex index 24ecd17..67fbb30 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -41,7 +41,7 @@ \maketitle {\footnotesize \begin{center} -CVS: \verb=$Id: rappels-maths.tex,v 1.15 2009-10-21 17:53:44 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.16 2009-10-21 18:17:11 david Exp $= \end{center} \par} \pretolerance=10000 @@ -728,20 +728,75 @@ conna % \subsection{Notions de théorie des groupes} -Rappel de la définition d'un groupe (notations multiplicative, -additive). Morphisme, isomorphisme de groupes. +Un \textbf{groupe} est un ensemble $G$ muni d'une opération binaire +$\star$ (c'est-à-dire une application $G\times G \to G$ dont on note +$g \star g'$ l'image d'un couple $(g,g')$) et d'un élément remarquable +$e$ tels que : +\begin{itemize} +\item Associativité de $\star$ : $x\star(y\star z) = (x\star y)\star z$ +\item Neutralité de $e$ pour $\star$ : $e\star x = x\star e = x$ +\item Existence d'inverses : pour chaque $x$, il existe un élément + noté $x'$ tel que) $x \star x' = x' \star x = e$ +\end{itemize} +Lorsque de plus la loi $\star$ est commutative ($y\star x = x\star +y$), on parle de \emph{groupe abélien} (ou commutatif). + +Exemples : l'addition sur les nombres réels (la loi $\star$ étant +l'addition et le neutre $e$ étant le nombre $0$) ; la multiplication +sur les nombres réels non nuls (la loi $\star$ étant la multiplication +et le neutre $e$ étant le nombre $1$) ; la composition des isométries +du plan (la loi $\star$ étant la composition et le neutre $e$ étant +l'identité). + +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}$ l'inverse de $x$), 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$ avec $m$ fois $x$, et $-x$ l'inverse, +alors appelé opposé, de $x$). 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). + +\smallbreak -Ordre d'un groupe = son cardinal. Ordre d'un élément $g$ dans un -groupe = le plus petit $m\geq 1$ tel que $g^m = 1$ (en notation +Un \textbf{morphisme} de groupe $\psi\colon G \to G'$ est une +application qui préserve la composition ($\psi(xy) = \psi(x)\, +\psi(y)$, le groupe étant noté multiplicativement), et du coup +forcément aussi l'élément neutre ($\psi(1) = 1$). 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). + +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$). +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$. Évidemment, si $g$ est d'ordre $m$, on a $g^m = 1$ +mais aussi $g^{m'} = 1$ pour tout multiple de $m$ ! + +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 +élément neutre ; c'est-à-dire, c'est une partie $H$ de $G$ telle que +$1 \in H$ et que $x,y \in H \limp xy \in H$ et que $x \in H \limp +x^{-1} \in H$ (cette dernière partie étant d'ailleurs automatique si +le groupe $G$ est fini). (Exemple : pour la multiplication, les +nombres réels strictement positifs forment un sous-groupe du groupe +des nombres réels non nuls.) + +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$. -Notion de sous-groupe. Sous-groupe engendré par une partie = plus -petit sous-groupe la contenant. Sous-groupe engendré par un -élément $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 1 \mapsto g$. +\smallbreak \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 @@ -769,10 +824,9 @@ D'o Les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme groupe additif !) sont précisément les inversibles de $\mathbb{Z}/m\mathbb{Z}$ (comme -anneau !). Démonstration... Attention ! on parlera aussi, plus loin, -des générateurs du groupe \emph{multiplicatif} -$(\mathbb{Z}/m\mathbb{Z})^\times$ (et de la question de savoir s'il y -en a). +anneau !). Attention ! on parlera aussi, plus loin, des générateurs +du groupe \emph{multiplicatif} $(\mathbb{Z}/m\mathbb{Z})^\times$ (et +de la question de savoir s'il y en a). Moralité : $\varphi(m)$ est aussi le nombre d'éléments d'un groupe cyclique (quelconque) d'ordre $m$ qui en sont un générateur. @@ -799,9 +853,19 @@ et dans $(\mathbb{Z}/7\mathbb{Z})^\times$ $2\times 2\times 2 = 1$ dans $(\mathbb{Z}/7\mathbb{Z})^\times$ et qu'on ne trouve pas $1$ avant). -Cas particulier : « petit théorème de Fermat » : si $p$ est premier, -alors $a^{p-1} \equiv 1 \pmod{p}$ lorsque $a$ n'est pas multiple -de $p$ ; donc, pour tout entier $a$ on a +Pour que l'ordre multiplicatif d'un élément $x$ dans +$\mathbb{Z}/m\mathbb{Z}$ soit défini, il faut (et il suffit) que cet +élément $x$ soit dans $(\mathbb{Z}/m\mathbb{Z})^\times$ (car c'est lui +le groupe multiplicatif), et dans ce cas l'ordre additif vaut +forcément $m$ car $x$ est un générateur du groupe cyclique +$\mathbb{Z}/m\mathbb{Z}$. + +\smallbreak + +Cas particulier du théorème d'Euler : le « petit théorème de + Fermat » : si $p$ est premier, alors $a^{p-1} \equiv 1 \pmod{p}$ +lorsque $a$ n'est pas multiple de $p$ ; donc, pour tout entier $a$ on +a \[ a^p \equiv a \pmod{p} \] @@ -859,35 +923,6 @@ cyclique (auquel cas ses g maximal possible d'un élément est $2^{r-2}$). \end{itemize} -% -\subsection{Exercices} - -\thingy Que vaut $10^{1000}$ modulo $7$ ? (Réponse : $4$.) Que vaut -$10^{1000}$ modulo $6$ ? (Réponse : $4$.) Que vaut $10^{10^{1000}}$ -modulo $7$ ? (Réponse : toujours $4$.) - -\thingy Quels sont les deux derniers chiffres (en base $10$) de -$2^{1000!}$ ? - -\thingy Montrer que pour tout $a\in \mathbb{Z}$ on a $a^{1729} \equiv -a \pmod{1729}$ (indication : $1729 = 7\times 13 \times 19$ ; utiliser -le théorème chinois). - -\thingy À quoi est isomorphe le groupe -$(\mathbb{Z}/56\mathbb{Z})^\times$ ? Quel est le plus grand ordre -possible d'un élément de ce groupe ? - -\thingy \textbf{Théorème de Wilson :} $p$ est premier si, et seulement -si, $(p-1)! \equiv -1 \pmod{p}$. - -\thingy \textbf{Théorème de Wolstenholme :} si $p\geq 5$ est premier, -le numérateur de -$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$ est -divisible par $p^2$. (Indications : on pourra regrouper $\frac{1}{k}$ -et $\frac{1}{p-k}$, diviser par $p$, et chercher à étudier une -congruence modulo $p$ ; on pourra faire usage du fait que -$1^2+2^2+3^2+\cdots+(p-1)^2 = \frac{1}{6}p(p-1)(2p-1)$.) - % \section{Polynômes} -- cgit v1.2.3