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