summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordavid <david>2009-10-21 18:30:30 +0000
committerdavid <david>2009-10-21 18:30:30 +0000
commitf9e49f00c3909cf7f15bd297067d85074544dd7b (patch)
tree4c5bf45d9fb3915f4a112048019ccf81e368389e
parentf41aa7da23cfb80e97f7b91d46ce0ad6bfe05be4 (diff)
downloadinfmdi720-f9e49f00c3909cf7f15bd297067d85074544dd7b.zip
infmdi720-f9e49f00c3909cf7f15bd297067d85074544dd7b.tar.gz
infmdi720-f9e49f00c3909cf7f15bd297067d85074544dd7b.tar.bz2
Rework the part about polynomials.upload-20091021
-rw-r--r--rappels-maths.tex72
1 files 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,13 +976,24 @@ 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$.
+$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éro de $f$ en $a$.
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}