From 6fee09df2501c25c667958f733c3701113a08ad8 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 26 Sep 2011 16:34:31 +0200
Subject: Various clarifications at the beginning of the course notes.

---
 rappels-maths.tex | 113 ++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 72 insertions(+), 41 deletions(-)

(limited to 'rappels-maths.tex')

diff --git a/rappels-maths.tex b/rappels-maths.tex
index 56bd174..60660fd 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -56,29 +56,33 @@ Git: \input{vcline.tex}
 
 \subsection{L'anneau des entiers}
 
-$\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ ensemble des
-entiers relatifs.  Sous-ensemble $\mathbb{N}$.
-
-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}
-
-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}.
+On appelle $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ l'ensemble
+des entiers relatifs.  Il a pour sous-ensemble $\mathbb{N} =
+\{0,1,2,3,\ldots\}$ l'ensemble des entiers naturels (ou positifs).
+
+Sur $\mathbb{Z}$ on a les opérations : $+$ (addition) et $\times$
+(multiplication) ; et les éléments remarquables : $0$, $1$.  Ces
+données vérifient les propriétés suivantes :
+\begin{enumerate}
+\item Associativité de l'addition : $x+(y+z) = (x+y)+z$
+\item Neutralité de zéro pour l'addition : $0+x = x+0 = x$
+\item Existence d'opposés (=symétriques pour l'addition) : (pour
+  chaque $x$, il existe un élément noté $-x$ tel que) $x + (-x) = (-x)
+  + x = 0$
+\item Commutativité de l'addition : $y+x = x+y$
+\item Distributivité de la multiplication sur l'addition : $x(y+z) =
+  xy + xz$ et $(x+y)z=xz+yz$
+\item Associativité de la multiplication : $x(yz) = (xy)z$
+\item Neutralité de un pour la multiplication : $1x = x1 = x$
+\item Commutativité de la multiplication : $yx = xy$
+\end{enumerate}
+
+Les trois premières propriétés traduisent le fait 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 traduisent le fait que $\mathbb{Z}$ est un
+\emph{anneau} ; les huit propriétés réunies traduisent le fait que
+$\mathbb{Z}$ est un \textbf{anneau commutatif}.
 
 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 =
@@ -89,9 +93,10 @@ $v=0$ (la r
 tel que $xy = 1$.  Dans $\mathbb{Z}$, les inversibles sont $1$ et
 $-1$.
 
-Relation d'ordre : relation réflexive (on a toujours $x\leq x$),
-antisymétrique (si $x\leq y$ et $y\leq x$ alors $x=y$) et transitive
-(si $x\leq y$ et $y\leq z$ alors $x\leq z$).
+On a aussi sur $\mathbb{Z}$ une relation d'ordre : c'est-à-dire une
+relation réflexive (on a toujours $x\leq x$), antisymétrique (si
+$x\leq y$ et $y\leq x$ alors $x=y$) et transitive (si $x\leq y$ et
+$y\leq z$ alors $x\leq z$).
 
 %
 \subsection{Écriture $b$-adique}
@@ -100,13 +105,17 @@ Si $b\geq 2$ est un entier naturel, tout entier naturel $A$ s'
 façon unique $A = \sum_{i=0}^{+\infty} a_i b^i$ avec $0\leq a_i<b$
 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$).
+\sum_{i=0}^{n-1} a_i b^i$).  Les $a_i$ s'appellent les \emph{chiffres}
+de cette écriture $b$-adique, $a_0$ s'appelant le chiffre des
+\emph{unités} ou chiffre \emph{de poids faible}.
 
-Écriture usuelle : $b=10$.  Informatique : $b=2$.  Un nombre « de $n$
-bits » signifie : inférieur à $2^n$.
+Écriture usuelle : $b=10$.  Informatique : $b=2$ (les chiffres portent
+alors le nom de \emph{bits}).  Un nombre « de $n$ bits » signifie :
+inférieur à $2^n$.
 
 Multiplier par $b$ revient à décaler tous les chiffres d'un cran vers
-la gauche.
+le poids fort (et mettre un $0$ comme nouveau chiffre de poids
+faible).
 
 %
 \subsection{Remarques sur la complexité des opérations}
@@ -117,11 +126,15 @@ Multiplication
 
 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 +
