diff options
| -rw-r--r-- | rappels-maths.tex | 203 |
1 files changed, 202 insertions, 1 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index 13cb112..ed3d328 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.4 2008-10-07 10:04:22 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.5 2008-10-14 11:04:11 david Exp $= \end{center} \par} \pretolerance=10000 @@ -783,10 +783,211 @@ cyclique (auquel cas ses générateurs s'appellent éléments % \subsection{Exercices} +\thingy Que vaut $10^{1000}$ modulo $7$ ? (Réponse : $4$.) Que vaut +$10^{1000}$ modulo $6$ ? (Réponse : $4$.) Que vaut $10^{10^{1000}}$ +modulo $7$ ? (Réponse : toujours $4$.) + +\thingy Quels sont les deux derniers chiffres (en base $10$) de +$2^{1000!}$ ? + \thingy Montrer que pour tout $a\in \mathbb{Z}$ on a $a^{1729} \equiv a \pmod{1729}$ (indication : $1729 = 7\times 13 \times 19$ ; utiliser le théorème chinois). +\thingy À quoi est isomorphe le groupe +$(\mathbb{Z}/56\mathbb{Z})^\times$ ? Quel est le plus grand ordre +possible d'un élément de ce groupe ? + +\thingy \textbf{Théorème de Wilson :} $p$ est premier si, et seulement +si, $(p-1)! \equiv -1 \pmod{p}$. + +\thingy \textbf{Théorème de Wolstenholme :} si $p\geq 5$ est premier, +le numérateur de +$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$ est +divisible par $p^2$. (Indications : on pourra regrouper $\frac{1}{k}$ +et $\frac{1}{p-k}$, diviser par $p$, et chercher à étudier une +congruence modulo $p$ ; on pourra faire usage du fait que +$1^2+2^2+3^2+\cdots+(p-1)^2 = \frac{1}{6}p(p-1)(2p-1)$.) + +% +\section{Polynômes} + +\subsection{Définition, structure d'anneau et degré} + +Soit $k$ un anneau commutatif quelconque, typiquement un corps +(exemples importants : $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ ou bien +$\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$). + +Un \textbf{polynôme} en $t$ à coefficients dans $k$ est une somme +formelle $f = a_0 + a_1 t + a_2 t^2 + \cdots$ avec $a_i \in k$ où +\emph{seul un nombre fini} des $a_i$ est non nul (sinon on parle de +\textbf{série formelle}). + +\textbf{Opérations :} +\begin{itemize} +\item Addition : terme à terme ($c_i = a_i+b_i$). +\item Multiplication : « produit de Cauchy » en développant +formellement ($c_i = \sum_{j=0}^{j=i} a_j b_{i-j}$). +\end{itemize} + +Si $k$ est un anneau commutatif, alors $k[t]$ aussi. + +\textbf{Degré} d'un polynôme : $\deg f =$ le plus grand $i$ tel que +$a_i \neq 0$ (le degré du polynôme nul est question de convention). +On peut donc écrire un polynôme de degré $\leq N$ comme $a_0 + \cdots ++ a_N t^N$ ; si $a_N = 1$ on dit que $f$ est \textbf{unitaire}. + +\textbf{Propriétés} du degré : +\begin{itemize} +\item $\deg (f+g) \leq \max(\deg f, \deg g)$ (avec égalité si $\deg f +\neq \deg g$) +\item $\deg (fg) = \deg f + \deg g$ (dès que $k$ est \emph{intègre}, + en particulier sur un corps) +\end{itemize} + +Si $k$ est un anneau commutatif intègre, alors $k[t]$ aussi. + +Attention, $k[t]$ n'est jamais un corps ! (Car $t$ n'a pas d'inverse +pour la multiplication.) + +\medbreak + +À souligner : \emph{analogie} importante entre les polyômes, notamment +dans $\mathbb{F}_p[t]$, et l'écriture en base $p$ des entiers. +Différence importante : pas de retenue pour les polynômes. + +Complexité des opérations : cf. entiers. + +% +\subsection{Opérations spécifiques aux polynômes} + +\textbf{Évaluation} de polynômes : si $f = a_0 + \cdots + a_N t^N$ et +$x \in A$ (une $k$-algèbre, par exemple $k$ ou $k[t]$), on définit +$f(x) = a_0 + \cdots + a_N x^N$. + +Cas particulier : \textbf{composition} : si $g \in k[t]$, on note +$f\circ g$ plutôt que $f(g)$. + +\medbreak +\textbf{Dérivée :} si $f = a_0 + a_1 t + \cdots + a_N t^N$ alors $f' = +a_1 + 2 a_2 t + \cdots + N a_N t^{N-1}$. + +\textbf{Attention :} On peut avoir $f'=0$ sans avoir $f$ constant +(e.g., $f = t^p$ dans $\mathbb{F}_p[t]$). + +\textbf{Dérivées successives :} $f^{(i+1)} = (f^{(i)})'$ pour $i \in +\mathbb{N}$. + +% +\subsection{Polynôme interpolateur, formule de Taylor} + +Dans cette section, soit $k$ un \emph{corps} et $f \in k[t]$. + +\medskip + +Soient $a_0,\ldots,a_N +\in k$ deux à deux distincts, où $N \geq \deg f$, et $b_i = f(a_i)$, +alors +\[ +f = \sum_{i=0}^N b_i \frac{\prod_{j\neq i}(t-a_j)}{\prod_{j\neq i}(a_i-a_j)} +\] + +Permet de reconstruire un polynôme à partir de ses valeurs en +suffisamment de points. + +\medbreak + +Si $N \geq \deg f$ et $N!$ n'est pas nul dans $k$, alors pour tout +$a\in k$ : +\[ +f = f(a) + (t-a)\,f'(a) + \frac{(t-a)^2}{2}\,f''(a) + +\cdots + \frac{(t-a)^N}{N!}\,f^{(N)}(a) +\] + +Permet de reconstruire un polynôme à partir de ses dérivées +successives en un point. + +% +\subsection{Division euclidienne de polynômes} + +Sauf mention du contraire, $k$ est maintenant un \textbf{corps}. + +\smallskip + +\textbf{Division euclidienne} analogue à celle des entiers : + +Si $f\in k[t]$ et $g\in k[t]$ est \emph{non nul}, +il existe un unique couple $(q,r)$ tel que : +\begin{itemize} +\item $q \in k[t]$, +\item $r \in k[t]$ est (nul ou) de degré $\deg r < \deg g$ et +\item $f = gq + r$. +\end{itemize} + +\medbreak + +\textbf{Algorithme « naïf »} de division euclidienne : procéder par +puissances \emph{décroissantes} : + +Soit $f = a_N t^N + \cdots + a_0$ et $g = b_D t^D + \cdots + b_0$ où +$b_D \neq 0$ (donc $\deg g = D$) : +\begin{itemize} +\item si $N<D$ on renvoie $q = 0$ et $r = f$ ; +\item sinon, on pose $c = a_N/b_D$, on définit $f^* = f - c t^{N-D} +g$, donc $\deg(f^*) < N$, on applique l'algorithme pour diviser $f^*$ +par $g$, soit $f^* = gq^* + r$ et on a $f = gq + r$ où $q = c t^{N-D} ++ q^*$. +\end{itemize} + +\smallbreak + +\textbf{Cas très important :} Le reste de la division euclidienne de +$f$ par $t-a$ (où $a \in k$ est une constante) est $f(a)$. +(Pourquoi ?) + +\smallbreak + +\textbf{Exercice :} Effectuer la division euclidienne de $t^7$ par $2 +t^3+1$ dans $\mathbb{F}_7[t]$. (Réponse : $t^7 = (2 t^3+1) (4 t^4 + 5 +t) + 2 t$.) + +% +\subsection{Arithmétique des polynômes} + +Relation de \textbf{divisibilité} : exactement analogue aux entiers. +Les \textbf{unités} de $k[t]$ sont les éléments de $k^\times$ +(polynômes constants non nuls). + +Polynômes \textbf{irréductibles} : définition analogue aux nombres +premiers. On les choisira normalement \emph{unitaires} ; par +convention, $0$ et les constantes ne sont pas irréductibles. Les +polynômes $t-a$ (unitaires de degré $1$) sont \emph{toujours} +irréductibles. Lorsque ce sont les seuls, le corps $k$ est dit +\emph{algébriquement clos}. + +Le corps $\mathbb{C}$ est algébriquement clos. Le corps $\mathbb{R}$ +ne l'est pas : les polynômes irréductibles sur $\mathbb{R}$ sont les +$t-a$ et les $t^2-2bt+c$ où $b^2-c<0$. Les corps finis (notamment +$\mathbb{F}_p$ déjà vu) ne sont pas algébriquement clos (« encore + moins » que $\mathbb{R}$). + +\medbreak + +\textbf{Décomposition en facteurs irréductibles :} Écriture unique de +tout $f\in k[t]$ non nul comme $c \prod_P P^{v_P(f)}$ où $c \in +k^\times$ est le coefficient dominant de $f$ et $v_P(f)\in \mathbb{N}$ +pour tout $P$ irréductible (presque tous nuls). + +Cas où $k$ est algébriquement clos : tout $f \in k[t]$ non nul s'écrit +de façon unique comme $c \prod_{a\in k} (t-a)^{v_a(f)}$ où $c \in +k^\times$ est le coefficient dominant de $f$ et $v_a(f)\in \mathbb{N}$ +est l'ordre du zéro de $f$ en $a$. + +\medbreak + +PGCD, algorithme d'Euclide, relations de Bézout, Euclide étendu : +exactement analogue aux entiers. + % % % |