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