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 |