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