More about Z/mZ.

1 files changed, 136 insertions, 1 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index 5c06c59..13cb112 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -40,7 +40,7 @@
 \maketitle
 {\footnotesize
 \begin{center}
-CVS: \verb=$Id: rappels-maths.tex,v 1.3 2008-09-30 21:58:17 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.4 2008-10-07 10:04:22 david Exp $=
 \end{center}
 \par}
 \pretolerance=10000
@@ -653,6 +653,141 @@ où $p$ parcourt les premiers divisant $n$.
 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.
+
+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
+multiplicative ; en notation additive, cela s'écrirait : $mg = 0$,
+i.e., un multiple de $g$).
+
+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$.
+
+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
+élément divise l'ordre du groupe : si $G$ est un groupe fini et $g \in
+G$ alors $g^{\#G} = 1$.
+
+%
+\subsection{Groupes cycliques}
+
+On dit qu'un groupe fini $G$ est \textbf{cyclique} lorsqu'il existe un
+élément $g$ (appelé \emph{générateur} de $G$) tel que tout élément de
+$G$ soit de la forme $g^k$ (une puissance de $g$, en notation
+multiplicative ; en notation additive, cela s'écrirait : $kg$, i.e.,
+un multiple de $g$), autrement dit : le sous-groupe engendré par $g$
+est $G$ tout entier.
+
+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).
+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$].
+
+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).
+
+Moralité : $\varphi(m)$ est aussi le nombre d'éléments d'un groupe
+cyclique (quelconque) d'ordre $m$ qui en sont générateur.
+
+%
+\subsection{Théorème d'Euler}
+
+Si $m$ est un entier naturel non nul et $a$ un entier premier à $m$,
+alors
+\[
+a^{\varphi(m)} \equiv 1 \pmod{m}
+\]
+
+Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$
+a un ordre qui doit diviser l'ordre du groupe, i.e. $\varphi(m)$.
+
+Attention ! ne pas confondre l'ordre d'un élément du groupe additif
+$\mathbb{Z}/m\mathbb{Z}$ et l'ordre d'un élément du groupe
+multiplicatif $(\mathbb{Z}/m\mathbb{Z})^\times$.  Exemple : quel est
+l'ordre de $2$ dans $\mathbb{Z}/7\mathbb{Z}$ ? dans
+$(\mathbb{Z}/7\mathbb{Z})^\times$ ?
+
+Cas particulier : petit théorème de Fermat : si $p$ est premier, alors
+pour tout entier $a$ on a
+\[
+a^p \equiv a \pmod{p}
+\]
+Ceci fournit une condition \emph{nécessaire} mais non suffisante pour
+qu'un nombre soit premier.
+
+%
+\subsection{Éléments primitifs}
+
+Soit $m$ un entier naturel non nul.  On dit que $g \in
+(\mathbb{Z}/m\mathbb{Z})^\times$ est (un résidu) \textbf{primitif}
+(modulo~$m$) lorsqu'il engendre $(\mathbb{Z}/m\mathbb{Z})^\times$
+(comme groupe abélien multiplicatif) --- ce qui entraîne que
+$(\mathbb{Z}/m\mathbb{Z})^\times$ est cyclique.
+
+Autrement dit, $g^{\varphi(m)}=1$ est optimal ($\varphi(m)$ est
+exactement l'ordre de $g$).
+
+Exemple : les puissances de $\bar 2$ modulo $9$ sont : $\bar 2,\bar
+4,\bar 8,\bar 7,\bar 5,\bar 1$ ; il y en a bien $\varphi(9)=6$ donc
+$2$ est primitif modulo $9$.
+
+\smallbreak
+\textbf{Attention !} Ne pas confondre :
+\begin{itemize}
+\item $\mathbb{Z}/m\mathbb{Z}$ (groupe \emph{additif}, d'élément
+neutre $0$) est d'ordre $m$ et est \emph{toujours} cyclique (avec pour
+générateurs au moins $1$ et $-1$, et tous les éléments de
+$(\mathbb{Z}/m\mathbb{Z})^\times$).
+\item $(\mathbb{Z}/m\mathbb{Z})^\times$ (groupe \emph{multiplicatif},
+d'élément neutre $1$) est d'ordre $\varphi(m)$ et est \emph{parfois}
+cyclique (auquel cas ses générateurs s'appellent éléments
+\emph{primitifs}).
+\end{itemize}
+
+\medbreak
+
+\textbf{Théorème :}
+\begin{itemize}
+\item Si $p$ est un nombre premier impair, alors
+  $(\mathbb{Z}/p\mathbb{Z})^\times$ est cyclique, i.e., il existe des
+  éléments primitifs modulo $p$.  (Il en existe exactement
+  $\varphi(p-1)$.)
+\item Si $p$ est un nombre premier impair et $r\geq 2$, alors
+  $(\mathbb{Z}/p^r\mathbb{Z})^\times$ est cyclique, i.e., il existe
+  des éléments primitifs modulo $p^r$.  (Il en existe exactement
+  $\varphi(p^{r-1}(p-1))$.)  \emph{Mieux} : $g$ est primitif modulo
+  $p^r$ si et seulement si il l'est modulo $p^2$.
+\item Si $p=2$ et $1\leq r\leq 2$, alors
+  $(\mathbb{Z}/2^r\mathbb{Z})^\times$ est trivialement cyclique.
+\item Si $p=2$ et $r \geq 3$, alors
+  $(\mathbb{Z}/2^r\mathbb{Z})^\times$ \emph{n'est pas} cyclique : il
+  est produit d'un groupe cyclique d'ordre $2$ engendré par $-1$ et
+  d'un groupe cyclique d'ordre $2^{r-2}$ engendré par $5$.
+\end{itemize}
+
+%
+\subsection{Exercices}
+
+\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).
+
+%
 %
 %
 \end{document}