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 |