From 1d04040b93484b109e83dff407026b7428624e2d Mon Sep 17 00:00:00 2001 From: david Date: Wed, 21 Oct 2009 17:53:44 +0000 Subject: Rework some more. --- rappels-maths.tex | 64 +++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file 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 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 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 \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 \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 \] 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.). -- cgit v1.2.3