summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2011-11-23 17:21:42 +0100
committerDavid A. Madore <david+git@madore.org>2011-11-23 17:21:42 +0100
commit99cd4fb818b9194c15738209ecca5f50d74d2792 (patch)
tree84189270627540be854cce4d9762d8e94d89c368
parent2b641059d07956e472019e3f93e4af13f2bfb09c (diff)
downloadinfmdi720-upload-20111123.tar.gz
infmdi720-upload-20111123.tar.bz2
infmdi720-upload-20111123.zip
Attempt to clarify various things.upload-20111123
-rw-r--r--rappels-maths.tex33
1 files changed, 23 insertions, 10 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex
index 57a421b..542bc7d 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -422,10 +422,9 @@ Si $au + bv = \pm 1$ on dit parfois que les rationnels $a/b$ et $-v/u$
\medbreak
Plus généralement, si $\pgcd(a,b) = d$, on peut trouver $u$ et $v$
-tels que $au+bv = d$ (en fait, il existe $d',d''$ avec $d=d'd''$ tels
-que $a/d'$ et $b/d''$ soient premiers entre eux, et si
-$(a/d')u_0+(b/d'')v_0 = 1$ est une relation de Bézout entre eux, alors
-on a $a(d''u_0)+b(d'v_0) = d$).
+tels que $au+bv = d$ (en fait, $\pgcd(\frac{a}{d},\frac{b}{d}) = 1$,
+et si $\frac{a}{d} u + \frac{b}{d} v = 1$ est une relation de Bézout
+entre eux, alors on a $au + bv = d$).
%
\subsection{Algorithme d'Euclide}
@@ -741,7 +740,8 @@ Généralisations du théorème chinois :
sont compatibles, alors on retrouve une unique classe modulo
$\ppcm(m,n)$ (pour faire le calcul en pratique, diviser les nombres
$m,n$ par $d',d''$ tels que $d'd''=d$ pour se ramener à deux nombres
- $m/d'$ et $n/d''$ premiers entre eux).
+ $m/d'$ et $n/d''$ premiers entre eux et dont le produit vaut
+ $\frac{mn}{\pgcd(m,n)} = \ppcm(m,n)$).
\item Si $m_1,\ldots,m_k$ sont premiers entre eux \emph{deux à deux},
alors la donnée d'une classe modulo le produit $m_1\cdots m_k$
équivaut à la donnée de classes modulo chacun des $m_i$ (pour faire
@@ -853,6 +853,9 @@ l'élément $g$. Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi
$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$, et donc $g^i
= g^j$ si $i \equiv j \pmod{m}$.
+Attention : le fait d'avoir $g^m = 1$ signifie (exactement) que
+l'ordre de $g$ \emph{divise} $m$, pas forcément qu'il est égal à $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
@@ -994,9 +997,10 @@ Soit $m$ un entier naturel non nul. On dit que $g \in
(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 : dire que $g$ est
-primitif modulo $m$ signifie que son ordre multiplicatif est
-exactement $\varphi(m)$ (et pas un autre diviseur de $\varphi(m)$).
+Autrement dit, $g^{\varphi(m)}=1$ est \emph{optimal} : dire que $g$
+est primitif modulo $m$ signifie que son ordre multiplicatif est
+\emph{exactement} $\varphi(m)$ (et pas un autre diviseur de
+$\varphi(m)$).
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
@@ -1020,8 +1024,8 @@ cyclique (auquel cas ses générateurs s'appellent éléments
\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
+ $(\mathbb{Z}/p\mathbb{Z})^\times$ est cyclique, i.e., \emph{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
@@ -1037,6 +1041,15 @@ cyclique (auquel cas ses générateurs s'appellent éléments
maximal possible d'un élément est $2^{r-2}$).
\end{itemize}
+\smallbreak
+
+Attention à ne pas faire l'erreur suivante : si on a
+$g^{\varphi(m)}=1$, cela \emph{ne signifie pas} que $g$ soit primitif,
+et d'ailleurs c'est le cas pour tout élément inversible de
+$\mathbb{Z}/m\mathbb{Z}$ d'après le théorème d'Euler : pour pouvoir
+dire que $g$ est primitif, la condition importante est que $g^i \neq
+1$ lorsque $0<i<\varphi(m)$.
+
%
\section{Polynômes}