Start second part.

1 files changed, 158 insertions, 4 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index badb046..dbb8889 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -29,6 +29,7 @@
 \newcommand{\pgcd}{\operatorname{pgcd}}
 \newcommand{\ppcm}{\operatorname{ppcm}}
 \newcommand{\signe}{\operatorname{signe}}
+\newcommand{\tee}{\mathbin{\top}}
 \renewcommand{\qedsymbol}{\smiley}
 %
 %
@@ -39,7 +40,7 @@
 \maketitle
 {\footnotesize
 \begin{center}
-CVS: \verb=$Id: rappels-maths.tex,v 1.1 2008-09-29 18:58:04 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.2 2008-09-29 21:40:25 david Exp $=
 \end{center}
 \par}
 \pretolerance=10000
@@ -103,8 +104,9 @@ complètement théorique.
 %
 \subsection{Divisiblité (exacte)}
 
-Définition.  Réflexive, transitive.  Pas tout à fait antisymétrique
-(mais vrai dans les entiers naturels).
+Définition.  Terminologie « diviseur de », « multiple de ».  Relation
+réflexive, transitive.  Pas tout à fait antisymétrique (mais vrai dans
+les entiers naturels).
 
 Note : Les entiers $1$ et $-1$ divisent tous les entiers.  L'entier
 $0$ est divisible par tous les entiers.
@@ -116,6 +118,12 @@ Un \textbf{nombre premier} $p$ est un entier (par convention :
 positif) divisible seulement par $1$, $-1$, lui-même et son opposé ;
 mais par convention, $1$ et $-1$ (et $0$...) ne sont pas premiers.
 
+Les premiers nombres premiers sont donc : $2$, $3$, $5$, $7$, $11$,
+$13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$,
+$59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$, $97$...
+
+\medbreak
+
 Sur leur répartition :
 
 Il y en a une infinité (Euclide).
@@ -125,7 +133,16 @@ $x\leq p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand »).
 
 Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à
 $\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée
-Poussin : « théorème des nombres premiers »).
+Poussin : « théorème des nombres premiers »).  Moralement : la
+probabilité qu'un nombre de $n$ bits aléatoire soit premier est
+environ $n\,\ln 2$.
+
+Beaucoup de questions ouvertes.  Par exemple : Conjecture des nombres
+premiers jumeaux : existe-t-il une infinité de nombres premiers $p$
+tels que $p+2$ soit aussi premier (tels que $3$, $5$, $11$, $17$,
+$29$, $41$, $59$, $71$...) ?
+
+\smallbreak
 
 \textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors
 $p$ divise $a$ ou $p$ divise $b$.
@@ -319,6 +336,11 @@ relation de Bézout entre $a$ et $b$.  Donc il n'y a pas unicité.
 Si $au + bv = \pm 1$ on dit parfois que les rationnels $a/b$ et $-v/u$
 (écrits sous forme irréductible) sont \emph{adjacents}.
 
