summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordavid <david>2009-10-21 17:36:47 +0000
committerdavid <david>2009-10-21 17:36:47 +0000
commited3a4451987146fb5f4decfb8b71552394405f9d (patch)
treeeaca8b1e41cef30785f4b5b62e590c9e05fa089b
parent1697a3dc5c8597aab3b07591944df44cfab310ff (diff)
downloadinfmdi720-ed3a4451987146fb5f4decfb8b71552394405f9d.zip
infmdi720-ed3a4451987146fb5f4decfb8b71552394405f9d.tar.gz
infmdi720-ed3a4451987146fb5f4decfb8b71552394405f9d.tar.bz2
Rewrite the section on integers.
-rw-r--r--rappels-maths.tex102
1 files changed, 61 insertions, 41 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex
index dfcad4b..338423d 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -41,7 +41,7 @@
\maketitle
{\footnotesize
\begin{center}
-CVS: \verb=$Id: rappels-maths.tex,v 1.13 2009-10-21 17:09:11 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.14 2009-10-21 17:36:47 david Exp $=
\end{center}
\par}
\pretolerance=10000
@@ -56,14 +56,35 @@ CVS: \verb=$Id: rappels-maths.tex,v 1.13 2009-10-21 17:09:11 david Exp $=
$\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ ensemble des
entiers relatifs. Sous-ensemble $\mathbb{N}$.
-Opérations : $+$, $\times$.
+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}
-Rappeler : $(\mathbb{Z},0,+)$ est un groupe abélien,
-$(\mathbb{Z},0,+,1,\times)$ est un anneau commutatif.
+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}.
-Mieux : anneau intègre (si $uv=0$ alors $u=0$ ou $v=0$).
+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 =
+0$).
-Éléments inversibles : $1$ et $-1$.
+Éléments inversibles : un \textbf{inversible} ou une \textbf{unité}
+(dans un anneau commutatif) est un élément $x$ tel qu'il existe $y$
+tel que $xy = 1$. Dans $\mathbb{Z}$, les inversibles sont $1$ et
+$-1$.
Relation d'ordre...
@@ -72,7 +93,9 @@ Relation d'ordre...
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 » (expliquer).
+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$).
Écriture usuelle : $b=10$. Informatique : $b=2$. Un nombre « de $n$
bits » signifie : inférieur à $2^n$.
@@ -80,8 +103,6 @@ bits » signifie : inférieur à $2^n$.
Multiplier par $b$ revient à décaler tous les chiffres d'un cran vers
la gauche.
-On passe pour l'instant sur l'écriture des nombres négatifs.
-
%
\subsection{Remarques sur la complexité des opérations}
@@ -89,7 +110,7 @@ Addition de nombres de $n$ bits : algorithme naïf en $O(n)$.
Multiplication : plus compliqué.
-Algorithme naïf en $O(n^2)$.
+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 +
@@ -105,9 +126,14 @@ complètement théorique.
%
\subsection{Divisiblité (exacte)}
-Définition. Terminologie « diviseur de », « multiple de ». Relation
-réflexive, transitive. Pas tout à fait antisymétrique (mais vrai dans
-les entiers naturels).
+Si $a$ et $b$ sont deux entiers, on dit que $b$ divise $a$, et on note
+$b|a$, lorsqu'il existe $q \in \mathbb{Z}$ tel que $a = bq$.
+
+Cette relation est réflexive (on a $a|a$ pour tout $a$) et transitive
+(si $b|a$ et $c|b$ alors $c|a$). Elle n'est pas tout à fait
+antisymétrique, mais c'est vrai dans les entiers naturels : si $a$ et
+$b$ sont des entiers naturels tels que $b|a$ et $a|b$ alors $b=a$
+(dans les entiers relatifs, on peut aussi avoir $b=-a$).
Note : Les entiers $1$ et $-1$ divisent tous les entiers. L'entier
$0$ est divisible par tous les entiers.
@@ -129,8 +155,10 @@ 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 »).
+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$.
Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à
$\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée
@@ -307,10 +335,10 @@ eux, être multiple de $m$ et de $n$ équivaut à être multiple de $mn$.
%
\subsection{PPCM}
-Définition analogue au PGCD. Exemple : le ppcm de $6$ et $10$
+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'entiers est défini, mais parfois surprenant (quel est le PPCM de
+d'entiers est défini, mais parfois surprenant (quel est le ppcm de
tous les nombres premiers ?).
%
@@ -340,7 +368,9 @@ 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$.
+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$).
%
\subsection{Algorithme d'Euclide}
@@ -397,30 +427,20 @@ nq+r$.
\textbf{Invariants :} $au+bv=m$ et $au'+bv'=n$.
-%
-\subsection{Exercices}
-
-\thingy Montrer que si $a, b \in \mathbb{Z}$ vérifient $a^2 = 2b^2$
-alors $a=b=0$. Comment interpréter ce résultat sur le
-nombre $\sqrt{2}$ ?
-
-\thingy Montrer que, si $n \geq 2$ alors $\sum_{i=1}^n \frac{1}{i}$
-n'est pas un entier. (Indication : montrer que sa valuation
-$2$-adique est strictement négative ; ou bien : montrer que sa
-valuation $p$-adique vaut $-1$ avec $p$ le plus grand nombre premier
-inférieur à $n$, en utilisant le postulat de Bertrand.)
-
-\thingy Montrer que, pour tout $p$ premier et $n$ entier naturel,
-$v_p(n!) = \sum_{i=i}^{+\infty} \lfloor\frac{n}{p^i}\rfloor$ (où
-$\lfloor\cdot\rfloor$ désigne la partie entière.
-
-\thingy Montrer que pour $a, b$ entiers, on a $\pgcd(a,b)\, \ppcm(a,b)
-= ab$.
+\smallbreak
-\thingy On définit par récurrence les nombres de Fibonacci : $F_0 =
-0$, $F_1 = 1$ et $F_{n+1} = F_n + F_{n-1}$. Écrire une relation de
-Bézout entre $F_8$ et $F_9$. Montrer que $F_n$ et $F_{n+1}$ sont
-premiers entre eux pour tout $n$.
+Dans la pratique, à la main, on procède ainsi : pour calculer une
+relation de Bézout entre $64$ et $47$, on effectue les divisions
+euclidiennes successives $64 = 1\times 47 + 17$, $47 = 2\times 17 +
+13$, $17 = 1\times 13 + 4$, $13 = 3\times 4 + 1$ jusqu'à tomber sur le
+reste $1$. Puis on réécrit ce reste en partant de la dernière
+division $1 = 13 - 3\times 4$ et en remplaçant successivement le reste
+de chaque division (les à l'envers) par une combinaison du dividende
+et du diviseur : $4 = 17 - 1\times 13$ donc $1 = 13 -
+3\times(17-1\times 13) = 4\times 13 - 3\times 17$ puis $13 = 47 -
+2\times 17$ donc $1 = 4\times (47 - 2\times 17) - 3\times 17 = 4\times
+47 - 11\times 17$ et enfin $17 = 1\times 64 - 47$ donc $1 = 4\times 47
+- 11\times (1\times 64 - 47) = 15\times 47 - 11\times 64$.
%
\section{Congruences et entiers modulaires}