diff options
| -rw-r--r-- | rappels-maths.tex | 113 |
1 files changed, 72 insertions, 41 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index 56bd174..60660fd 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -56,29 +56,33 @@ Git: \input{vcline.tex} \subsection{L'anneau des entiers} -$\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ ensemble des -entiers relatifs. Sous-ensemble $\mathbb{N}$. - -Opérations : $+$, $\times$ ; éléments remarquables : $0$, $1$. -Vérifient les propriétés suivantes : -\begin{itemize} -\item Associativité de $+$ : $x+(y+z) = (x+y)+z$ -\item Neutralité de $0$ pour $+$ : $0+x = x+0 = x$ -\item Existence d'opposés : (pour chaque $x$, il existe un élément - noté $-x$ tel que) $x + (-x) = (-x) + x = 0$ -\item Commutativité de $+$ : $y+x = x+y$ -\item Distributivité de $\times$ sur $+$ : $x(y+z) = xy + xz$ -\item Associativité de $\times$ : $x(yz) = (xy)z$ -\item Neutralité de $1$ pour $\times$ : $1x = x1 = x$ -\item Commutativité de $\times$ : $yx = xy$ -\end{itemize} - -Les trois premières propriétés signifient que $\mathbb{Z}$ est un -\emph{groupe} pour l'addition ; les quatre premières, que $\mathbb{Z}$ -est un \emph{groupe abélien} pour l'addition ; les sept premières -propriétés signifient que $\mathbb{Z}$ est un \emph{anneau} ; les huit -propriétés réunies signifient que $\mathbb{Z}$ est un \textbf{anneau - commutatif}. +On appelle $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ l'ensemble +des entiers relatifs. Il a pour sous-ensemble $\mathbb{N} = +\{0,1,2,3,\ldots\}$ l'ensemble des entiers naturels (ou positifs). + +Sur $\mathbb{Z}$ on a les opérations : $+$ (addition) et $\times$ +(multiplication) ; et les éléments remarquables : $0$, $1$. Ces +données vérifient les propriétés suivantes : +\begin{enumerate} +\item Associativité de l'addition : $x+(y+z) = (x+y)+z$ +\item Neutralité de zéro pour l'addition : $0+x = x+0 = x$ +\item Existence d'opposés (=symétriques pour l'addition) : (pour + chaque $x$, il existe un élément noté $-x$ tel que) $x + (-x) = (-x) + + x = 0$ +\item Commutativité de l'addition : $y+x = x+y$ +\item Distributivité de la multiplication sur l'addition : $x(y+z) = + xy + xz$ et $(x+y)z=xz+yz$ +\item Associativité de la multiplication : $x(yz) = (xy)z$ +\item Neutralité de un pour la multiplication : $1x = x1 = x$ +\item Commutativité de la multiplication : $yx = xy$ +\end{enumerate} + +Les trois premières propriétés traduisent le fait que $\mathbb{Z}$ est +un \emph{groupe} pour l'addition ; les quatre premières, que +$\mathbb{Z}$ est un \emph{groupe abélien} pour l'addition ; les sept +premières propriétés traduisent le fait que $\mathbb{Z}$ est un +\emph{anneau} ; les huit propriétés réunies traduisent le fait que +$\mathbb{Z}$ est un \textbf{anneau commutatif}. Mieux : c'est un \emph{anneau intègre} : si $uv=0$ alors $u=0$ ou $v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 = @@ -89,9 +93,10 @@ $v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 = tel que $xy = 1$. Dans $\mathbb{Z}$, les inversibles sont $1$ et $-1$. -Relation d'ordre : relation réflexive (on a toujours $x\leq x$), -antisymétrique (si $x\leq y$ et $y\leq x$ alors $x=y$) et transitive -(si $x\leq y$ et $y\leq z$ alors $x\leq z$). +On a aussi sur $\mathbb{Z}$ une relation d'ordre : c'est-à-dire une +relation réflexive (on a toujours $x\leq x$), antisymétrique (si +$x\leq y$ et $y\leq x$ alors $x=y$) et transitive (si $x\leq y$ et +$y\leq z$ alors $x\leq z$). % \subsection{Écriture $b$-adique} @@ -100,13 +105,17 @@ Si $b\geq 2$ est un entier naturel, tout entier naturel $A$ s'écrit de façon unique $A = \sum_{i=0}^{+\infty} a_i b^i$ avec $0\leq a_i<b$ entiers naturels « presque tous nuls » (c'est-à-dire nuls sauf un nombre fini : donc la somme peut en fait s'écrire $A = -\sum_{i=0}^{n-1} a_i b^i$). +\sum_{i=0}^{n-1} a_i b^i$). Les $a_i$ s'appellent les \emph{chiffres} +de cette écriture $b$-adique, $a_0$ s'appelant le chiffre des +\emph{unités} ou chiffre \emph{de poids faible}. -Écriture usuelle : $b=10$. Informatique : $b=2$. Un nombre « de $n$ -bits » signifie : inférieur à $2^n$. +Écriture usuelle : $b=10$. Informatique : $b=2$ (les chiffres portent +alors le nom de \emph{bits}). Un nombre « de $n$ bits » signifie : +inférieur à $2^n$. Multiplier par $b$ revient à décaler tous les chiffres d'un cran vers -la gauche. +le poids fort (et mettre un $0$ comme nouveau chiffre de poids +faible). % \subsection{Remarques sur la complexité des opérations} @@ -117,11 +126,15 @@ Multiplication : plus compliqué. Algorithme naïf en $O(n^2)$ (appris à l'école primaire). -\emph{Multiplication de Karatsuba} : utilise récursivement -l'identité ${(a_1 w + a_0)} \penalty0 {(b_1 w + b_0)} = a_1 b_1 w^2 + -[(a_1+a_0)(b_1+b_0)-a_1 b_1-a_0 b_0] w + a_0 b_0$ pour une complexité -en $O(n^{\frac{\log 3}{\log 2}})$ (soit $O(n^{1.58\ldots})$). Facile -à implémenter. +\emph{Multiplication de Karatsuba} : utilise récursivement l'identité +${(a_1 w + a_0)} \penalty0 {(b_1 w + b_0)} = a_1 b_1 w^2 ++[(a_1+a_0)(b_1+b_0)-a_1 b_1-a_0 b_0] w + a_0 b_0$ (avec $a_0,a_1$ les +moitiés de poids respectivement faible et fort des chiffres du nombre +$A = a_1 w + a_0$ à multiplier et $b_0,b_1$ les moitiés de poids +faible et fort du nombre $B = b_1 w + b_0$ ; ici, $w$ vaut $2^{n/2}$ +si on travaille en binaire sur des nombres de $n$ bits), pour une +complexité en $O(n^{\frac{\log 3}{\log 2}})$ (soit +$O(n^{1.58\ldots})$). Facile à implémenter. \emph{Multiplication de Strassen} : par transformée de Fourier rapide, complexité en $O(n\,\log^2 n)$, difficile à implémenter. @@ -161,15 +174,15 @@ Sur leur répartition : Il y en a une infinité (Euclide). Pour tout $x>1$, il y a toujours un nombre premier $p$ tel que $x < p -< 2x$ (\v Ceby\v sëv : « postulat de Bertrand »). De façon -équivalente : si $p$ est premier, alors le nombre premier qui le suit -immédiatement est $<2p$. +< 2x$ (\v Ceby\v sëv : « postulat de Bertrand », démontré en 1850). +De façon équivalente : si $p$ est premier, alors le nombre premier qui +le suit immédiatement est $<2p$. 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 »). Moralement : la -probabilité qu'un nombre de $n$ bits aléatoire soit premier est -environ $\frac{1}{n\,\ln 2}$. +Poussin : « théorème des nombres premiers », démontré en 1896). +Moralement : la probabilité qu'un nombre de $n$ bits aléatoire soit +premier est environ $\frac{1}{n\,\ln 2}$. Beaucoup de questions ouvertes. Par exemple : Conjecture des nombres premiers jumeaux : existe-t-il une infinité de nombres premiers $p$ @@ -200,6 +213,11 @@ de donner un sens au produit infini. Dire que $b|a$ signifie $v_p(b) Quant à $u$, c'est simplement le signe de $n$. +Exemple : $7920 = 2^4\times 3^2\times 5\times 11$, c'est-à-dire que +$v_2(7920)=4$, $v_3(7920)=2$, $v_5(7920)=1$, $v_7(7920)=0$, +$v_{11}(7920)=1$, et $v_p(7920)=0$ pour n'importe quel nombre premier +$p\geq 13$. + % \subsection{Remarques sur la complexité} @@ -241,6 +259,11 @@ v_p(x) + v_p(y)$ ; inégalité sur la somme : on a $v_p(x+y) \geq $x \in \mathbb{Q}$ est entier signifie exactement $v_p(x) \geq 0$ pour tout $p$. +Remarque : calculer $v_p(n)$, pour un $n$ donné et un $p$ premier +donné, est facile. Ce qui est difficile dans la décomposition en +facteurs premiers, c'est de trouver tous les $p$ tels que $v_p(n) > 0$ +(ou en fait, en trouver \emph{un}). + % \subsection{Division euclidienne} @@ -262,6 +285,11 @@ division euclidienne de $a$ par $b$. Dire que $r=0$ signifie exactement que $b$ divise $a$ (la division euclidienne est alors \emph{exacte}). +Exemple : le reste de la division euclidienne de $a$ (un entier +quelconque) par $2$ vaut : $0$ lorsque $a$ est \emph{pair}, et $1$ +lorsque $a$ est \emph{impair} ; ce sont les seules deux valeurs +possibles. + \medbreak \textbf{Algorithme naïf :} (celui de l'école primaire) en $O(n^2)$. @@ -333,6 +361,9 @@ Lorsque $\pgcd(m_1,\ldots,m_\ell)=1$, on dit que les $m_i$ sont 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}. +Exemple : $6, 10, 15$ sont premiers entre eux dans leur ensemble, mais +pas deux à deux. + \textbf{Lemme de Gauß amélioré :} Si $m$ et $n$ sont premiers entre eux, être multiple de $m$ et de $n$ équivaut à être multiple de $mn$. |