+\medbreak
+
+Plus généralement, si $\pgcd(a,b) = d$, on peut trouver $u$ et $v$
+tels que $au+bv = d$.
+
 %
 \subsection{Algorithme d'Euclide}
 
@@ -375,6 +397,138 @@ nq+r$.
 \textbf{Invariants :} $au+bv=m$ et $au'+bv'=n$.
 
 %
+\section{Congruences et entiers modulaires}
+
+\subsection{Congruence}
+
+Soit $m$ un entier fixé pour le moment :
+
+Si $x$ et $x'$ sont entiers, on dit que $x$ et $x'$ sont
+\textbf{congrus} modulo $m$, noté $x \equiv x' \pmod{m}$, lorsque
+$x-x'$ est multiple de $m$.  Relation réflexive, symétrique,
+transitive.
+
+Compatibilité avec les opérations : (à $m$ fixé,) si $x\equiv x'$ et
+$y \equiv y'$ alors $x+y \equiv x'+y'$ et $xy \equiv x'y'$.  À $m$
+variable : si $m|m'$ alors $x \equiv x' \pmod{m'}$ implique $x\equiv
+x' \pmod{m}$ (la congruence modulo $m'$ est \emph{plus fine} que
+modulo $m$).
+
+Représentants : si $m \geq 1$ alors chaque entier est congru
+modulo $m$ à l'un des nombres $0,1,2,\ldots,(m-1)$ (le reste de sa
+division euclidienne par $m$ !).
+
+Exemple de $\mathbb{Z}/2\mathbb{Z}$ avec pair=$\bar 0$ et impair=$\bar
+1$.
+
+On veut définir $\mathbb{Z}/m\mathbb{Z} = \{\bar 0, \bar 1, \bar 2,
+\ldots, \overline{m-1}\}$ de façon analogue : pour ajouter $\bar x$ et
+$\bar y$, on consière $\bar x + \bar y = \overline{x+y}$ et $\bar x\,
+\bar y = \overline{xy}$.  Reste à savoir ce que la barre veut dire !
+
+%
+\subsection{Généralité sur les quotients}
+
+Généralité : soit $E$ un ensemble et $\sim$ une relation d'équivalence
+(i.e., réflexive, symétrique, transitive) sur $E$, on appelle
+$E/{\sim}$ l'ensemble des classes d'équivalence de $E$ modulo $\sim$
+(la classe d'équivalence d'un élément $x\in E$ est l'ensemble des
+éléments $x'\in E$ tels que $x\sim x'$).  On note $\pi \colon E \to
+(E/{\sim})$ la fonction qui envoie $x\in E$ sur sa classe
+d'équivalence $\pi(x) = \bar x$.  Ainsi : $\pi(x) = \pi(x')$ ssi $x
+\sim x'$.  (Moralement : on a transformé la relation d'équivalence
+$\sim$ en une vraie égalité.)
+
+Si on a sur $E$ une opération binaire, disons, $\tee$, telle que $x
+\sim x'$ et $y \sim y'$ impliquent $(x\tee x') \sim (y\tee y')$ (on
+dit que $\sim$ est \emph{compatible} avec l'opération $\tee$), alors
+on peut définir une opération binaire $\mathbin{\bar\top}$ sur
+$E/{\sim}$ par $\pi(x) \mathbin{\bar\top} \pi(x') = \pi(x\tee x')$.
+
+L'application $\pi\colon E \to (E/{\sim})$ préserve alors l'opération
+$\tee$ et on dit qu'il s'agit d'un \emph{morphisme} (d'ensembles munis
+d'une opération binaire $\tee$).
+
+%
+\subsection{Calculs dans $\mathbb{Z}/m\mathbb{Z}$}
+
+Vision concrète de $\mathbb{Z}/m\mathbb{Z}$ pour $m\geq 1$ : on
+travaille avec les nombres $0,\ldots,m-1$ (qui sont des
+\emph{représentants} arbitraires des $m$ classes de congruences
+modulo $m$).  Les opérations sont faites dans les entiers mais ensuite
+on se ramène à une classe représentée par un entier entre $0$ et $m-1$
+en effectuant une division euclidienne par $m$.
+
+Exemple : si $m=10$, on a $\bar 8 + \bar 5 = \bar 3$ et $\bar 8 \times
+\bar 5 = \bar 0$.
+
+(Note : en fait, pour l'addition, il suffit de soustraire
+éventuellement $m$ si le résultat l'excède : pas besoin de faire une
+vraie division euclidienne.)
+
+Les ordinateurs travaillent naturellement dans
+$\mathbb{Z}/2^r\mathbb{Z}$ avec $r$ valant typiquement $16$, $32$ ou
+$64$.
+
+Note importante : Le choix des représentants $0,\ldots,m-1$ est
+arbitraire : on pourrait tout aussi bien choisir $1,\ldots,m$ ou bien
+$-\lfloor\frac{m-1}{2}\rfloor,\ldots,\lfloor\frac{m}{2}\rfloor$ (ou
+encore des choses tout à fait arbitraires).
+
+\medbreak
+
+Et si $m\leq 1$ ?
+\begin{itemize}
+\item On a $\mathbb{Z}/1\mathbb{Z} = \{\bar 0\}$, et les opérations
+  sont triviales ($\bar 0 + \bar 0 = \bar 0$ et $\bar 0 \times \bar 0
+  = \bar 0$).
+\item On a $\mathbb{Z}/0\mathbb{Z} = \mathbb{Z}$.
+\item Si $m<0$ alors $\mathbb{Z}/m\mathbb{Z} =
+  \mathbb{Z}/(-m)\mathbb{Z}$.
+\end{itemize}
+
+En général quand on parle de $\mathbb{Z}/m\mathbb{Z}$ on sous-entend
+$m\geq 1$, parfois même $m \geq 2$ !
+
+%
+\subsection{Premières propriétés de $\mathbb{Z}/m\mathbb{Z}$}
+
+C'est un anneau commutatif.  Il n'est \emph{pas intègre} en général :
+on peut avoir $ab=\bar 0$ dans $\mathbb{Z}/m\mathbb{Z}$ alors que $a
+\neq \bar 0$ et $b \neq \bar 0$ (exemple : $\bar 2 \times \bar 5 =
+\bar 0$ dans $\mathbb{Z}/10\mathbb{Z}$).
+
+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$.
+
+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
+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.
+
+%
+\subsection{Inversibles de $\mathbb{Z}/m\mathbb{Z}$}
+
+Si $a$ et $m$ sont premiers entre eux, alors on sait qu'on peut
+trouver une relation de Bézout $au + mv = 1$.  On a alors $\bar a \bar
+u = \bar 1$ : on dit que $\bar a$ est \emph{(multiplicativement)
+  inversible} dans $\mathbb{Z}/m\mathbb{Z}$, ou est une \emph{unité}
+de cet anneau.  Réciproquement, si on peut trouver $\bar u$ tel que
+$\bar a \bar u = \bar 1$, alors $a$ est premier à $m$.
+
+On appelle $(\mathbb{Z}/m\mathbb{Z})^\times$ l'ensemble des
+inversibles multiplicatifs de $\mathbb{Z}/m\mathbb{Z}$.  C'est un
+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$.
+
+%
 %
 %
 \end{document}