Rewrite the section on integers.

1 files changed, 61 insertions, 41 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index dfcad4b..338423d 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.13 2009-10-21 17:09:11 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.14 2009-10-21 17:36:47 david Exp $=
 \end{center}
 \par}
 \pretolerance=10000
@@ -56,14 +56,35 @@ CVS: \verb=$Id: rappels-maths.tex,v 1.13 2009-10-21 17:09:11 david Exp $=
 $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ ensemble des
 entiers relatifs.  Sous-ensemble $\mathbb{N}$.
 
-Opérations : $+$, $\times$.
+Opérations : $+$, $\times$ ; éléments remarquables : $0$, $1$.
+Vérifient les propriétés suivantes :
+\begin{itemize}
+\item Associativité de $+$ : $x+(y+z) = (x+y)+z$
+\item Neutralité de $0$ pour $+$ : $0+x = x+0 = x$
+\item Existence d'opposés : (pour chaque $x$, il existe un élément
+  noté $-x$ tel que) $x + (-x) = (-x) + x = 0$
+\item Commutativité de $+$ : $y+x = x+y$
+\item Distributivité de $\times$ sur $+$ : $x(y+z) = xy + xz$
+\item Associativité de $\times$ : $x(yz) = (xy)z$
+\item Neutralité de $1$ pour $\times$ : $1x = x1 = x$
+\item Commutativité de $\times$ : $yx = xy$
+\end{itemize}
 
-Rappeler : $(\mathbb{Z},0,+)$ est un groupe abélien,
-$(\mathbb{Z},0,+,1,\times)$ est un anneau commutatif.
+Les trois premières propriétés signifient que $\mathbb{Z}$ est un
+\emph{groupe} pour l'addition ; les quatre premières, que $\mathbb{Z}$
+est un \emph{groupe abélien} pour l'addition ; les sept premières
+propriétés signifient que $\mathbb{Z}$ est un \emph{anneau} ; les huit
+propriétés réunies signifient que $\mathbb{Z}$ est un \textbf{anneau
+  commutatif}.
 
-Mieux : anneau intègre (si $uv=0$ alors $u=0$ ou $v=0$).
+Mieux : c'est un \emph{anneau intègre} : si $uv=0$ alors $u=0$ ou
+$v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 =
+0$).
 
-Éléments inversibles : $1$ et $-1$.
+Éléments inversibles : un \textbf{inversible} ou une \textbf{unité}
+(dans un anneau commutatif) est un élément $x$ tel qu'il existe $y$
+tel que $xy = 1$.  Dans $\mathbb{Z}$, les inversibles sont $1$ et
+$-1$.
 
 Relation d'ordre...
 
@@ -72,7 +93,9 @@ Relation d'ordre...
 
 Si $b\geq 2$ est un entier naturel, tout entier naturel $A$ s'écrit de
 façon unique $A = \sum_{i=0}^{+\infty} a_i b^i$ avec $0\leq a_i<b$
-entiers naturels « presque tous nuls » (expliquer).
+entiers naturels « presque tous nuls » (c'est-à-dire nuls sauf un
+nombre fini : donc la somme peut en fait s'écrire $A =
+\sum_{i=0}^{n-1} a_i b^i$).
 
 Écriture usuelle : $b=10$.  Informatique : $b=2$.  Un nombre « de $n$
 bits » signifie : inférieur à $2^n$.
@@ -80,8 +103,6 @@ bits » signifie : inférieur à $2^n$.
 Multiplier par $b$ revient à décaler tous les chiffres d'un cran vers
 la gauche.
 
-On passe pour l'instant sur l'écriture des nombres négatifs.
-
 %
 \subsection{Remarques sur la complexité des opérations}
 
@@ -89,7 +110,7 @@ Addition de nombres de $n$ bits : algorithme naïf en $O(n)$.
 
 Multiplication : plus compliqué.
 
