diff options
Diffstat (limited to 'rappels-maths.tex')
| -rw-r--r-- | rappels-maths.tex | 162 |
1 files changed, 158 insertions, 4 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index badb046..dbb8889 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -29,6 +29,7 @@ \newcommand{\pgcd}{\operatorname{pgcd}} \newcommand{\ppcm}{\operatorname{ppcm}} \newcommand{\signe}{\operatorname{signe}} +\newcommand{\tee}{\mathbin{\top}} \renewcommand{\qedsymbol}{\smiley} % % @@ -39,7 +40,7 @@ \maketitle {\footnotesize \begin{center} -CVS: \verb=$Id: rappels-maths.tex,v 1.1 2008-09-29 18:58:04 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.2 2008-09-29 21:40:25 david Exp $= \end{center} \par} \pretolerance=10000 @@ -103,8 +104,9 @@ complètement théorique. % \subsection{Divisiblité (exacte)} -Définition. Réflexive, transitive. Pas tout à fait antisymétrique -(mais vrai dans les entiers naturels). +Définition. Terminologie « diviseur de », « multiple de ». Relation +réflexive, transitive. Pas tout à fait antisymétrique (mais vrai dans +les entiers naturels). Note : Les entiers $1$ et $-1$ divisent tous les entiers. L'entier $0$ est divisible par tous les entiers. @@ -116,6 +118,12 @@ Un \textbf{nombre premier} $p$ est un entier (par convention : positif) divisible seulement par $1$, $-1$, lui-même et son opposé ; mais par convention, $1$ et $-1$ (et $0$...) ne sont pas premiers. +Les premiers nombres premiers sont donc : $2$, $3$, $5$, $7$, $11$, +$13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$, +$59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$, $97$... + +\medbreak + Sur leur répartition : Il y en a une infinité (Euclide). @@ -125,7 +133,16 @@ $x\leq p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand »). 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 »). +Poussin : « théorème des nombres premiers »). Moralement : la +probabilité qu'un nombre de $n$ bits aléatoire soit premier est +environ $n\,\ln 2$. + +Beaucoup de questions ouvertes. Par exemple : Conjecture des nombres +premiers jumeaux : existe-t-il une infinité de nombres premiers $p$ +tels que $p+2$ soit aussi premier (tels que $3$, $5$, $11$, $17$, +$29$, $41$, $59$, $71$...) ? + +\smallbreak \textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors $p$ divise $a$ ou $p$ divise $b$. @@ -319,6 +336,11 @@ relation de Bézout entre $a$ et $b$. Donc il n'y a pas unicité. Si $au + bv = \pm 1$ on dit parfois que les rationnels $a/b$ et $-v/u$ (écrits sous forme irréductible) sont \emph{adjacents}. +\medbreak + +Plus généralement, si $\pgcd(a,b) = d$, on peut trouver $u$ et $v$ +tels que $au+bv = d$. + % \subsection{Algorithme d'Euclide} @@ -375,6 +397,138 @@ nq+r$. \textbf{Invariants :} $au+bv=m$ et $au'+bv'=n$. % +\section{Congruences et entiers modulaires} + +\subsection{Congruence} + +Soit $m$ un entier fixé pour le moment : + +Si $x$ et $x'$ sont entiers, on dit que $x$ et $x'$ sont +\textbf{congrus} modulo $m$, noté $x \equiv x' \pmod{m}$, lorsque +$x-x'$ est multiple de $m$. Relation réflexive, symétrique, +transitive. + +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 +x' \pmod{m}$ (la congruence modulo $m'$ est \emph{plus fine} que +modulo $m$). + +Représentants : si $m \geq 1$ alors chaque entier est congru +modulo $m$ à l'un des nombres $0,1,2,\ldots,(m-1)$ (le reste de sa +division euclidienne par $m$ !). + +Exemple de $\mathbb{Z}/2\mathbb{Z}$ avec pair=$\bar 0$ et impair=$\bar +1$. + +On veut définir $\mathbb{Z}/m\mathbb{Z} = \{\bar 0, \bar 1, \bar 2, +\ldots, \overline{m-1}\}$ de façon analogue : pour ajouter $\bar x$ et +$\bar y$, on consière $\bar x + \bar y = \overline{x+y}$ et $\bar x\, +\bar y = \overline{xy}$. Reste à savoir ce que la barre veut dire ! + +% +\subsection{Généralité sur les quotients} + +Généralité : soit $E$ un ensemble et $\sim$ une relation d'équivalence +(i.e., réflexive, symétrique, transitive) sur $E$, on appelle +$E/{\sim}$ l'ensemble des classes d'équivalence de $E$ modulo $\sim$ +(la classe d'équivalence d'un élément $x\in E$ est l'ensemble des +éléments $x'\in E$ tels que $x\sim x'$). On note $\pi \colon E \to +(E/{\sim})$ la fonction qui envoie $x\in E$ sur sa classe +d'équivalence $\pi(x) = \bar x$. Ainsi : $\pi(x) = \pi(x')$ ssi $x +\sim x'$. (Moralement : on a transformé la relation d'équivalence +$\sim$ en une vraie égalité.) + +Si on a sur $E$ une opération binaire, disons, $\tee$, telle que $x +\sim x'$ et $y \sim y'$ impliquent $(x\tee x') \sim (y\tee y')$ (on +dit que $\sim$ est \emph{compatible} avec l'opération $\tee$), alors +on peut définir une opération binaire $\mathbin{\bar\top}$ sur +$E/{\sim}$ par $\pi(x) \mathbin{\bar\top} \pi(x') = \pi(x\tee x')$. + +L'application $\pi\colon E \to (E/{\sim})$ préserve alors l'opération +$\tee$ et on dit qu'il s'agit d'un \emph{morphisme} (d'ensembles munis +d'une opération binaire $\tee$). + +% +\subsection{Calculs dans $\mathbb{Z}/m\mathbb{Z}$} + +Vision concrète de $\mathbb{Z}/m\mathbb{Z}$ pour $m\geq 1$ : on +travaille avec les nombres $0,\ldots,m-1$ (qui sont des +\emph{représentants} arbitraires des $m$ classes de congruences +modulo $m$). Les opérations sont faites dans les entiers mais ensuite +on se ramène à une classe représentée par un entier entre $0$ et $m-1$ +en effectuant une division euclidienne par $m$. + +Exemple : si $m=10$, on a $\bar 8 + \bar 5 = \bar 3$ et $\bar 8 \times +\bar 5 = \bar 0$. + +(Note : en fait, pour l'addition, il suffit de soustraire +éventuellement $m$ si le résultat l'excède : pas besoin de faire une +vraie division euclidienne.) + +Les ordinateurs travaillent naturellement dans +$\mathbb{Z}/2^r\mathbb{Z}$ avec $r$ valant typiquement $16$, $32$ ou +$64$. + +Note importante : Le choix des représentants $0,\ldots,m-1$ est +arbitraire : on pourrait tout aussi bien choisir $1,\ldots,m$ ou bien +$-\lfloor\frac{m-1}{2}\rfloor,\ldots,\lfloor\frac{m}{2}\rfloor$ (ou +encore des choses tout à fait arbitraires). + +\medbreak + +Et si $m\leq 1$ ? +\begin{itemize} +\item On a $\mathbb{Z}/1\mathbb{Z} = \{\bar 0\}$, et les opérations + sont triviales ($\bar 0 + \bar 0 = \bar 0$ et $\bar 0 \times \bar 0 + = \bar 0$). +\item On a $\mathbb{Z}/0\mathbb{Z} = \mathbb{Z}$. +\item Si $m<0$ alors $\mathbb{Z}/m\mathbb{Z} = + \mathbb{Z}/(-m)\mathbb{Z}$. +\end{itemize} + +En général quand on parle de $\mathbb{Z}/m\mathbb{Z}$ on sous-entend +$m\geq 1$, parfois même $m \geq 2$ ! + +% +\subsection{Premières propriétés de $\mathbb{Z}/m\mathbb{Z}$} + +C'est un anneau commutatif. Il n'est \emph{pas intègre} en général : +on peut avoir $ab=\bar 0$ dans $\mathbb{Z}/m\mathbb{Z}$ alors que $a +\neq \bar 0$ et $b \neq \bar 0$ (exemple : $\bar 2 \times \bar 5 = +\bar 0$ dans $\mathbb{Z}/10\mathbb{Z}$). + +Surjection canonique : c'est l'application $\pi\colon \mathbb{Z} \to +\mathbb{Z}/m\mathbb{Z}$ qui envoie $x\in\mathbb{Z}$ sur sa classe de +congruence modulo $m$. C'est un \emph{morphisme d'anneaux}, i.e., il +préserve l'addition et la multiplication et envoie $0$ et $1$ sur $0$ +et $1$. + +Si $m|m'$, il y a une application naturelle $\mathbb{Z}/m'\mathbb{Z} +\to \mathbb{Z}/m\mathbb{Z}$ car les classes modulo $m'$ sont plus +fines que modulo $m$. (Exemple : connaître la congruence modulo $4$ +permet de connaître la congruence modulo $2$.) C'est également un +morphisme d'anneaux. + +% +\subsection{Inversibles de $\mathbb{Z}/m\mathbb{Z}$} + +Si $a$ et $m$ sont premiers entre eux, alors on sait qu'on peut +trouver une relation de Bézout $au + mv = 1$. On a alors $\bar a \bar +u = \bar 1$ : on dit que $\bar a$ est \emph{(multiplicativement) + inversible} dans $\mathbb{Z}/m\mathbb{Z}$, ou est une \emph{unité} +de cet anneau. Réciproquement, si on peut trouver $\bar u$ tel que +$\bar a \bar u = \bar 1$, alors $a$ est premier à $m$. + +On appelle $(\mathbb{Z}/m\mathbb{Z})^\times$ l'ensemble des +inversibles multiplicatifs de $\mathbb{Z}/m\mathbb{Z}$. C'est un +groupe pour la multiplication (plus généralement, dans tout anneau +commutatif $A$, l'ensemble des inversibles/unités de $A$ forme un +groupe noté $A^\times$). + +On note $\varphi(m)$ le cardinal de $(\mathbb{Z}/m\mathbb{Z})^\times$. + +% % % \end{document} |