diff options
-rw-r--r-- | rappels-maths.tex | 59 |
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$ |