-[(a_1+a_0)(b_1+b_0)-a_1 b_1-a_0 b_0] w + a_0 b_0$ pour une complexité
-en $O(n^{\frac{\log 3}{\log 2}})$ (soit $O(n^{1.58\ldots})$).  Facile
-à implémenter.
+\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
++[(a_1+a_0)(b_1+b_0)-a_1 b_1-a_0 b_0] w + a_0 b_0$ (avec $a_0,a_1$ les
+moitiés de poids respectivement faible et fort des chiffres du nombre
+$A = a_1 w + a_0$ à multiplier et $b_0,b_1$ les moitiés de poids
+faible et fort du nombre $B = b_1 w + b_0$ ; ici, $w$ vaut $2^{n/2}$
+si on travaille en binaire sur des nombres de $n$ bits), pour une
+complexité en $O(n^{\frac{\log 3}{\log 2}})$ (soit
+$O(n^{1.58\ldots})$).  Facile à implémenter.
 
 \emph{Multiplication de Strassen} : par transformée de Fourier
 rapide, complexité en $O(n\,\log^2 n)$, difficile à implémenter.
@@ -161,15 +174,15 @@ Sur leur r
 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 »).  De façon
-équivalente : si $p$ est premier, alors le nombre premier qui le suit
-immédiatement est $<2p$.
+< 2x$ (\v Ceby\v sëv : « postulat de Bertrand », démontré en 1850).
+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
-Poussin : « théorème des nombres premiers »).  Moralement : la
-probabilité qu'un nombre de $n$ bits aléatoire soit premier est
-environ $\frac{1}{n\,\ln 2}$.
+Poussin : « théorème des nombres premiers », démontré en 1896).
+Moralement : la probabilité qu'un nombre de $n$ bits aléatoire soit
+premier est environ $\frac{1}{n\,\ln 2}$.
 
 Beaucoup de questions ouvertes.  Par exemple : Conjecture des nombres
 premiers jumeaux : existe-t-il une infinité de nombres premiers $p$
@@ -200,6 +213,11 @@ de donner un sens au produit infini.  Dire que $b|a$ signifie $v_p(b)
 
 Quant à $u$, c'est simplement le signe de $n$.
 
+Exemple : $7920 = 2^4\times 3^2\times 5\times 11$, c'est-à-dire que
+$v_2(7920)=4$, $v_3(7920)=2$, $v_5(7920)=1$, $v_7(7920)=0$,
+$v_{11}(7920)=1$, et $v_p(7920)=0$ pour n'importe quel nombre premier
+$p\geq 13$.
+
 %
 \subsection{Remarques sur la complexité}
 
@@ -241,6 +259,11 @@ v_p(x) + v_p(y)$
 $x \in \mathbb{Q}$ est entier signifie exactement $v_p(x) \geq 0$ pour
 tout $p$.
 
+Remarque : calculer $v_p(n)$, pour un $n$ donné et un $p$ premier
+donné, est facile.  Ce qui est difficile dans la décomposition en
+facteurs premiers, c'est de trouver tous les $p$ tels que $v_p(n) > 0$
+(ou en fait, en trouver \emph{un}).
+
 %
 \subsection{Division euclidienne}
 
@@ -262,6 +285,11 @@ division euclidienne de $a$ par
 Dire que $r=0$ signifie exactement que $b$ divise $a$ (la division
 euclidienne est alors \emph{exacte}).
 
+Exemple : le reste de la division euclidienne de $a$ (un entier
+quelconque) par $2$ vaut : $0$ lorsque $a$ est \emph{pair}, et $1$
+lorsque $a$ est \emph{impair} ; ce sont les seules deux valeurs
+possibles.
+
 \medbreak
 
 \textbf{Algorithme naïf :} (celui de l'école primaire) en $O(n^2)$.
@@ -333,6 +361,9 @@ Lorsque $\pgcd(m_1,\ldots,m_\ell)=1$, on dit que les $m_i$ sont
 Lorsque $\pgcd(m_i,m_j)=1$ pour tous $i\neq j$, on dit que les $m_i$
 sont premiers entre eux \emph{deux à deux}.
 
+Exemple : $6, 10, 15$ sont premiers entre eux dans leur ensemble, mais
+pas deux à deux.
+
 \textbf{Lemme de Gauß amélioré :} Si $m$ et $n$ sont premiers entre
 eux, être multiple de $m$ et de $n$ équivaut à être multiple de $mn$.
 
-- 
cgit v1.2.3