summaryrefslogtreecommitdiffstats
path: root/rappels-maths.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2011-09-27 18:07:55 +0200
committerDavid A. Madore <david+git@madore.org>2011-09-27 18:07:55 +0200
commit21bd01d5abb493044b51eb66c9ac21555a5af691 (patch)
tree01683927c3d70cec83848755da865a1490650823 /rappels-maths.tex
parent6fee09df2501c25c667958f733c3701113a08ad8 (diff)
downloadinfmdi720-21bd01d5abb493044b51eb66c9ac21555a5af691.tar.gz
infmdi720-21bd01d5abb493044b51eb66c9ac21555a5af691.tar.bz2
infmdi720-21bd01d5abb493044b51eb66c9ac21555a5af691.zip
Additions/clarifications/corrections.
Diffstat (limited to 'rappels-maths.tex')
-rw-r--r--rappels-maths.tex41
1 files changed, 30 insertions, 11 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex
index 60660fd..15c307f 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -356,11 +356,16 @@ entiers est $0$),
\subsection{Entiers premiers entre eux}
Lorsque $\pgcd(m_1,\ldots,m_\ell)=1$, on dit que les $m_i$ sont
-\textbf{premiers entre eux} \emph{dans leur ensemble}.
+\textbf{premiers entre eux} \emph{dans leur ensemble}. Cela signifie
+qu'il n'existe aucun nombre premier (ou : aucun nombre autre que $\pm
+1$) qui divise tous les $m_i$ à la fois.
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}.
+Bien entendu, pour seulement deux nombres, ces définitions coïncident,
+et on dit simplement qu'ils sont premiers entre eux.
+
Exemple : $6, 10, 15$ sont premiers entre eux dans leur ensemble, mais
pas deux à deux.
@@ -368,17 +373,27 @@ pas deux à deux.
eux, être multiple de $m$ et de $n$ équivaut à être multiple de $mn$.
\textbf{Dirichlet :} La probabilité pour que deux entiers « tirés au
- hasard » soient premiers entre eux est $\frac{6}{\pi^2}$.
+ hasard » soient premiers entre eux est $\frac{6}{\pi^2}$
+(c'est-à-dire que la probabilité que deux entiers tirés au hasard
+entre $0$ et $N-1$ soient premiers entre eux tend vers
+$\frac{6}{\pi^2}$ quand $N \to +\infty$).
%
\subsection{PPCM}
-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éfinition analogue au pgcd (un ppcm de $m_1,\ldots,m_\ell$ est un
+multiple commun à tous les $m_i$ qui divise n'importe quel autre
+multiple commun ; par convention, on prend celui qui est positif).
+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) : $v_p(\ppcm(m_1,\ldots,m_\ell)) =
+\max(v_p(m_1),\ldots,v_p(m_\ell))$. Le ppcm d'une famille infinie
d'entiers est défini, mais parfois surprenant (quel est le ppcm de
tous les nombres premiers ?).
+Remarque : pour deux nombres, on a $\ppcm(m,m') \times \pgcd(m,m') =
+|mm'|$.
+
%
\subsection{Relation de Bézout}
@@ -406,9 +421,10 @@ 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$ (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$).
+tels que $au+bv = d$ (en fait, il existe $d',d''$ avec $d=d'd''$ tels
+que $a/d'$ et $b/d''$ soient premiers entre eux, et si
+$(a/d')u_0+(b/d'')v_0 = 1$ est une relation de Bézout entre eux, alors
+on a $a(d''u_0)+b(d'v_0) = d$).
%
\subsection{Algorithme d'Euclide}
@@ -494,6 +510,9 @@ Si $x$ et $x'$ sont entiers, on dit que $x$ et $x'$ sont
$x-x'$ est multiple de $m$. Relation réflexive, symétrique,
transitive.
+Dire $x \equiv 0 \pmod{m}$ signifie simplement que $x$ est multiple
+de $m$.
+
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
@@ -719,9 +738,9 @@ Généralisations du théorème chinois :
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).
+ $\ppcm(m,n)$ (pour faire le calcul en pratique, diviser les nombres
+ $m,n$ par $d',d''$ tels que $d'd''=d$ pour se ramener à deux nombres
+ $m/d'$ et $n/d''$ 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