From 1f5844826dcfd73d2f78153df1cf2537333c1851 Mon Sep 17 00:00:00 2001
From: david <david>
Date: Tue, 7 Oct 2008 10:04:22 +0000
Subject: More about Z/mZ.
---
rappels-maths.tex | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 136 insertions(+), 1 deletion(-)
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
@@ -652,6 +652,141 @@ o
\textbf{Algorithmiquement�:} \emph{lent} en g�n�ral (demande de
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).
+
%
%
%
--
cgit v1.2.3