diff options
| -rw-r--r-- | rappels-maths.tex | 102 |
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} |