summaryrefslogtreecommitdiffstats
path: root/rappels-maths.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david@procyon.(none)>2010-10-20 16:39:49 (GMT)
committerDavid A. Madore <david@procyon.(none)>2010-10-20 16:39:49 (GMT)
commit90e6f0df6b5a3d33b3fd75878dd6328590b71f5c (patch)
treedf1b2aa96b627faf5f29712f9d0a3af4fb4a71e5 /rappels-maths.tex
parent2a0b9f66ae3f487bea66fc87e2c6784fc787123f (diff)
downloadinfmdi720-90e6f0df6b5a3d33b3fd75878dd6328590b71f5c.zip
infmdi720-90e6f0df6b5a3d33b3fd75878dd6328590b71f5c.tar.gz
infmdi720-90e6f0df6b5a3d33b3fd75878dd6328590b71f5c.tar.bz2
Various corrections and improvements throughout the text.
Diffstat (limited to 'rappels-maths.tex')
-rw-r--r--rappels-maths.tex263
1 files changed, 180 insertions, 83 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex
index 4aa718f..8325f80 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -1,6 +1,7 @@
%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
+\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{times}
% A tribute to the worthy AMS:
@@ -86,7 +87,9 @@ $v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 =
tel que $xy = 1$. Dans $\mathbb{Z}$, les inversibles sont $1$ et
$-1$.
-Relation d'ordre...
+Relation d'ordre : relation réflexive (on a toujours $x\leq x$),
+antisymétrique (si $x\leq y$ et $y\leq x$ alors $x=y$) et transitive
+(si $x\leq y$ et $y\leq z$ alors $x\leq z$).
%
\subsection{Écriture $b$-adique}
@@ -230,9 +233,11 @@ Quelle est la valuation $2$-adique de $192$ ? $3$-adique ?
$5$-adique ? Quelles sont les valuations $p$-adiques de
$-\frac{24}{11}$, pour tous les $p$ possibles ?
-Propriétés de $v_p$ : produit (cf. lemme de Gauß), inégalité sur la
-somme (et cas d'égalité)... Dire que $x \in \mathbb{Q}$ est entier
-signifie exactement $v_p(x) \geq 0$ pour tout $p$.
+Propriétés de $v_p$ : produit (cf. lemme de Gauß) : on a $v_p(xy) =
+v_p(x) + v_p(y)$ ; inégalité sur la somme : on a $v_p(x+y) \geq
+\min(v_p(x), v_p(y))$ avec égalité si $v_p(x) \neq v_p(y)$. Dire que
+$x \in \mathbb{Q}$ est entier signifie exactement $v_p(x) \geq 0$ pour
+tout $p$.
%
\subsection{Division euclidienne}
@@ -306,7 +311,7 @@ entiers. La notation $\pgcd(\cdots)$ est évidemment la plus claire.
\textbf{Quelques propriétés :}
\begin{itemize}
-\item le pgcd d'un seul entier $m$ est lui-même (et le pgcd de zéro
+\item le pgcd d'un seul entier $m$ est sa valeur absolue (et le pgcd de zéro
entiers est $0$),
\item le pgcd est associatif (par exemple\\
$\pgcd(m_1,m_2,m_3) = \pgcd(\pgcd(m_1,m_2),m_3)$),
@@ -388,7 +393,9 @@ Soit à calculer le pgcd de deux entiers $a$ et $b$.
\end{itemize}
\smallskip
-\textbf{Invariant :} $\pgcd(m,n) = \pgcd(a,b)$ (constant)
+\textbf{Invariant :} $\pgcd(m,n) = \pgcd(a,b)$ (constant) ;
+l'algorithme termine car $n$ décroît strictement à chaque étape (et
+reste un entier naturel).
\medbreak
Exemple : soit à calculer le pgcd de $a=98$ et
@@ -622,6 +629,8 @@ surjections canoniques :
\mathbb{Z}/(mn)\mathbb{Z} \to (\mathbb{Z}/m\mathbb{Z})
\times (\mathbb{Z}/n\mathbb{Z})
\]
+Autrement dit, il s'agit de l'application qui envoie un entier $z$
+modulo $mn$ sur sa classe modulo $m$ et sa classe modulo $n$.
Il s'agit d'un \emph{morphisme d'anneaux} (car les surjections
canoniques en sont !) :
@@ -735,39 +744,51 @@ $e$ tels que :
\begin{itemize}
\item Associativité de $\star$ : $x\star(y\star z) = (x\star y)\star z$
\item Neutralité de $e$ pour $\star$ : $e\star x = x\star e = x$
-\item Existence d'inverses : pour chaque $x$, il existe un élément
+\item Existence de symétriques : pour chaque $x$, il existe un élément
noté $x'$ tel que) $x \star x' = x' \star x = e$
\end{itemize}
Lorsque de plus la loi $\star$ est commutative ($y\star x = x\star
y$), on parle de \emph{groupe abélien} (ou commutatif).
Exemples : l'addition sur les nombres réels (la loi $\star$ étant
-l'addition et le neutre $e$ étant le nombre $0$) ; la multiplication
-sur les nombres réels non nuls (la loi $\star$ étant la multiplication
-et le neutre $e$ étant le nombre $1$) ; la composition des isométries
-du plan (la loi $\star$ étant la composition et le neutre $e$ étant
-l'identité).
+l'addition et le neutre $e$ étant le nombre $0$), ou sur les
+complexes, ou sur les entiers ; la multiplication sur les nombres
+réels non nuls (la loi $\star$ étant la multiplication et le neutre
+$e$ étant le nombre $1$), ou sur les réels strictement positifs, ou
+sur les complexes non nuls ; la composition des isométries du plan (la
+loi $\star$ étant la composition et le neutre $e$ étant l'identité).
+
+Contre-exemple : la multiplication sur les entiers (ou même sur les
+entiers non nuls) \emph{ne forme pas} un groupe, faute d'inverses pour
+les entiers autres que $\pm 1$.
Généralement, un groupe est noté soit de façon multiplicative (on
écrit $xy$ au lieu de $x\star y$ et $1$ au lieu de $e$, et dans ce cas
on note $x^m$ l'élément $x\star x\star \cdots x$ avec $m$ fois $x$ et
-$x^{-1}$ l'inverse de $x$), soit de façon additive (on écrit $x+y$ au
-lieu de $x\star y$ et $0$ au lieu de $e$, et dans ce cas on note $mx$
-l'élément $x + x + + \cdots + x$ avec $m$ fois $x$, et $-x$ l'inverse,
-alors appelé opposé, de $x$). Très souvent on utilise une de ces deux
-notations de façon implicite. La notation additive est en principe
-réservée aux groupes abéliens (mais on n'en rencontrera pas de
-non-abéliens dans ce cours).
+$x^{-1}$ le symétrique de $x$, alors appelé « inverse »), soit de
+façon additive (on écrit $x+y$ au lieu de $x\star y$ et $0$ au lieu
+de $e$, et dans ce cas on note $mx$ l'élément $x + x + + \cdots + x$
+avec $m$ fois $x$, et $-x$ le symétrique de $x$, alors appelé
+« opposé »). Très souvent on utilise une de ces deux notations de
+façon implicite. La notation additive est en principe réservée aux
+groupes abéliens (mais on n'en rencontrera pas de non-abéliens dans ce
+cours).
\smallbreak
Un \textbf{morphisme} de groupe $\psi\colon G \to G'$ est une
-application qui préserve la composition ($\psi(xy) = \psi(x)\,
-\psi(y)$, le groupe étant noté multiplicativement), et du coup
-forcément aussi l'élément neutre ($\psi(1) = 1$). Un
-\textbf{isomorphisme} de groupes est un morphisme bijectif ;
-moralement : les groupes $G$ et $G'$ sont abstraitement « le même »
-(mais éventuellement notés ou étiquetés différemment).
+application qui préserve la composition ($\psi(x\star y) = \psi(x)
+\star \psi(y)$), et du coupb forcément aussi l'élément neutre
+($\psi(e) = e$) et les symétriques (le symétrique de $\psi(x)$ est
+l'image du symétrique de $x$). Un \textbf{isomorphisme} de groupes
+est un morphisme bijectif ; moralement : les groupes $G$ et $G'$ sont
+abstraitement « le même » (mais éventuellement notés ou étiquetés
+différemment). Attention ! On aura souvent affaire, par exemple, à
+un morphisme entre un groupe noté additivement et un groupe noté
+multiplicativement : dans ce cas, cela signifie $\psi(x+y) =
+\psi(x)\,\psi(y)$. Exemple : l'exponentielle (de base $e$, disons)
+constitue un isomorphisme entre le groupe additif des réels et le
+groupe multiplicatif des réels non nuls.
L'\textbf{ordre d'un groupe} est simplement son cardinal, lorsque
celui-ci est fini. L'\textbf{ordre d'un élément} $g$ dans un groupe
@@ -775,8 +796,8 @@ fini est le plus petit $m\geq 1$ tel que $g^m = 1$ (en notation
multiplicative ; en notation additive, cela s'écrirait : $mg = 0$,
i.e., un multiple de $g$) ; c'est aussi le nombre de puissances
distinctes (en notation additive : de multiples distincts) de
-l'élément $g$. Évidemment, si $g$ est d'ordre $m$, on a $g^m = 1$
-mais aussi $g^{m'} = 1$ pour tout multiple de $m$ !
+l'élément $g$. Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi
+$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$.
Un \textbf{sous-groupe} $H$ d'un groupe $G$ est un sous-ensemble de
$G$ qui est lui-même un groupe pour la même opération et le même
@@ -811,7 +832,8 @@ On dit qu'un groupe fini $G$ est \textbf{cyclique} lorsqu'il existe un
$G$ soit de la forme $g^k$ (une puissance de $g$, en notation
multiplicative ; en notation additive, cela s'écrirait : $kg$, i.e.,
un multiple de $g$), autrement dit : le sous-groupe engendré par $g$
-est $G$ tout entier.
+est $G$ tout entier. Ou encore : $G$ est cyclique de générateur $g$
+si et seulement si l'ordre de $g$ est égal à l'ordre de $G$.
Le groupe \emph{additif} $\mathbb{Z}/m\mathbb{Z}$ est cyclique, avec
pour générateur $1$ (mais ce n'est pas le seul possible !
@@ -822,14 +844,50 @@ D'où une autre définition possible : un groupe cyclique $G$ [de
générateur $g$] est un groupe isomorphe à $\mathbb{Z}/m\mathbb{Z}$
[avec $1$ correspondant à $g$].
-Les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme groupe additif !)
-sont précisément les inversibles de $\mathbb{Z}/m\mathbb{Z}$ (comme
-anneau !). Attention ! on parlera aussi, plus loin, des générateurs
-du groupe \emph{multiplicatif} $(\mathbb{Z}/m\mathbb{Z})^\times$ (et
-de la question de savoir s'il y en a).
+Quels sont tous les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme
+groupe additif !) ? Réponse : ce sont précisément les classes modulo
+$m$ des entiers premiers à $m$, c'est-à-dire les inversibles de
+$\mathbb{Z}/m\mathbb{Z}$ (comme anneau !). (Démonstration : si $\bar
+a$ engendre le groupe additif $\mathbb{Z}/m\mathbb{Z}$, alors en
+particulier il doit engendrer $\bar 1$, c'est-à-dire qu'on peut écrire
+$\bar 1 = \bar a + \bar a + \cdots + \bar a$, avec $u$ fois $\bar a$
+disons, donc $\bar a \bar u = \bar 1$ dans l'anneau
+$\mathbb{Z}/m\mathbb{Z}$, et $\bar a$ y est bien inversible.
+Réciproquement, si $\bar a \bar u = \bar 1$, et si $\bar a + \bar a +
+\cdots + \bar a = 0$, avec $k$ fois $\bar a$, alors en multipliant par
+$\bar u$ on a $\bar 1 + \bar 1 + \cdots + \bar 1 = 0$, soit $\bar k =
+0$, donc $k$ est multiple de $m$ : ceci prouve que l'ordre de $\bar a$
+ne peut pas être plus petit que $m$.)
+
+Ainsi, pour $m$ entier naturel non nul et $a$ entier, il y a
+équivalence entre :
+\begin{itemize}
+\item les entiers $a$ et $m$ sont premiers entre eux,
+\item l'élément $\bar a$ a pour ordre (additif) $m$ dans le groupe
+ $\mathbb{Z}/m\mathbb{Z}$,
+\item l'élément $\bar a$ est générateur du groupe
+ $\mathbb{Z}/m\mathbb{Z}$,
+\item l'élément $\bar a$ est inversible dans l'anneau
+ $\mathbb{Z}/m\mathbb{Z}$,
+\item l'élément $\bar a$ appartient au groupe
+ $(\mathbb{Z}/m\mathbb{Z})^\times$ des inversible de l'anneau
+ $\mathbb{Z}/m\mathbb{Z}$.
+\end{itemize}
+
+En particulier, $\mathbb{Z}/m\mathbb{Z}$ admet $\varphi(m)$
+générateurs. Comme un groupe cyclique d'ordre $m$ est la même chose
+que (un groupe isomorphe à) $\mathbb{Z}/m\mathbb{Z}$, on en déduit :
+le nombre de générateurs de n'import quel groupe cyclique d'ordre $m$
+est $\varphi(m)$.
+
+Attention ! on parlera aussi, plus loin, des générateurs du groupe
+\emph{multiplicatif} $(\mathbb{Z}/m\mathbb{Z})^\times$ (et de la
+question de savoir s'il y en a). Il ne faut pas confondre !
+
+\medbreak
-Moralité : $\varphi(m)$ est aussi le nombre d'éléments d'un groupe
-cyclique (quelconque) d'ordre $m$ qui en sont un générateur.
+De façon générale, l'ordre additif de $\bar a$ dans
+$\mathbb{Z}/m\mathbb{Z}$ vaut exactement $m/\pgcd(a,m)$.
%
\subsection{Théorème d'Euler}
@@ -841,7 +899,8 @@ a^{\varphi(m)} \equiv 1 \pmod{m}
\]
Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$
-a un ordre qui doit diviser l'ordre du groupe, i.e. $\varphi(m)$.
+a un ordre qui d'après Lagrange doit diviser l'ordre du groupe,
+i.e. $\varphi(m)$.
\textbf{Attention !} ne pas confondre l'ordre (« additif ») d'un
élément du groupe additif $\mathbb{Z}/m\mathbb{Z}$ et l'ordre
@@ -881,8 +940,9 @@ Soit $m$ un entier naturel non nul. On dit que $g \in
(comme groupe abélien multiplicatif) --- ce qui entraîne que
$(\mathbb{Z}/m\mathbb{Z})^\times$ est cyclique.
-Autrement dit, $g^{\varphi(m)}=1$ est optimal ($\varphi(m)$ est
-exactement l'ordre de $g$).
+Autrement dit, $g^{\varphi(m)}=1$ est optimal : dire que $g$ est
+primitif modulo $m$ signifie que son ordre multiplicatif est
+exactement $\varphi(m)$ (et pas un autre diviseur de $\varphi(m)$).
Exemple : les puissances de $\bar 2$ modulo $9$ sont : $\bar 2,\bar
4,\bar 8,\bar 7,\bar 5,\bar 1$ ; il y en a bien $\varphi(9)=6$ donc
@@ -928,14 +988,17 @@ cyclique (auquel cas ses générateurs s'appellent éléments
\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}$).
+Soit $k$ un anneau commutatif quelconque (par exemple : $\mathbb{Z}$),
+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{série formelle}). Autrement dit, on peut écrire $f = a_0 +
+a_1 t + \cdots + a_n t^n$ pour un certain $n$ (et si on impose $a_n
+\neq 0$, ceci définit $n$, qui s'appellera alors le degré de $f$).
\textbf{Opérations :}
\begin{itemize}
@@ -949,7 +1012,9 @@ 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}.
++ a_N t^N$ ; si $a_N = 1$ on dit que $f$ est \textbf{unitaire}. Plus
+généralement, le coefficient $a_{\deg f}$ s'appelle \emph{coefficient
+ dominant} de $f$.
\textbf{Propriétés} du degré :
\begin{itemize}
@@ -1004,36 +1069,29 @@ a_1 + 2 a_2 t + \cdots + N a_N t^{N-1}$.
\mathbb{N}$.
%
-\subsection{Polynôme interpolateur, formule de Taylor}
+\subsection{Polynôme interpolateur}
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.
-
-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
+\textbf{Fait fondamental :} lorsque deux polynômes de degré $\leq N$
+coïncident en (au moins) $N+1$ points, ils sont égaux ; de façon
+équivalente, si un polynôme de degré $\leq N$ s'annule en $\geq N+1$
+points, alors c'est le polynôme nul.
-Si $N \geq \deg f$ et $N!$ n'est pas nul dans $k$, alors pour tout
-$a\in k$ :
+Réciproquement, si $a_0,\ldots,a_N \in k$ sont deux à deux distincts,
+et $b_0,\ldots,b_N\in k$ sont quelconques, alors
\[
-f = f(a) + (t-a)\,f'(a) + \frac{(t-a)^2}{2}\,f''(a) +
-\cdots + \frac{(t-a)^N}{N!}\,f^{(N)}(a)
+\sum_{i=0}^N b_i \frac{\prod_{j\neq i}(t-a_j)}{\prod_{j\neq i}(a_i-a_j)}
\]
+(\emph{polynôme interpolateur de Lagrange}) est un polynôme de
+degré $\leq N$ prenant en $a_i$ la valeur $b_i$. D'après ce qu'on
+vient de dire, c'est \emph{le} seul polynôme de degré $\leq N$ prenant
+en chaque $a_i$ la valeur $b_i$.
-Permet de reconstruire un polynôme à partir de ses dérivées
-successives en un point.
+Ceci permet de reconstruire un polynôme à partir de ses valeurs en
+suffisamment de points.
%
\subsection{Division euclidienne de polynômes}
@@ -1070,8 +1128,9 @@ par $g$, soit $f^* = gq^* + r$ et on a $f = gq + r$ où $q = c t^{N-D}
\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 ?)
+$f$ par $t-a$ (où $a \in k$ est une constante) est $f(a)$. (En effet,
+c'est clair lorsque $a = 0$, et on en déduit le cas général par
+translation.)
\smallbreak
@@ -1123,42 +1182,65 @@ 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$).
+par convention. Dans l'algorithme d'Euclide, il faut donc au final
+diviser le dernier reste par son coefficient dominant pour le rendre
+unitaire ; notamment, 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, or 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 : 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.
+Vision concrète : les éléments de $k[t]/(P)$ sont représentés de façon
+unique par des polynômes à coefficients dans $k$ de degré strictement
+inférieur au degré de $P$, et on se ramène à $\deg f < \deg P$ par
+division euclidienne après chaque opération (en fait, on n'a besoin de
+prendre le reste de la division euclidienne par $P$ qu'après une
+multiplication, puisque l'addition des polynômes ne fait jamais monter
+leur degré).
+
+Pour tout $c \in k^\times$, on a $k[t]/(cP) = k[t]/(P)$. Autrement
+dit, multiplier $P$ par une constante ne change rien, donc on aura
+tendance à supposer que $P$ est unitaire quand on écrit $k[t]/(P)$.
Les éléments de $k$ se voient comme des éléments de $k[t]/(P)$ (les
constantes).
-Élément très important : $\bar t$. Il vérifie $P(\bar t) = 0$.
+Élément très important : $\bar t$. Il vérifie $P(\bar t) = 0$ (car le
+reste de la division euclidienne de $P(t) = P$ par $P$ est $0$).
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}$).
+aussi fini, et de cardinal $(\#k)^{\deg P}$ (concrètement, se donner
+un élément de $k[t]/(P)$ revient à se donner un élément de $k[t]$ de
+degré $<\deg P$, donc à se donner $\deg P$ coefficients, chacun
+pouvant prendre $\#k$ valeurs).
+
+\smallbreak
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émonstration que
pour les entiers, avec un petit peu d'algèbre linéaire).
+\smallbreak
+
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 en utilisant la
-factorisation $t^2-1=(t-1)(t+1)$ ; noter que ce n'est pas un corps).
+\cong \mathbb{R}[t]/(t-1) \times \mathbb{R}[t]/(t+1) \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)$.
+Vérifier qu'il s'agit d'un \emph{corps} à $4$ éléments. On le notera
+$\mathbb{F}_4$. (\emph{Attention !} Ce n'est pas
+$\mathbb{Z}/4\mathbb{Z}$, car ce dernier n'est pas un corps !)
-\medskip
+\medbreak
\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 l'appelle
@@ -1226,7 +1308,9 @@ $L$ de caractéristique $p$ est $\mathbb{F}_p = \{x\in L : x^p = x\}$.
On admet également l'unicité à isomorphisme près : deux corps finis à
$q$ éléments, pour le même $q$, sont isomorphes. (C'est-à-dire qu'il
s'agit abstraitement du même objet, mais dont les éléments peuvent
-être « nommés » différemment.)
+être « nommés » différemment.) On notera $\mathbb{F}_q$ le corps à
+$q$ éléments, s'il existe (on va voir que c'est le cas pour toute
+puissance $q$ d'un nombre premier).
%
\subsection{Morphisme de Frobenius, conjugués d'un élément}
@@ -1281,8 +1365,8 @@ Il y a cependant des rapports : par exemple, si $x \neq 0$ est de
degré $r$ alors son ordre multiplicatif divise $p^r - 1$ (car on a
$x^{p^r} = x$ par définition de $r$, donc $x^{p^r - 1} = 1$) ;
notamment, si $x$ est d'ordre $q - 1 = p^d - 1$ (on va voir qu'il
-existe de tels éléments) alors $x$ est de degré $d$ (mais la
-réciproque n'est pas vraie).
+existe de tels éléments, ce sont les éléments primitifs) alors $x$ est
+de degré $d$ (mais la réciproque n'est pas vraie).
%
\subsection{Existence et inclusions des corps finis}
@@ -1291,7 +1375,12 @@ Pour tout nombre premier $p$ et tout $d \geq 1$, il existe un corps à
$q = p^d$ éléments, qu'on peut noter $\mathbb{F}_q$. On peut le voir
comme $\mathbb{F}_q \cong \mathbb{F}_p[t]/(f)$ pour un certain
polynôme $f \in \mathbb{F}_p[t]$ irréductible de degré $d$
-(l'affirmation est qu'il en existe !).
+(l'affirmation importante est qu'il en existe !).
+
+Moralement, le fait de choisir tel ou tel polynôme $f$ irréductible de
+degré $d$ (unitaire, disons) ne change pas le corps $\mathbb{F}_q$
+qu'on obtient comme $\mathbb{F}_p[t]/(f)$, cela change uniquement la
+valeur de l'élément représenté comme $\bar t$.
\smallbreak
@@ -1302,6 +1391,12 @@ un sous-corps ayant $q$ éléments) si et seulement si : (1) $p=p'$ et
(Exemple : $\mathbb{F}_4$ est contenu dans $\mathbb{F}_{16}$ mais pas
dans $\mathbb{F}_8$.)
+Rappelons que lorsque c'est le cas (que $q'$ est une puissance
+de $q$), on peut retrouver $\mathbb{F}_q$ dans $\mathbb{F}_{q'}$ comme
+l'ensemble $\{x : x^q=x\}$ des racines de $t^q - t$, ou encore comme
+l'ensemble des éléments dont le degré au-dessus de $\mathbb{F}_p$
+divise $d$ (car $x^q = x$ signifie $\Frob^d(x) = x$).
+
%
\subsection{Test de Rabin, factorisation de $t^{p^d}-t$}
@@ -1381,7 +1476,9 @@ Autrement dit, si $\mathbb{F}$ est un corps fini, il existe des
éléments $g$, dits \textbf{primitifs}, qui engendrent le groupe
multiplicatif $\mathbb{F}^\times$ des éléments non nuls
de $\mathbb{F}$, c'est-à-dire tels que tout élément non nul de
-$\mathbb{F}$ soit une puissance de $g$.
+$\mathbb{F}$ soit une puissance de $g$. Un élément primitif de
+$\mathbb{F}_q$ est un élément de $\mathbb{F}_q^\times$ dont l'ordre
+multiplicatif vaut exactement $q-1$.
Le nombre d'éléments primitifs est bien sûr $\varphi(q-1)$ (puisque,
une fois qu'on sait que $\mathbb{F}^\times$ est cyclique, comme il est