diff options
| -rw-r--r-- | rappels-maths.tex | 41 |
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 |