Rework some more.

1 files changed, 58 insertions, 6 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index 338423d..24ecd17 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.14 2009-10-21 17:36:47 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.15 2009-10-21 17:53:44 david Exp $=
 \end{center}
 \par}
 \pretolerance=10000
@@ -556,6 +556,16 @@ fines que modulo $m$.  (Exemple : connaître la congruence modulo $4$
 permet de connaître la congruence modulo $2$.)  C'est également un
 morphisme d'anneaux.
 
+\textbf{Attention !} le paragraphe précédent signifie que quand
+$m|m'$, on peut réduire modulo $m$ un élément de
+$\mathbb{Z}/m'\mathbb{Z}$.  Ceci n'a pas de sens sans l'hypothèse
+$m|m'$ !  Par exemple, donné un élément de $\mathbb{Z}/20\mathbb{Z}$,
+il y a un sens à parler de sa classe modulo $5$ ou modulo $4$ ou
+modulo $2$ (c'est-à-dire dire s'il est pair ou impair...) ; en
+revanche, il n'y a \emph{aucun sens} à parler de sa classe modulo $3$
+(ou même à se demander s'il est multiple de $3$).  Le théorème
+« chinois » précisera cette idée.
+
 %
 \subsection{Inversibles de $\mathbb{Z}/m\mathbb{Z}$}
 
@@ -585,8 +595,9 @@ Exemple : dans $\mathbb{Z}/10\mathbb{Z}$, les éléments $\bar 1, \bar
 
 On note $\varphi(m)$ le cardinal de
 $(\mathbb{Z}/m\mathbb{Z})^\times$ : la fonction $\varphi$ s'appelle
-\emph{fonction indicatrice d'Euler} (exemple : $\varphi(10) = 4$).  On
-verra plus loin comment la calculer.
+\emph{fonction indicatrice d'Euler} ; elle compte donc le nombre
+d'entiers entre $0$ et $m-1$ premiers avec $m$ (exemple : $\varphi(10)
+= 4$).  On verra plus loin comment la calculer.
 
 Note : on a deux involutions importantes sur
 $(\mathbb{Z}/m\mathbb{Z})^\times$ : l'une est $\bar a \mapsto -\bar
@@ -625,6 +636,14 @@ c'est donc un \textbf{isomorphisme}.
 Dresser la table d'isomorphisme de $\mathbb{Z}/10\mathbb{Z}$ avec
 $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z})$...
 
+\smallbreak
+
+Concrètement, le théorème chinois signifie : lorsque $m$ et $n$ sont
+premiers entre eux, se donner un entier modulo $mn$ revient au même
+que se donner cet entier modulo $m$ et modulo $n$ séparément (et, de
+plus, toutes les combinaisons d'une classe modulo $m$ et d'une classe
+modulo $n$ sont possibles pour une unique classe modulo $mn$).
+
 %
 \subsection{Théorème chinois explicite}
 
@@ -638,6 +657,11 @@ a pour réciproque
 \end{array}
 \]
 
+(Remarque : dans cette expression, on peut se contenter de calculer
+$uy$ modulo $n$ avant de le multiplier par $m$, et de même $vx$
+modulo $m$ avant de le multiplier par $n$, ce qui est parfois plus
+efficace que de faire tout le calcul modulo $mn$.)
+
 Exemple : trouver le nombre entre $0$ et $100$ congru à $9$
 modulo $11$ et à $3$ modulo $13$.  (Relation de Bézout : $6\times 11 -
 5 \times 13 = 1$ ; ensuite, $6 \times 11 \times 3 - 5 \times 13 \times
@@ -645,9 +669,27 @@ modulo $11$ et à $3$ modulo $13$.  (Relation de Bézout : $6\times 11 -
 
 \medskip
 
-Plus généralement, connaissant la classe d'un entier modulo
-$m_1,\ldots,m_k$, on peut retrouver sa classe modulo
-$\ppcm(m_1,\ldots,m_k)$.
+Généralisations du théorème chinois :
+\begin{itemize}
+\item Si $m$ et $n$ ne sont pas premiers entre eux, toute donnée d'une
+  classe $x$ modulo $m$ et d'une classe $y$ modulo $n$ ne permet pas
+  forcément de retrouver une classe modulo $mn$ (il faut, et il
+  suffit, pour cela, que $x$ et $y$ soient « compatibles »,
+  c'est-à-dire congrus modulo $d = \pgcd(m,n)$).  Lorsque $x$ et $y$
+  sont compatibles, alors on retrouve une unique classe modulo
+  $\ppcm(m,n)$ (pour faire le calcul en pratique, diviser l'un des
+  deux nombres $m,n$ par $d$ pour se ramener à deux nombres premiers
+  entre eux).
+\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
+  le calcul en pratique, on utilise les classes modulo $m_1,m_2$ pour
+  trouver une classe modulo $m_1 m_2$, puis celle-ci et la classe
+  modulo $m_3$ déterminent une classe modulo $m_1 m_2 m_3$, etc.).
+\item En combinant ces deux généralisations : connaissant la classe
+  d'un entier modulo $m_1,\ldots,m_k$, on peut retrouver sa classe
+  modulo $\ppcm(m_1,\ldots,m_k)$.
+\end{itemize}
 
 %
 \subsection{Calcul de l'indicatrice d'Euler}
@@ -670,6 +712,16 @@ On en déduit :
 \]
 où $p$ parcourt les premiers divisant $n$.
 
+Exemple : $\varphi(63) = \frac{2}{3}\times\frac{6}{7}\times 63 = 36$.
+
+(Intuitivement : parmi les $n$ entiers de $0$ à $n-1$, pour chacun des
+nombres premiers $p$ divisant $n$, il y a une proportion
+$\frac{p-1}{p}$ des nombres qui ne sont pas multiples de $p$, et
+toutes ces propriétés sont indépendantes --- c'est essentiellement le
+théorème chinois --- donc la proportion des nombres qui ne sont
+multiples d'aucun des $p$ divisant $n$ est le produit des
+$\frac{p-1}{p}$.)
+
 \textbf{Algorithmiquement :} \emph{lent} en général (demande de
 connaître la d.f.p.).