From f9e49f00c3909cf7f15bd297067d85074544dd7b Mon Sep 17 00:00:00 2001 From: david Date: Wed, 21 Oct 2009 18:30:30 +0000 Subject: Rework the part about polynomials. --- rappels-maths.tex | 72 +++++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 52 insertions(+), 20 deletions(-) diff --git a/rappels-maths.tex b/rappels-maths.tex index 67fbb30..944910c 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.16 2009-10-21 18:17:11 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.17 2009-10-21 18:30:30 david Exp $= \end{center} \par} \pretolerance=10000 @@ -976,12 +976,23 @@ Complexit \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$. +$x$ est dans $k$ ou $k[t]$ (ou plus généralement une « $k$-algèbre »), +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{Racines :} si $f(x) = 0$ avec $x \in k$, on dit que $x$ est +une \emph{racine} du polynôme $f$. + +\textbf{Attention :} On peut très bien avoir $f(x) = 0$ pour tout $x +\in k$ sans pour autant que $f$ soit nul (e.g., $f = t^p - t$ dans +$\mathbb{F}_p[t]$). + +(Mais on va voir que si $k$ est un corps, le nombre de racines de $f$ +dans $k$ est inférieur ou égal au degré de $f$.) + \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}$. @@ -1009,6 +1020,9 @@ 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. +Ceci assure notamment que si $f$ s'annule en $N+1$ points (où $N \geq +\deg f$) alors $f$ est le polynôme nul. + \medbreak Si $N \geq \deg f$ et $N!$ n'est pas nul dans $k$, alors pour tout @@ -1069,11 +1083,16 @@ 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). +Dire qu'un polynôme $f$ admet $a$ pour racine signifie exactement que +$t-a$ divise $f$. + +Les \textbf{unités} (ou inversibles) 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 +premiers : on dit que $f$ est irréductible lorsque $\deg f \geq 1$ et +qu'il n'existe pas d'écriture $f = gh$ avec $\deg g \geq 1$ et $\deg h +\geq 1$. 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 @@ -1102,35 +1121,48 @@ est l'ordre du z PGCD, algorithme d'Euclide, relations de Bézout, Euclide étendu : exactement analogue aux entiers. +Attention cependant : de même que le pgcd de deux entiers est choisi +positif par convention, le pgcd de deux polynômes est choisi unitaire +par convention. Dans l'algorithme d'Euclide, si le reste final est +une \emph{constante} non nulle (pas nécessairement $1$), les polynômes +sont premiers entre eux (par exemple, le pgcd de $t+2$ et $t$ dans +$\mathbb{R}[t]$ est $1$, ces polynômes sont premiers entre eux, même +si le reste de la division de $t+2$ par $t$ est $2$). + % \subsection{Anneaux $k[t]/(P)$} -Analogues exacts de $\mathbb{Z}/m\mathbb{Z}$. Vision abstraite : -$f\equiv g\pmod{P}$ ssi $P$ divise $f-g$, et on quotiente. Vision -concrète : se ramener à $\deg f < \deg P$ par division euclidienne -après chaque opération. +Analogues exacts de $\mathbb{Z}/m\mathbb{Z}$. Vision abstraite : on +définit $f\equiv g\pmod{P}$ ssi $P$ divise $f-g$, et on quotiente. +Vision concrète : se ramener à $\deg f < \deg P$ par division +euclidienne après chaque opération. + +Les éléments de $k$ se voient comme des éléments de $k[t]/(P)$ (les +constantes). -Élément très important : $\bar t$. +Élément très important : $\bar t$. Il vérifie $P(\bar t) = 0$. -C'est un espace vectoriel de dimension $\deg P$ sur $k$. Si $k$ est -fini alors $k[t]/(P)$ l'est (de cardinal $(\#k)^{\deg P}$). +Si on sait ce que ça signifie : $k[t]/(P)$ est un espace vectoriel de +dimension $\deg P$ sur $k$. Si $k$ est fini alors $k[t]/(P)$ est +aussi fini (de cardinal $(\#k)^{\deg P}$). Théorème chinois : si $P$ et $Q$ sont premiers entre eux, on a -$k[t]/(PQ) \cong (k[t]/(P)) \times (k[t]/(Q))$ (même démo qu'avant, -avec un petit peu d'algèbre linéaire). +$k[t]/(PQ) \cong (k[t]/(P)) \times (k[t]/(Q))$ (même démonstration que +pour les entiers, avec un petit peu d'algèbre linéaire). -Exemple idiot : $k[t]/(t) \cong k$. Exemples moins idiot : +Exemple idiot : $k[t]/(t) \cong k$ (ici, $\bar t = 0$). En fait, +$k[t]/(t-a) \cong k$ où $\bar t$ devient $a$. Exemples moins idiot : $\mathbb{R}[t]/(t^2+1) \cong \mathbb{C}$, et $\mathbb{R}[t]/(t^2-1) -\cong \mathbb{R} \times \mathbb{R}$ (théorème chinois ; noter que ce -n'est pas un corps). +\cong \mathbb{R} \times \mathbb{R}$ (théorème chinois en utilisant la +factorisation $t^2-1=(t-1)(t+1)$ ; noter que ce n'est pas un corps). Exercice : dresser les tables de $\mathbb{F}_2[t]/(t^2+t+1)$. \medskip \textbf{Important :} $k[t]/(P)$ est un corps \emph{si et seulement si} -$P \in k[t]$ est irréductible. Lorsque c'est le cas, on dit que c'est -le \textbf{corps de rupture} de $P$ sur $k$. +$P \in k[t]$ est irréductible. Lorsque c'est le cas, on l'appelle +\textbf{corps de rupture} de $P$ sur $k$. % \section{Corps finis} -- cgit v1.2.3