Exercises for first part. Continue second part.

1 files changed, 128 insertions, 4 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index dbb8889..5c06c59 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -40,7 +40,7 @@
 \maketitle
 {\footnotesize
 \begin{center}
-CVS: \verb=$Id: rappels-maths.tex,v 1.2 2008-09-29 21:40:25 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.3 2008-09-30 21:58:17 david Exp $=
 \end{center}
 \par}
 \pretolerance=10000
@@ -397,6 +397,31 @@ nq+r$.
 \textbf{Invariants :} $au+bv=m$ et $au'+bv'=n$.
 
 %
+\subsection{Exercices}
+
+\thingy Montrer que si $a, b \in \mathbb{Z}$ vérifient $a^2 = 2b^2$
+alors $a=b=0$.  Comment interpréter ce résultat sur le
+nombre $\sqrt{2}$ ?
+
+\thingy Montrer que, si $n \geq 2$ alors $\sum_{i=1}^n \frac{1}{i}$
+n'est pas un entier.  (Indication : montrer que sa valuation
+$2$-adique est strictement négative ; ou bien : montrer que sa
+valuation $p$-adique vaut $-1$ avec $p$ le plus grand nombre premier
+inférieur à $n$, en utilisant le postulat de Bertrand.)
+
+\thingy Montrer que, pour tout $p$ premier et $n$ entier naturel,
+$v_p(n!) = \sum_{i=i}^{+\infty} \lfloor\frac{n}{p^i}\rfloor$ (où
+$\lfloor\cdot\rfloor$ désigne la partie entière.
+
+\thingy Montrer que pour $a, b$ entiers, on a $\pgcd(a,b)\, \ppcm(a,b)
+= ab$.
+
+\thingy On définit par récurrence les nombres de Fibonacci : $F_0 =
+0$, $F_1 = 1$ et $F_{n+1} = F_n + F_{n-1}$.  Écrire une relation de
+Bézout entre $F_8$ et $F_9$.  Montrer que $F_n$ et $F_{n+1}$ sont
+premiers entre eux pour tout $n$.
+
+%
 \section{Congruences et entiers modulaires}
 
 \subsection{Congruence}
@@ -501,8 +526,8 @@ on peut avoir $ab=\bar 0$ dans $\mathbb{Z}/m\mathbb{Z}$ alors que $a
 Surjection canonique : c'est l'application $\pi\colon \mathbb{Z} \to
 \mathbb{Z}/m\mathbb{Z}$ qui envoie $x\in\mathbb{Z}$ sur sa classe de
 congruence modulo $m$.  C'est un \emph{morphisme d'anneaux}, i.e., il
-préserve l'addition et la multiplication et envoie $0$ et $1$ sur $0$
-et $1$.
+préserve l'addition et la multiplication et envoie $0$ et $1$ sur
+$\bar 0$ et $\bar 1$.
 
 Si $m|m'$, il y a une application naturelle $\mathbb{Z}/m'\mathbb{Z}
 \to \mathbb{Z}/m\mathbb{Z}$ car les classes modulo $m'$ sont plus
@@ -526,7 +551,106 @@ groupe pour la multiplication (plus généralement, dans tout anneau
 commutatif $A$, l'ensemble des inversibles/unités de $A$ forme un
 groupe noté $A^\times$).
 
-On note $\varphi(m)$ le cardinal de $(\mathbb{Z}/m\mathbb{Z})^\times$.
+Si $\bar a$ est inversible dans $\mathbb{Z}/m\mathbb{Z}$, on pourra
+noter $\bar a^{-1}$ son inverse (qui est évidemment de nouveau
+inversible...).  On le calcule à partir d'une relation de Bézout.
+Attention, il n'est pas évident de relier $\bar a^{-1}$ avec le
+rationnel $1/a$ !
+
+Exemple : dans $\mathbb{Z}/10\mathbb{Z}$, les éléments $\bar 1, \bar
+3, \bar 7, \bar 9$ sont inversibles, et leurs inverses sont $\bar
+1^{-1} = \bar 1, \bar 3^{-1} = \bar 7, \bar 7^{-1} = \bar 3, \bar
+9^{-1} = \bar 9$.
+
+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.
+
+Note : on a deux involutions importantes sur
+$(\mathbb{Z}/m\mathbb{Z})^\times$ : l'une est $\bar a \mapsto -\bar
+a$, et l'autre est $\bar a \mapsto \bar a^{-1}$.  Comme la première
+n'a pas de point fixe, $\varphi(m)$ est toujours \emph{pair} (sauf
+pour $m=2$).
+
+Si $p$ est premier, alors tous les nombres entre $1$ et $p-1$ sont
+premiers avec $p$ : $(\mathbb{Z}/p\mathbb{Z})^\times = \{\bar
+1,\ldots, \overline{p-1}\}$ (et notamment $\varphi(p) = p-1$).  Tous
+les éléments de $\mathbb{Z}/p\mathbb{Z}$ sont inversibles sauf $\bar
+0$ : on dit que l'anneau $\mathbb{Z}/p\mathbb{Z}$ est un \emph{corps}
+et on le note $\mathbb{F}_p$.
+
+%
+\subsection{Théorème chinois}
+
+Si $m$ et $n$ sont deux naturels non nuls \textbf{premiers entre eux},
+considérons l'application dont les composantes sont les deux
+surjections canoniques :
+\[
+\mathbb{Z}/(mn)\mathbb{Z} \to (\mathbb{Z}/m\mathbb{Z})
+\times (\mathbb{Z}/n\mathbb{Z})
+\]
+
+Il s'agit d'un \emph{morphisme d'anneaux} (car les surjections
+canoniques en sont !) :
+\begin{itemize}
+\item il est injectif car un entier multiple de $m$ et de $n$
+est multiple de $mn$ (lemme de Gauß),
+\item il est surjectif car les cardinaux coïncident ($mn$ au départ et
+à l'arrivée),
+\end{itemize}
+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})$...
+
+%
+\subsection{Théorème chinois explicite}
+
+Si on a une relation de Bézout $um+vn=1$, alors l'isomorphisme chinois
+a pour réciproque
+\[
+\begin{array}{c}
+(\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \to
+\mathbb{Z}/(mn)\mathbb{Z}\\
+(x,y) \mapsto umy+vnx\\
+\end{array}
+\]
+
+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
+9 \equiv 5\times 11 - 1\times 13 \equiv 42 \pmod{11\times 13}$.)
+
+\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)$.
+
+%
+\subsection{Calcul de l'indicatrice d'Euler}
+
+Si $m$ et $n$ (naturels non nuls) sont premiers entre eux, par le
+théorème chinois on a $(\mathbb{Z}/(mn)\mathbb{Z})^\times \cong
+(\mathbb{Z}/m\mathbb{Z})^\times \times
+(\mathbb{Z}/n\mathbb{Z})^\times$, donc
+\[
+\varphi(mn) = \varphi(m)\,\varphi(n)
+\]
+
+Si $p$ est premier alors $\varphi(p^r) = (p-1)\,p^{r-1}$ (car être
+premier avec $p^r$ équivaut à être premier à $p$, et c'est le cas de
+$p-1$ entiers sur $p$).
+
+On en déduit :
+\[
+\varphi(n) = n\,\prod_{p|n}\left(1-\frac{1}{p}\right)
+\]
+où $p$ parcourt les premiers divisant $n$.
+
+\textbf{Algorithmiquement :} \emph{lent} en général (demande de
+connaître la d.f.p.).
 
 %
 %