-Algorithme naïf en $O(n^2)$.
+Algorithme naïf en $O(n^2)$ (appris à l'école primaire).
 
 \emph{Multiplication de Karatsuba} : utilise récursivement
 l'identité ${(a_1 w + a_0)} \penalty0 {(b_1 w + b_0)} = a_1 b_1 w^2 +
@@ -105,9 +126,14 @@ complètement théorique.
 %
 \subsection{Divisiblité (exacte)}
 
-Définition.  Terminologie « diviseur de », « multiple de ».  Relation
-réflexive, transitive.  Pas tout à fait antisymétrique (mais vrai dans
-les entiers naturels).
+Si $a$ et $b$ sont deux entiers, on dit que $b$ divise $a$, et on note
+$b|a$, lorsqu'il existe $q \in \mathbb{Z}$ tel que $a = bq$.
+
+Cette relation est réflexive (on a $a|a$ pour tout $a$) et transitive
+(si $b|a$ et $c|b$ alors $c|a$).  Elle n'est pas tout à fait
+antisymétrique, mais c'est vrai dans les entiers naturels : si $a$ et
+$b$ sont des entiers naturels tels que $b|a$ et $a|b$ alors $b=a$
+(dans les entiers relatifs, on peut aussi avoir $b=-a$).
 
 Note : Les entiers $1$ et $-1$ divisent tous les entiers.  L'entier
 $0$ est divisible par tous les entiers.
@@ -129,8 +155,10 @@ Sur leur répartition :
 
 Il y en a une infinité (Euclide).
 
-Pour tout $x>1$, il y a toujours un nombre premier $p$ tel que
-$x < p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand »).
+Pour tout $x>1$, il y a toujours un nombre premier $p$ tel que $x < p
+< 2x$ (\v Ceby\v sëv : « postulat de Bertrand »).  De façon
+équivalente : si $p$ est premier, alors le nombre premier qui le suit
+immédiatement est $<2p$.
 
 Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à
 $\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée
@@ -307,10 +335,10 @@ eux, être multiple de $m$ et de $n$ équivaut à être multiple de $mn$.
 %
 \subsection{PPCM}
 
-Définition analogue au PGCD.  Exemple : le ppcm de $6$ et $10$
+Définition analogue au pgcd.  Exemple : le ppcm de $6$ et $10$
 est $30$ ; le ppcm de $6$, $10$ et $15$ est aussi $30$.  Lien avec la
 DFP (pour un nombre fini d'entiers).  Le ppcm d'une famille infinie
-d'entiers est défini, mais parfois surprenant (quel est le PPCM de
+d'entiers est défini, mais parfois surprenant (quel est le ppcm de
 tous les nombres premiers ?).
 
 %
@@ -340,7 +368,9 @@ Si $au + bv = \pm 1$ on dit parfois que les rationnels $a/b$ et $-v/u$
 \medbreak
 
 Plus généralement, si $\pgcd(a,b) = d$, on peut trouver $u$ et $v$
-tels que $au+bv = d$.
+tels que $au+bv = d$ (en fait, $a/d$ et $b$ sont premiers entre eux,
+et si $(a/d)u+bv' = 1$ est une relation de Bézout entre eux, alors on
+a $au+b(v'd) = d$).
 
 %
 \subsection{Algorithme d'Euclide}
@@ -397,30 +427,20 @@ 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$.
+\smallbreak
 
-\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$.
+Dans la pratique, à la main, on procède ainsi : pour calculer une
+relation de Bézout entre $64$ et $47$, on effectue les divisions
+euclidiennes successives $64 = 1\times 47 + 17$, $47 = 2\times 17 +
+13$, $17 = 1\times 13 + 4$, $13 = 3\times 4 + 1$ jusqu'à tomber sur le
+reste $1$.  Puis on réécrit ce reste en partant de la dernière
+division $1 = 13 - 3\times 4$ et en remplaçant successivement le reste
+de chaque division (les à l'envers) par une combinaison du dividende
+et du diviseur : $4 = 17 - 1\times 13$ donc $1 = 13 -
+3\times(17-1\times 13) = 4\times 13 - 3\times 17$ puis $13 = 47 -
+2\times 17$ donc $1 = 4\times (47 - 2\times 17) - 3\times 17 = 4\times
+47 - 11\times 17$ et enfin $17 = 1\times 64 - 47$ donc $1 = 4\times 47
+- 11\times (1\times 64 - 47) = 15\times 47 - 11\times 64$.
 
 %
 \section{Congruences et entiers modulaires}