summaryrefslogtreecommitdiffstats
path: root/rappels-maths.tex
diff options
context:
space:
mode:
authordavid <david>2009-10-21 18:17:11 +0000
committerdavid <david>2009-10-21 18:17:11 +0000
commitf41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4 (patch)
treebe724493cca8d705b2ea0faf80d3294b73938c84 /rappels-maths.tex
parent1d04040b93484b109e83dff407026b7428624e2d (diff)
downloadinfmdi720-f41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4.tar.gz
infmdi720-f41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4.tar.bz2
infmdi720-f41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4.zip
Rework the part on Z/mZ.
Diffstat (limited to 'rappels-maths.tex')
-rw-r--r--rappels-maths.tex131
1 files 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ître la d.f.p.).
%
\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ù une autre définition possible : un groupe cyclique $G$ [de
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$ ? (réponse : $3$ car
$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}
\]
@@ -860,35 +924,6 @@ cyclique (auquel cas ses générateurs s'appellent éléments
\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}
\subsection{Définition, structure d'anneau et degré}