diff options
| author | david <david> | 2009-10-21 18:17:11 +0000 |
|---|---|---|
| committer | david <david> | 2009-10-21 18:17:11 +0000 |
| commit | f41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4 (patch) | |
| tree | be724493cca8d705b2ea0faf80d3294b73938c84 | |
| parent | 1d04040b93484b109e83dff407026b7428624e2d (diff) | |
| download | infmdi720-f41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4.tar.gz infmdi720-f41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4.tar.bz2 infmdi720-f41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4.zip | |
Rework the part on Z/mZ.
| -rw-r--r-- | rappels-maths.tex | 131 |
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�} |