diff options
| -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} |