summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--rappels-maths.tex59
1 files changed, 39 insertions, 20 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex
index 1c48796..0377aef 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.9 2008-10-19 22:53:13 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.10 2008-10-21 16:04:33 david Exp $=
\end{center}
\par}
\pretolerance=10000
@@ -671,7 +671,7 @@ additive�: multiples). L'ordre $m$ de ce sous-groupe est l'ordre
de�$g$. Ce sous-groupe est isomorphe � $\mathbb{Z}/m\mathbb{Z}$, avec
$\bar 1 \mapsto g$.
-Th�or�me de Lagrange�: dans un groupe fini, l'ordre de tout
+\textbf{Th�or�me de Lagrange�:} Dans un groupe fini, l'ordre de tout
sous-groupe divise l'ordre du groupe. En particulier, l'ordre d'un
�l�ment divise l'ordre du groupe�: si $G$ est un groupe fini et $g \in
G$ alors $g^{\#G} = 1$.
@@ -723,8 +723,8 @@ multiplicatif $(\mathbb{Z}/m\mathbb{Z})^\times$. Exemple�: quel est
l'ordre de $2$ dans $\mathbb{Z}/7\mathbb{Z}$�? dans
$(\mathbb{Z}/7\mathbb{Z})^\times$�?
-Cas particulier�: petit th�or�me de Fermat�: si $p$ est premier, alors
-pour tout entier $a$ on a
+Cas particulier�: ��petit th�or�me de Fermat���: si $p$ est premier,
+alors pour tout entier $a$ on a
\[
a^p \equiv a \pmod{p}
\]
@@ -757,7 +757,7 @@ $(\mathbb{Z}/m\mathbb{Z})^\times$).
\item $(\mathbb{Z}/m\mathbb{Z})^\times$ (groupe \emph{multiplicatif},
d'�l�ment neutre�$1$) est d'ordre�$\varphi(m)$ et est \emph{parfois}
cyclique (auquel cas ses g�n�rateurs s'appellent �l�ments
-\emph{primitifs}).
+\emph{primitifs} et il y en a $\varphi(\varphi(m))$).
\end{itemize}
\medbreak
@@ -778,7 +778,8 @@ cyclique (auquel cas ses g�n�rateurs s'appellent �l�ments
\item Si $p=2$ et $r \geq 3$, alors
$(\mathbb{Z}/2^r\mathbb{Z})^\times$ \emph{n'est pas} cyclique�: il
est produit d'un groupe cyclique d'ordre $2$ engendr� par $-1$ et
- d'un groupe cyclique d'ordre $2^{r-2}$ engendr� par�$5$.
+ d'un groupe cyclique d'ordre $2^{r-2}$ engendr� par�$5$ (l'ordre
+ maximal possible d'un �l�ment est $2^{r-2}$).
\end{itemize}
%
@@ -968,7 +969,7 @@ irr�ductibles. Lorsque ce sont les seuls, le corps $k$ est dit
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
+$t-a$ et les $t^2-bt+c$ o� $b^2-4c<0$. Les corps finis (notamment
$\mathbb{F}_p$ d�j� vu) ne sont pas alg�briquement clos (��encore
moins�� que $\mathbb{R}$).
@@ -1027,16 +1028,24 @@ le \textbf{corps de rupture} de�$P$ sur�$k$.
Caract�ristique d'un corps�: c'est l'ordre additif de�$1$ si celui-ci
est fini (sinon on convient que c'est�$0$).
-Tout corps fini contient un $\mathbb{Z}/p\mathbb{Z}$, qui en est un
-sous-corps $\mathbb{F}_p$�: on dit que c'est le sous-corps premier.
-Le corps est alors un espace vectoriel dessus�: si $d$ est sa
-dimension, son nombre d'�l�ments est $p^d$.
+Tout corps de caract�ristique $p>0$ contient un
+$\mathbb{Z}/p\mathbb{Z}$, qui en est un sous-corps $\mathbb{F}_p$
+(donc $p$ est premier)�: on dit que c'est le sous-corps premier. Le
+corps est alors un espace vectoriel dessus�: le corps est fini, et si
+$d$ est sa dimension, son nombre d'�l�ments est $p^d$.
+
+Moralit�: le nombre d'�l�ments d'un corps fini est une puissance�$q =
+p^d$ d'un nombre premier�$p$ (il n'y a pas de corps � $6$ ou $10$
+�l�ments�!), et le corps contient alors $\mathbb{F}_p =
+\mathbb{Z}/p\mathbb{Z}$ qu'on appelle son corps premier�; et $p$
+s'appelle la caract�ristique.
%
\subsection{Unicit�}
Dans un corps $F$ � $q$ �l�ments, on a $a^{q-1} = 1$ pour tout $a \in
-K^\times$ (par Lagrange) donc on a $a^q = a$ pour tout�$a \in K$.
+K^\times$ (par Lagrange) donc on a $a^q = a$ pour tout�$a \in K$
+(��petit th�or�me de Fermat�� g�n�ralis�).
Comme le polyn�me $t^q-t$, de degr� $q$, ne peut avoir que $q$
racines, si $F$ est contenu dans un corps $L$ plus gros, alors $F =
@@ -1062,7 +1071,9 @@ nuls). On le note aussi $\Frob_p$ pour �viter l'ambigu�t�.
Si $q = p^d$, on a souvent besoin d'introduire $\Frob^d = \Frob_q
\colon x \mapsto x^q$ (compos�e $d$-i�me du Frobenius). Notamment,
dans un corps � $q = p^d$ �l�ments, puisque $x^q = x$ pour tout�$x$,
-la compos�e $d$ fois de $\Frob_p$ est l'identit�.
+la compos�e $d$ fois de $\Frob_p$, soit $\Frob_q$, est l'identit�.
+(Pour cette raison, on dit aussi que $\Frob_q$ est le Frobenius
+\emph{au-dessus} de $\mathbb{F}_q$.)
%
\subsection{Existence et inclusions des corps finis}
@@ -1192,10 +1203,11 @@ les deux conditions suivantes sont v�rifi�es�:
$e_1$ de�$e$.
\end{itemize}
(Remarque�: le premier s'�crit $t^{q^e}\equiv t \pmod{f}$, et pour le
-v�rifier on applique un algorithme d'exponentiation rapide dans
-$\mathbb{F}_q[t]/(f)$. De m�me, la seconde condition se teste avec
-l'algorithme d'Euclide en commen�ant par calculer $t^{q^{e_1}}$
-modulo�$f$.)
+v�rifier on applique un algorithme d'exponentiation
+rapide\footnote{Par exemple, dans ce cas, tout simplement �lever $e$
+ fois successivement � la puissance�$q$.} dans $\mathbb{F}_q[t]/(f)$.
+De m�me, la seconde condition se teste avec l'algorithme d'Euclide en
+commen�ant par calculer $t^{q^{e_1}}$ modulo�$f$.)
\smallskip
@@ -1212,6 +1224,12 @@ second, $t^4-t \equiv t^3+t+1 \pmod{g}$ puis $g = t^4+t^3+1 \equiv t^2
\pmod{t^3+t+1}$ et enfin $t^3+t+1 \equiv 1 \pmod{t^2}$ donc $t^4-t$ et
$g$ sont bien irr�ductibles.)
+\bigbreak
+
+\textbf{Note�:} Contrairement � la situation dans les entiers, on peut
+effectuer efficacement la factorisation des polyn�mes sur les corps
+finis.
+
%
\subsection{R�capitulation�: comment manipuler les $\mathbb{F}_q$}
@@ -1240,7 +1258,7 @@ Exercice�: V�rifier que $f = t^3 + t + 1 \in \mathbb{F}_2[t]$ est
irr�ductible, et s'en servir pour dresser les tables d'op�ration de
$\mathbb{F}_8$. (Pour v�rifier que $f$ est irr�ductible�: $t^3 \equiv
t+1 \pmod{f}$ donc $t^4 \equiv t^2+t$ donc $t^8 \equiv t^4+t^2 \equiv
-t$, et il n'y a pas d'autre condition � v�rifier.)
+t$, et par ailleurs $f \equiv 1 \pmod{t^2-t}$.)
%
\subsection{�l�ments primitifs}
@@ -1253,7 +1271,7 @@ Autrement dit, si $\mathbb{F}$ est un corps fini, il existe des
multiplicatif 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$.
-Le nombre d'�l�ments primitifs est bien s�r�$\varphi(q)$.
+Le nombre d'�l�ments primitifs est bien s�r�$\varphi(q-1)$.
Si un �l�ment $g \in \mathbb{F}_q$, avec $q = p^d$, est primitif,
alors tous ses conjugu�s sur le corps premier $g^p, g^{p^2}, g^{p^3},
@@ -1270,7 +1288,8 @@ car $7$ engendre $\mathbb{Z}/15\mathbb{Z}$�; $\{g^3,g^6,g^{12},g^9\}$
en est un autre, de degr�$4$ mais \emph{non primitifs}�; enfin,
$\{g^5,g^{10}\}$ est un ensemble complet de conjugu�s de degr�$2$�;
et $\{1=g^{15}\}$ et $\{0\}$ sont les deux seuls �l�ments de degr�$1$
-sur le corps de base�$\mathbb{F}_2$.
+sur le corps de base�$\mathbb{F}_2$�; on a donc $\mathbb{F}_4 = \{0,
+1, g^5, g^{10}\}$.
Exercice�: on a trouv� pr�c�demment deux polyn�mes irr�ductibles
unitaires $f = t^4 + t + 1$ et $g = t^4 + t^3 + 1$ de degr�$4$