diff options
| -rw-r--r-- | rappels-maths.tex | 132 |
1 files changed, 128 insertions, 4 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index dbb8889..5c06c59 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -40,7 +40,7 @@ \maketitle {\footnotesize \begin{center} -CVS: \verb=$Id: rappels-maths.tex,v 1.2 2008-09-29 21:40:25 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.3 2008-09-30 21:58:17 david Exp $= \end{center} \par} \pretolerance=10000 @@ -397,6 +397,31 @@ 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$. + +\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$. + +% \section{Congruences et entiers modulaires} \subsection{Congruence} @@ -501,8 +526,8 @@ on peut avoir $ab=\bar 0$ dans $\mathbb{Z}/m\mathbb{Z}$ alors que $a 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$. +préserve l'addition et la multiplication et envoie $0$ et $1$ sur +$\bar 0$ et $\bar 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 @@ -526,7 +551,106 @@ 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$. +Si $\bar a$ est inversible dans $\mathbb{Z}/m\mathbb{Z}$, on pourra +noter $\bar a^{-1}$ son inverse (qui est évidemment de nouveau +inversible...). On le calcule à partir d'une relation de Bézout. +Attention, il n'est pas évident de relier $\bar a^{-1}$ avec le +rationnel $1/a$ ! + +Exemple : dans $\mathbb{Z}/10\mathbb{Z}$, les éléments $\bar 1, \bar +3, \bar 7, \bar 9$ sont inversibles, et leurs inverses sont $\bar +1^{-1} = \bar 1, \bar 3^{-1} = \bar 7, \bar 7^{-1} = \bar 3, \bar +9^{-1} = \bar 9$. + +On note $\varphi(m)$ le cardinal de +$(\mathbb{Z}/m\mathbb{Z})^\times$ : la fonction $\varphi$ s'appelle +\emph{fonction indicatrice d'Euler} (exemple : $\varphi(10) = 4$). On +verra plus loin comment la calculer. + +Note : on a deux involutions importantes sur +$(\mathbb{Z}/m\mathbb{Z})^\times$ : l'une est $\bar a \mapsto -\bar +a$, et l'autre est $\bar a \mapsto \bar a^{-1}$. Comme la première +n'a pas de point fixe, $\varphi(m)$ est toujours \emph{pair} (sauf +pour $m=2$). + +Si $p$ est premier, alors tous les nombres entre $1$ et $p-1$ sont +premiers avec $p$ : $(\mathbb{Z}/p\mathbb{Z})^\times = \{\bar +1,\ldots, \overline{p-1}\}$ (et notamment $\varphi(p) = p-1$). Tous +les éléments de $\mathbb{Z}/p\mathbb{Z}$ sont inversibles sauf $\bar +0$ : on dit que l'anneau $\mathbb{Z}/p\mathbb{Z}$ est un \emph{corps} +et on le note $\mathbb{F}_p$. + +% +\subsection{Théorème chinois} + +Si $m$ et $n$ sont deux naturels non nuls \textbf{premiers entre eux}, +considérons l'application dont les composantes sont les deux +surjections canoniques : +\[ +\mathbb{Z}/(mn)\mathbb{Z} \to (\mathbb{Z}/m\mathbb{Z}) +\times (\mathbb{Z}/n\mathbb{Z}) +\] + +Il s'agit d'un \emph{morphisme d'anneaux} (car les surjections +canoniques en sont !) : +\begin{itemize} +\item il est injectif car un entier multiple de $m$ et de $n$ +est multiple de $mn$ (lemme de Gauß), +\item il est surjectif car les cardinaux coïncident ($mn$ au départ et +à l'arrivée), +\end{itemize} +c'est donc un \textbf{isomorphisme}. + +Dresser la table d'isomorphisme de $\mathbb{Z}/10\mathbb{Z}$ avec +$(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z})$... + +% +\subsection{Théorème chinois explicite} + +Si on a une relation de Bézout $um+vn=1$, alors l'isomorphisme chinois +a pour réciproque +\[ +\begin{array}{c} +(\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \to +\mathbb{Z}/(mn)\mathbb{Z}\\ +(x,y) \mapsto umy+vnx\\ +\end{array} +\] + +Exemple : trouver le nombre entre $0$ et $100$ congru à $9$ +modulo $11$ et à $3$ modulo $13$. (Relation de Bézout : $6\times 11 - +5 \times 13 = 1$ ; ensuite, $6 \times 11 \times 3 - 5 \times 13 \times +9 \equiv 5\times 11 - 1\times 13 \equiv 42 \pmod{11\times 13}$.) + +\medskip + +Plus généralement, connaissant la classe d'un entier modulo +$m_1,\ldots,m_k$, on peut retrouver sa classe modulo +$\ppcm(m_1,\ldots,m_k)$. + +% +\subsection{Calcul de l'indicatrice d'Euler} + +Si $m$ et $n$ (naturels non nuls) sont premiers entre eux, par le +théorème chinois on a $(\mathbb{Z}/(mn)\mathbb{Z})^\times \cong +(\mathbb{Z}/m\mathbb{Z})^\times \times +(\mathbb{Z}/n\mathbb{Z})^\times$, donc +\[ +\varphi(mn) = \varphi(m)\,\varphi(n) +\] + +Si $p$ est premier alors $\varphi(p^r) = (p-1)\,p^{r-1}$ (car être +premier avec $p^r$ équivaut à être premier à $p$, et c'est le cas de +$p-1$ entiers sur $p$). + +On en déduit : +\[ +\varphi(n) = n\,\prod_{p|n}\left(1-\frac{1}{p}\right) +\] +où $p$ parcourt les premiers divisant $n$. + +\textbf{Algorithmiquement :} \emph{lent} en général (demande de +connaître la d.f.p.). % % |