summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordavid <david>2009-10-21 17:53:44 +0000
committerdavid <david>2009-10-21 17:53:44 +0000
commit1d04040b93484b109e83dff407026b7428624e2d (patch)
tree4052c21c877c2940ea56276088f425a260a1becb
parented3a4451987146fb5f4decfb8b71552394405f9d (diff)
downloadinfmdi720-1d04040b93484b109e83dff407026b7428624e2d.zip
infmdi720-1d04040b93484b109e83dff407026b7428624e2d.tar.gz
infmdi720-1d04040b93484b109e83dff407026b7428624e2d.tar.bz2
Rework some more.
-rw-r--r--rappels-maths.tex64
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.).