summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-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