\ifx\danslelivre\undefined \documentclass[9pt]{../configuration/smfart} \input{../configuration/commun} \input{../configuration/smf} \input{../configuration/adresse} \input{../configuration/gadgets} \input{../configuration/francais} \input{../configuration/numerotation} \input{../configuration/formules} \input{../configuration/encoredesmacros} \usepackage{stmaryrd} \usepackage{wasysym} \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{srcltx} \synctex=1 \title{Corps finis} \externaldocument{extensions-algebriques} \externaldocument{algo-corps-finis} \externaldocument{correspondance-galois} \begin{document} \maketitle \tableofcontents \else \chapter{Corps finis} \fi \section{Propriétés élémentaires} \subsection{Caractéristique} Soit $k$ un corps. Le noyau de l'unique morphisme d'anneaux $𝐙→k$ est un idéal premier de $𝐙$. On rappelle que la \emph{caractéristique} de $k$ désigne le générateur positif ou nul de cet idéal : on le note $\car k$. C'est un nombre premier (souvent noté $p$) ou bien $0$. Lorsque $\car k$ est un nombre premier $p>0$, l'image de $\ZZ\to k$ est isomorphe à $\ZZ/p\ZZ$. Pour tout nombre premier $p$, on note $𝐅_p$ le quotient $𝐙/p𝐙$. C'est un corps (car c'est un anneau intègre fini) de caractéristique $p$ à $p$ éléments. Pour tout corps $k$ de caractéristique $p$, l'image de $\ZZ \to k$ est un sous-corps de $k$ isomorphe à $\FF_p$, qui est le plus petit sous-corps de $k$ (car les sous-corps de $k$ sont eux aussi de caractéristique $p$) et que l'on appelle \emph{corps premier} de $k$. On appelle par ailleurs \emph{exposant caractéristique} \index{exposant caractéristique} de $k$ l'entier valant $1$ si $\car k= 0$ et valant $\car k$ sinon. \begin{lemme2}\label{structures-sur-corps-premier} Soit $p$ un nombre premier. Un groupe abélien $M$ peut être munie d'une structure d'espace vectoriel sur le corps $\FF_p$ exactement lorsque tout élément $x\in M$ vérifie $px = 0$, auquel cas cette structure de $\FF_p$-espace vectoriel est unique. Un anneau $A$ non nécessairement commutatif peut-être muni d'une structure de $𝐅_p$-algèbre non nécessairement commutative si et seulement si l'image de $p$ dans $A$ par le morphisme canonique (et unique) $𝐙→A$ est nulle. Cette structure est alors unique. \end{lemme2} \begin{proof} Pour ce qui est de la première affirmation, tout $\FF_p$-espace vectoriel doit manifestement vérifier $px = 0$ pour tout $x$, et si un groupe abélien $M$ vérifie cette condition, on peut alors poser $\bar k\cdot x = k x$, pour tous $k \in \ZZ$, dont on note $\bar k \in \FF_p$ la classe modulo $p$, et tout $x \in M$, ce qui définit une structure de $\FF_p$ espace vectoriel sur $M$, qui était la seule possible car $\bar k = k\cdot \bar 1$ dans $\FF_p$. En particulier, toute $\FF_p$-algèbre non nécessairement commutative $A$ doit vérifier $p 1_A = 0$, c'est-à-dire que l'image de $p$ par le morphisme $\ZZ \to A$ est nulle ; et si cette condition est satisfaite dans un anneau non nécessairement commutatif $A$ alors $p x = p 1_A x = 0$ pour tout $x \in A$ donc on vient de voir qu'il y a une unique façon de mettre sur $A$ une structure de $\FF_p$-espace vectoriel, qui est clairement une structure de $\FF_p$-algèbre non nécessairement commutative. \end{proof} \begin{lemme2}\label{anneaux-a-p-elements} Soit $A$ un anneau non nécessairement commutatif ayant $p$ éléments, où $p$ est un nombre premier. Alors il existe un unique isomorphisme entre $\FF_p$ et $A$. \end{lemme2} \begin{proof} L'image du morphisme d'anneaux $\ZZ \to A$ est un sous-anneau de $A$ dont le cardinal doit diviser $p$ ; comme $0_A \neq 1_A$ (sans quoi $A$ serait l'anneau nul, qui a un seul élément, ce qui n'est pas le cas), ce cardinal est $p$, c'est-à-dire que $\ZZ \to A$ est surjectif. Il définit donc un isomorphisme $\ZZ/n\ZZ \buildrel\sim\over\to A$ avec $n$ le générateur positif de son noyau, et en comparant les cardinaux on voit que $n=p$, de sorte qu'on a un isomorphisme $\FF_p \buildrel\sim\over\to A$, qui était visiblement le seul possible. \end{proof} On peut donc parler \emph{du} corps fini ayant $p$ éléments, et il n'y a pas de problème à identifier $\FF_p$ au corps premier de n'importe quel corps de caractéristique $p$. \begin{proposition2} Soit $F$ un corps fini. Alors, la caractéristique de $F$ est un nombre premier $p>0$ et le cardinal de $F$ est une puissance de $p$. \end{proposition2} \begin{démo}[Démonstration de la proposition] Le morphisme $𝐙→F$ n'est pas injectif car $F$ est fini donc $\car(F)≠0$. D'autre part, si $p=\car(F)$, le lemme \ref{structures-sur-corps-premier} assure que $F$ un $\FF_p$-espace vectoriel (de façon unique). Si $r=\dim_{\FF_p}(F)$ (nécessairement finie), on a $\# F=p^r$. \end{démo} Il est fréquent, lorsqu'on a affaire à un corps fini, de noter $p$ sa caractéristique et $q$ son nombre d'éléments (qui en est donc une puissance), à tel point que ces notations sont parfois utilisées, si cela ne cause pas de confusion, sans avoir été introduites. En particulier, une expression telle que « soit $F$ un corps fini de cardinal $p^r$ » sous-entendra toujours que $p$ est un nombre premier et $r>0$ un entier naturel non nul. \begin{remarque2} On peut montrer que tout corps gauche fini est commutatif (théorème de Wedderburn ; nous en donnerons une démonstration en \ref{Wedderburn}), ou même que toute algèbre à division alternative mais non nécessairement associative est un corps fini. \end{remarque2} \subsection{Le morphisme de Frobenius} \begin{proposition2}[petit théorème de Fermat]\label{petit-theoreme-fermat} Soit $F$ un corps fini ayant $q$ éléments. Alors tout élément $x$ de $F$ vérifie $x^q = x$. Plus précisément, les racines du polynôme $X^q-X$ dans $F$ sont tous les éléments de $F$, chacun avec multiplicité $1$ : on a \[ X^q - X = \prod_{a \in F} (X-a) \] \end{proposition2} \begin{proof} Le groupe multiplicatif $F^×$ des inversibles de $F$ est d'ordre $q-1$, donc si $x \neq 0$ on a $x^{q-1} = 1$ donc $x^q = x$ ; le cas $x=0$ est trivial. Pour ce qui est de la seconde affirmation, on vient de montrer que $\prod_{a \in F} (X-a)$ divise $X^q-X$, et comme ces deux polynômes sont unitaires et de même degré, ils sont égaux. \end{proof} \begin{corollaire2}\label{unicite-corps-q-elements-pour-inclusion} Si $K$ est un corps de caractéristique $p>0$, alors pour toute puissance $q = p^r$ de $p$, il existe au plus un sous-corps de $K$ ayant $q$ éléments. \end{corollaire2} \begin{proof} Si $F$ est un sous-corps de $K$ à $q$ éléments, alors la proposition \ref{petit-theoreme-fermat} montre que $F$ est exactement l'ensemble des racines de $X^q-X$ (dans $F$ donc dans $K$), ce qui prouve l'unicité. \end{proof} Autrement dit, un corps à $q$ éléments est unique comme sous-corps de n'importe quel sur-corps. On va voir en \ref{existence-et-unicite-corps finis} qu'il est également unique à isomorphisme près (mais pas à isomorphisme unique près). \begin{proposition2}\label{morphisme-de-frobenius} Soient $p$ un nombre premier et $A$ une $𝐅_p$-algèbre. L'application $\Frob|_A\colon A→A$ donnée par $a↦a^p$ est un \emph{endomorphisme} de $A$. \end{proposition2} \begin{démo} Seule l'identité $\Frob|_A(x+y)=\Frob|_A(x)+\Frob|_A(y)$ n'est pas évidente. Elle résulte de la formule du binôme de Newton et de la congruence $\frac{p!}{i!(p-i)!}≡0\pmod{p}$ pour tout $01$, l'entier $q^m-1$ divise $q^n-1$, \item le polynôme $X^m-1$ divise $X^n-1$ (dans $\ZZ[X]$ ou, par conséquent, $A[X]$ pour n'importe quel anneau $A$), \item pour tout entier $q>1$, le polynôme $X^{q^m}-X$ divise $X^{q^n}-X$ (de même). \end{itemize} \end{lemme2} \begin{proof} Le premier point découle de ce que $q^n-1 = (q^m-1)(q^{n-m} + q^{n-2m} + \cdots + q^{2m} + q^m + 1)$, comme on le voit en dévelopant. Le second découle de même de ce que $X^n-1 = (X^m-1)(X^{n-m} + X^{n-2m} + \cdots + X^{2m} + X^m + 1)$. Le troisième point découle des deux premiers : puisque $q^m-1$ divise $q^n-1$, le polynôme $X^{q^m-1} - 1$ divise $X^{q^n-1} - 1$, et par conséquent $X^{q^m} - X$ divise $X^{q^n} - X$. \end{proof} \begin{lemme2}\label{lemme-non-divisibilite-x-q-r-x} Soient $m$ et $n$ deux entiers naturels non nuls et $r$ le reste de la division euclidienne de $m$ par $n$ ; on suppose $r>0$. Alors : \begin{itemize} \item pour tout entier $q>1$, le reste de la division euclidienne de $q^m-1$ par $q^n-1$ est $q^r-1$, \item il existe $g$ dans $\ZZ[X]$ tel que $X^m-1 = (X^n-1) g + (X^r-1)$, \item pour tout entier $q>1$, il existe $g$ dans $\ZZ[X]$ tel que $X^{q^m}-X = (X^{q^n}-X) g + (X^{q^r}-X)$. \end{itemize} \end{lemme2} \begin{proof} Écrivons $m = kn+r$ : le lemme \ref{lemme-divisibilite-x-q-r-x} montre que $q^{kn} \equiv 1 \pmod{q^n-1}$, et par conséquent $q^m - 1 \equiv q^r -1 \pmod{q^n-1}$ ; puisque $0 < q^r - 1 < q^n - 1$, on a le premier point annoncé. Le second est rigoureusement analogue. Le troisième découle des deux premiers : puisque $q^r - 1$ est le reste de la division euclidienne de $q^m - 1$ par $q^n - 1$, on peut écrire $X^{q^m-1} - 1 = (X^{q^n-1}-1) g + (X^{q^r-1}-1)$, donc $X^{q^m} - X = (X^{q^n}-X) g + (X^{q^r}-X)$. \end{proof} \begin{lemme2}\label{lemme-pgcd-x-q-r-x} Soient $m$ et $n$ deux entiers naturels non nuls et $d$ leur pgcd. Alors : \begin{itemize} \item pour tout entier $q>1$, les entiers $q^m-1$ et $q^n-1$ ont pour pgcd $q^d-1$ (concrètement, il existe $u,v$ entiers tels que $(q^m-1)u + (q^n-1)v = q^d-1$), \item les polynômes $X^m-1$ et $X^n-1$ de $\ZZ[X]$ engendrent l'idéal $(X^d-1)$ de $\ZZ[X]$ (concrètement, il existe $u,v$ de $\ZZ[X]$ tels que $(X^m-1)u + (X^n-1)v = X^d-1$), \item pour tout entier $q>1$, les polynômes $X^{q^m}-X$ et $X^{q^n}-X$ de $\ZZ[X]$ engendrent l'idéal $(X^{q^d}-X)$ de $\ZZ[X]$ (concrètement, il existe $u,v$ de $\ZZ[X]$ tels que $(X^{q^m}-X) u + (X^{q^n}-X) v = X^{q^d}-X$. \end{itemize} \end{lemme2} \begin{proof} Avant toute chose, \ref{lemme-divisibilite-x-q-r-x} assure bien que $q^d-1$ divise $q^m-1$ et $q^n-1$, que $X^d-1$ divise bien $X^m-1$ et $X^n-1$, et que $X^{q^d}-X$ divise bien $X^{q^m}-X$ et $X^{q^n}-X$. (Ceci justifie notamment que dire « il existe $u,v$ de $\ZZ[X]$ tels que $(X^m-1)u + (X^n-1)v = X^d-1$ » traduise bien le fait que $X^m-1$ et $X^n-1$ engendrent l'idéal $(X^d-1)$, et pas un idéal plus gros, et de même pour les autres points.) Montrons le premier point par récurrence sur $n$. Si $n=d$, tout est clair. Sinon, soit $r$ le reste de la division euclidienne de $m$ par $n$, qui vérifie bien sûr $r>0$. Alors le reste de la division euclidienne de $q^m-1$ par $q^n-1$ vaut $q^r-1$ d'après \ref{lemme-non-divisibilite-x-q-r-x}. Par conséquent, $\pgcd(q^m-1,q^n-1) = \pgcd(q^n-1,q^r-1)$. Comme $n$ et $r$ sont premiers entre eux, l'hypothèse de récurrence permet de conclure que ceci vaut $q^d-1$, ce qu'on voulait prouver. Montrons le second point par récurrence sur $n$. Si $n=d$, tout est clair. Sinon, soit $r$ le reste de la division euclidienne de $m$ par $n$, qui vérifie bien sûr $r>0$. Alors on peut écrire $X^m-1 = (X^n-1) g + (X^r-1)$ d'après \ref{lemme-non-divisibilite-x-q-r-x}. Comme $n$ et $r$ sont premiers entre eux, l'hypothèse de récurrence permet de trouver une écriture $X^d-1 = (X^n-1)u + (X^r-1)v$ ; en remplaçant $X^r-1$ par $X^m-1 - (X^n-1) g$, on trouve bien une écriture $X^d-1 = (X^m-1)u' + (X^n-1)v'$ comme souhaitée. Le troisième point se démontre encore par récurrence sur $n$. Si $n=d$, tout est clair. Sinon, soit $r$ le reste de la division euclidienne de $m$ par $n$, qui vérifie bien sûr $r>0$. Alors on peut écrire $X^{q^m}-X = (X^{q^n}-X) g + (X^{q^r}-X)$ d'après \ref{lemme-non-divisibilite-x-q-r-x}. Comme $n$ et $r$ sont premiers entre eux, l'hypothèse de récurrence permet de trouver une écriture $X^{q^d}-X = (X^{q^n}-X)u + (X^{q^r}-X)v$ ; en remplaçant $X^{q^r}-X$ par $X^{q^m}-X - (X^{q^n}-X) g$, on trouve bien une écriture $X^{q^d}-X = (X^{q^m}-X)u' + (X^{q^n}-X)v'$ comme souhaitée. \end{proof} \begin{proposition2}\label{inclusions-corps-finis} Si $q = p^r$ et $q' = p^{\prime r'}$, on a $\FF_q \subseteq \FF_{q'}$ (au sens où $\FF_{q'}$ contient un sous-corps à $q$ éléments, qui est alors unique et isomorphe à $\FF_q$) si et seulement si $p = p'$ et $r|r'$. Le degré de l'extension $\FF_{q'} \bo \FF_q$ est alors $r'/r$. Si $q = p^r$ et $q' = p^{r'}$ avec $\pgcd(r,r') = r_0$, alors $\FF_q \cap \FF_{q'} = \FF_{q_0}$ où $q_0 = p^{r_0}$ dans n'importe quel corps contenant des sous-corps ayant $q$ et $q'$ éléments. \end{proposition2} \begin{proof} Si $\FF_q \subseteq \FF_{q'}$ où $q = p^r$ et $q' = p^{\prime r'}$, on doit nécessairement avoir $p = p'$ car ce sont les caractéristiques de ces deux corps. Par ailleurs, $\FF_{q'}$ est un espace vectoriel de dimension finie sur $\FF_q$, donc en notant $s$ sa dimension, on a $q' = q^s$, c'est-à-dire $r' = rs$ et $r|r'$ comme annoncé. Réciproquement, si $p = p'$ et $r|r'$, alors $q' = q^s$ où $s = r'/r$ est entier, donc le lemme \ref{lemme-divisibilite-x-q-r-x} montre que $X^{q'} - X$ est multiple de $X^q - X$ (dans $\ZZ[X]$ et en particulier dans $\FF_{q'}[X]$), et comme $X^{q'}-X$ est scindé sur $\FF_{q'}$, le polynôme $X^q-X$ l'est aussi, ce qui montre que $\FF_q \subseteq \FF_{q'}$ d'après \ref{sous-corps-a-q-elements}. La seconde affirmation est alors claire : $\FF_q \cap \FF_{q'}$ est un corps fini qui contient le corps fini à $p^{r_1}$ éléments si et seulement si $r_1 | r$ et $r_1 | r'$, c'est-à-dire si et seulement si $r_1 | r_0$ où $r_0 = \pgcd(r,r')$ --- autrement dit, il s'agit justement de $\FF_{q_0}$. \end{proof} \section{Polynômes irréductibles} \subsection{Polynômes minimaux et éléments conjugués} Lorsque $x \in \FF_{q^r}$, on rappelle que le \emph{polynôme minimal} (\refext{Alg}{polynome-minimal}) de $x$ sur $\FF_q$ (lequel est un sous-corps de $\FF_{q^r}$ d'après \ref{inclusions-corps-finis}) est le polynôme unitaire $h \in \FF_q[X]$ engendrant l'idéal dans $\FF_q[X]$ des polynômes $f$ tels que $f(x) = 0$, et que c'est l'unique polynôme unitaire irréductible dans $\FF_q[X]$ s'annulant en $x$ ; son degré est le degré $s = [\FF_q(x) : \FF_q]$ de $x$ sur $\FF_q$, qui divise le degré $r = [\FF_{q^r} : \FF_q]$ de l'extension. De plus, dans ces conditions, on a $\FF_q(x) \cong \FF_q[X]/(h) \cong \FF_{q^s}$ : en particulier, d'après \ref{petit-theoreme-fermat}, l'élément $x$ vérifie $x^{q^s} = x$, et $h(X) | (X^{q^s}-X)$. Réciproquement, on rappelle que si $h \in \FF_q[X]$ est un polynôme irréductible quelconque alors $\FF_q[X]/(h)$ est un corps, et la classe $x$ de $X$ modulo $h$ (c'est-à-dire dans $\FF_q[X]/(h) = \FF_q(x)$) a $h$ pour polynôme minimal. \begin{proposition2}\label{racines-polynome-minimal-corps-fini} Lorsque $x \in \FF_{q^r}$ a pour polynôme minimal $h$ sur $\FF_q$ et degré $s$ (divisant $r$), alors le polynôme $h$ est scindé sur $\FF_{q^r}$ et ses racines sont $x, x^q, x^{q^2}, \ldots, x^{q^{s-1}}$ : \[ h(X) = \prod_{i=0}^{s-1} (X-\Frob_q^i(x)) \] \end{proposition2} \begin{proof} Puisque $h \in \FF_q[X]$ et que $\Frob_q$ est un automorphisme de $\FF_{q^r}$ fixant $\FF_q$, on a $h(\Frob_q^i(x)) = \Frob_q^i(h(x)) = 0$ pour tout $i$, c'est-à-dire que les $x^{q^i}$ sont racines de $h$. Montrons maintenant que $x, x^q, \ldots, x^{q^{s-1}}$ sont deux à deux distincts, c'est-à-dire que l'ordre de $\Frob_q$ agissant sur $x$ (qui doit diviser $s$, comme on l'a expliqué) est exactement $s$ : or si on a $x^{q^t} = x$ pour $t \leq s$, on a $x \in \FF_{q^t}$ donc le degré $s$ de $x$ sur $\FF_q$ diviserait $t$, ce qui n'est possible que pour $t=s$. Finalement, on a trouvé $s$ racines distinctes dans $\FF_{q^r}$ pour un polynôme ($h$) de degré $s$, c'est-à-dire que ce polynôme est scindé avec la décomposition annoncée. \end{proof} Le phénomène qu'on vient de mettre en évidence, bien particulier aux corps finis, et qui traduira le fait que leur groupe de Galois absolu est abélien, est que pour tout polynôme irréductible $h \in \FF_q[X]$, le polynôme $h$ est scindé sur n'importe quel corps qui en contient une racine, autrement dit, \emph{le corps de rupture $\FF_q[X]/(h)$ de $h$ en est un corps de décomposition}. En particulier, en utilisant \ref{inclusions-corps-finis}, $\FF_{q^r}$ est un corps de décomposition de $h$ (supposé irréductible !) pour tout multiple $r$ du degré de $h$. Si $h$ n'est pas supposé irréductible, il découle de ce qui vient d'être dit que \emph{son corps de décompossition est $\FF_{q^r}$ où $r$ est le plus petit commun multiple des degrés des facteurs irréductibles de $h$}. De plus, on vient de voir que l'ordre de $\Frob_q$ agissant sur $x$ --- ou, par conséquent, sur $\FF_q(x)$ --- est exactement le degré $s$ de $x$ sur $\FF_q$. En utilisant le théorème de l'élément primitif (\refext{Alg}{element-primitif}), on peut conclure que $\Frob_q$ agissant sur $\FF_{q^r}$ est d'ordre exactement $r$ ; on fournira toutefois en \ref{existence-polynome-irreductible-tout-degre-corps-finis} une démonstration plus simple du théorème de l'élément primitif dans le cas particulier des corps finis. \begin{corollaire2}\label{elements-conjugues-corps-finis} Soient $x,x' \in \FF_{q^r}$. Les conditions suivantes sont équivalentes : \begin{enumerate} \item les polynômes minimaux de $x$ et $x'$ sur $\FF_q$ sont égaux, \item le polynôme minimal de $x$ s'annule en $x'$, \item tout polynôme $f \in \FF_q[X]$ à coefficient dans $\FF_q$ s'annulant en $x$ s'annule aussi en $x'$, \item il existe $i$ (qu'on peut supposer compris entre $0$ et $r-1$) tel que $x' = x^{q^i}$. \end{enumerate} \end{corollaire2} \begin{proof} L'équivalence entre les deux premières conditions (qui n'a rien de particulier au cas des corps finis) résulte du fait que le polynôme minimal d'un élément sur $\FF_q$ est l'unique polynôme unitaire irréductible sur $\FF_q$ s'annulant en cet élément. L'équivalence avec la troisième résulte de ce que les polynômes de $\FF_q[X]$ s'annulant en un élément de $\FF_{q^r}$ sont exactement les multiples du polynôme minimal de cet élément. Enfin, la proposition précédente montre que, quel que soit $x \in \FF_{q^r}$, les autres racines de son polynôme minimal sont justement les $x^{q^i}$ (pour $i$ qu'on peut supposer entre $0$ et $r-1$) : il y a donc équivalence entre (ii) et (iv). \end{proof} Des éléments $x,x' \in \FF_{q^r}$ vérifiant les conditions équivalentes énoncées dans le corollaire \ref{elements-conjugues-corps-finis} sont dits \emph{conjugués sur $\FF_q$}. La première condition montre qu'il s'agit bien d'une relation d'équivalence, et la seconde, que tout élément de $\FF_{q^r}$ a un nombre de conjugués sur $\FF_q$ égal à son degré sur $\FF_q$. (Cette définition et ces propriétés seront généralisées plus tard dans le cadre d'une extension de corps plus générale : cf. \refext{CG}{conjugues=racines}.) La proposition suivante généralise la dernière affirmation de \ref{petit-theoreme-fermat} : \begin{proposition2}\label{factorisation-x-q-r-x} La décomposition en facteurs irréductibles du polynôme $X^{q^r} - X$ dans $\FF_q[X]$ est donnée comme le produit de tous les polynômes unitaires irréductibles de $\FF_q[X]$ de degré divisant $r$, chacun apparaissant avec multiplicité $1$. Notamment, la somme des degrés de tous les polynômes unitaires irréductibles de $\FF_q[X]$ de degré divisant $r$ vaut $q^r$. \end{proposition2} \begin{proof} Si $h \in \FF_q[X]$ est irréductible de degré $s$ avec $s|r$, alors il est scindé à racines simples dans $\FF_{q^r}$ d'après \ref{racines-polynome-minimal-corps-fini} et les remarques qui suivent : il s'ensuit que $h$ divise $X^{q^r} - X$ (dans $\FF_{q^r}[X]$ donc dans $\FF_q[X]$). Comme tous les polynômes unitaires irréductibles de degré divisant $r$ dans $\FF_q[X]$ sont deux à deux premiers entre eux, le fait que $X^{q^r}-X$ soit multiple de chacun d'eux implique qu'il est multiple de leur produit. Pour conclure, il reste donc à montrer l'égalité des degrés, c'est-à-dire la dernière affirmation de l'énoncé : or cela se voit en écrivant $q^r$ (le cardinal de $\FF_{q^r}$) comme somme des cardinaux de chaque classe de conjugaison d'éléments sur $\FF_q$ (chacune étant associée à un unique polynôme minimal, dont elle a un cardinal égal au degré). \end{proof} \begin{exemple2}\label{irreductibles-sur-f16} Le polynôme $X^{16}-X$ se factorise sur $\FF_2$ comme : $X^{16}-X = X(X+1)\penalty-100 (X^2+X+1)\penalty-100 (X^4+X+1)\penalty0 (X^4+X^3+1)\penalty-50 (X^4+X^3+X^2+X+1)$. \end{exemple2} \subsubsection{}\label{definition-fonction-de-Moebius} On appelle \emph{fonction de Möbius} la fonction $\mu \colon \NN \to \ZZ$ définie par $\mu(n) = 0$ si $n$ est multiple du carré d'un entier autre que $1$ et $\mu(n) = (-1)^t$ si $n = p_1\cdots p_t$ avec $p_1,\ldots,p_t$ des nombres premiers deux à deux distincts (ainsi, $\mu(1) = 1$, $\mu(2) = -1$, $\mu(3) = -1$, $\mu(4) = 0$, $\mu(5) = -1$, $\mu(6) = 1$, $\mu(7) = -1$, $\mu(8) = 0$, $\mu(9) = 0$, $\mu(10) = 1$). On admet le résultat suivant : \begin{proposition2}[théorème d'inversion de Möbius] Si $\Gamma$ est un groupe abélien et que $f\colon \NN_{>0} \to \Gamma$ est une fonction quelconque, alors les deux formules suivantes sont équivalentes pour une fonction $g\colon \NN_{>0} \to \Gamma$ : \[ g(n) = \sum_{d|n} f(d) \] \[ f(n) = \sum_{d|n} \mu\big(\frac{n}{d}\big)\, g(d) \] \end{proposition2} \begin{corollaire2}\label{denombrement-polynomes-irreductibles-corps-finis} Le nombre de polynômes unitaires irréductibles de degré $n$ sur $\FF_q$ vaut \[ \frac{1}{n} \sum_{d|n} \mu\big(\frac{n}{d}\big)\, q^d \] Où $\mu$ est la fonction de Möbius. Lorsque $n \to +\infty$ (à $q$ fixé), ce nombre vaut $\frac{1}{n} q^n + O(q^{n/2})$. \end{corollaire2} \begin{proof} Pour ce qui est de la première affirmation, en notant $M(n)$ le nombre --- qu'on cherche à calculer --- d'unitaires irréductibles de degré $n$ sur $\FF_q$, la formule d'inversion de Möbius montre qu'il suffit de prouver $q^n = \sum_{d|n} d\,M(d)$ : or c'est justement la deuxième affirmation de l'énoncé de la proposition \ref{factorisation-x-q-r-x}. Pour ce qui est de l'estimation asymptotique, remarquons que dans la somme exacte, le terme $d=n$ vaut $\frac{1}{n} q^n$, le terme $d=\frac{n}{2}$, s'il existe (c'est-à-dire, si $n$ est pair), vaut $-\frac{1}{n} q^{n/2}$, et tous les autres termes, dont le nombre est au plus $n$, sont chacun $O(q^{n/3})$ --- leur somme est donc bien $O(q^{n/2})$. \end{proof} Même sans utiliser la formule d'inversion de Möbius, on peut au moins démontrer, dans le même esprit que cette estimation asymptotique : \begin{corollaire2}\label{existence-polynome-irreductible-tout-degre-corps-finis} Sur $\FF_q$, il existe au moins un polynôme irréductible de chaque degré $r$. De façon équivalente, dans $\FF_{q^r}$, il existe un élément de degré $r$ sur $\FF_q$. \end{corollaire2} \begin{proof} Le nombre d'éléments de $\FF_{q^r}$ de degré $ r q^{r/2}$, soit $q^{r/2} > r$, ce qui se produit dès que $2^r > r^2$, donc dès que $r > 4$. Pour les valeurs plus petites de $r$, on constate que $q^4 > q^2 + q$ et $q^3 > q$ et $q^2 > q$ (et $q > 0$...) pour tout $q \geq 2$. \end{proof} On verra en \ref{cyclicite-groupe-multiplicatif-corps} un résultat plus fin : l'existence d'éléments ou de polynômes \emph{primitifs}. Avec les remarques qui suivent \ref{racines-polynome-minimal-corps-fini}, ceci montre notamment que $\Frob_q$ agissant sur $\FF_{q^r}$ est d'ordre exactement $r$. \subsection{Critères d'irréductibilité} \begin{proposition2}[critère d'irréductibilité de Rabin]\label{critere-rabin} Un polynôme $h \in \FF_q[X]$ de degré $r$ est irréductible si et seulement si il vérifie la conjonction des deux conditions suivantes : \begin{itemize} \item le polynôme $h$ divise $X^{q^r}-X$, \item le polynôme $h$ est premier avec $X^{q^s}-X$ pour tout $s$ diviseur strict de $r$ (ou simplement les diviseurs immédiats de $r$, c'est-à-dire les $r/\ell$ avec $\ell$ diviseur premier de $r$). \end{itemize} \end{proposition2} \begin{proof} Si $h$ est irréductible de degré $r$, alors, d'après \ref{factorisation-x-q-r-x}, $h$ divise $X^{q^r}-X$, et s'il divise $X^{q^s}-X$ pour $s|r$, on doit avoir $r|s$, ce qui n'est possible que pour $s=r$ et la seconde condition est démontrée ($h$ étant supposé irréductible, s'il ne divise pas $X^{q^s}-X$, il est premier avec lui). Réciproquement, si $h$ vérifie les deux conditions annoncées, et si $h_1$ en est un facteur irréductible, le degré $r_1$ de $h_1$ doit diviser $r$ d'après la première condition (toujours en utilisant \ref{factorisation-x-q-r-x}), et il ne peut pas être un diviseur strict de $r$ d'après la seconde condition (qui assure que $h_1$ ne divise pas $X^{q^s}-X$) : donc $r_1=r$ et $h_1=h$. Ceci montre que $h$ est irréductible. Le fait qu'il suffise de tester la seconde condition pour les diviseurs $s$ de la forme $r/\ell$ avec $\ell$ premier résulte de ce que $X^{q^s}-X$ divise $X^{q^{s'}}-X$ si $s|s'$. \end{proof} \begin{remarques2}\label{remarques-critere-rabin} \begin{itemize} \item On ne peut pas se contenter de vérifier l'une des deux conditions énoncées : l'exemple du polynôme $X^6+X^5+X^4+X^3+X^2+X+1 = (X^3+X^2+1)\penalty-100 (X^3+X+1) \in \FF_2[X]$, qui n'est pas irréductible mais vérifie la première condition (il divise déjà $X^8-X$) montre que la première condition, seule, n'assure pas l'irréductibilité ; et l'exemple du polynôme $X^5 + X^4 + 1 = (X^2+X+1)\penalty-100 (X^3+X+1) \in \FF_2[X]$, qui n'est pas irréductible mais est premier à $X^2-X$ montre que la seconde condition, seule, n'est pas non plus suffisante. On peut aussi donner l'exemple de $X^6 + X^5 + X = X (X^2+X+1) (X^3+X+1) \in \FF_2[X]$, qui n'est pas irréductible bien qu'il vérifie la première condition et aussi la seconde condition dans laquelle on a affaibli « $h$ est premier avec $X^{q^s}-X$ » en « $h$ ne divise pas $X^{q^s}-X$ » (pour tout diviseur $s$ de $r$, soit ici $s \in \{1,2,3\}$). \item Le critère de Rabin fournit un \emph{algorithme} permettant de tester l'irréductibilité d'un polynôme $h \in \FF_q[X]$ de degré $r$ en un nombre raisonnable (i.e., polynomial\footnote{On peut par exemple montrer qu'il s'effectue en au pire $O(r^{2+\varepsilon})$ opérations pour tout $\varepsilon>0$, où la constante impliquée par le $O$ dépend de $\varepsilon$ et $q$.} en $r$) d'opérations dans $\FF_q$ : en effet, la première condition du critère s'exprime également comme $X^{q^r} \equiv X \pmod{h}$, ce qui se teste en calculant $X^{q^r}$ dans $\FF_q[X]/(h)$ au moyen d'un algorithme d'exponentiation rapide, et la seconde condition, pour un $s$ donné, peut se tester au moyen de l'algorithme d'Euclide étendu (pour calculer le pgcd), dont la première étape consiste à calculer le reste de la division euclidienne de $X^{q^s}-X$ par $h$, ce qui peut de nouveau se faire en travaillant dans $\FF_q[X]/(h)$. \item Une fois qu'on dispose d'un algorithme permettant de tester l'irréductibilité d'un polynôme $h \in \FF_q[X]$ de degré $r$ donné, il est possible de \emph{générer} des polynômes irréductibles de degré $r$ selon le principe simple suivant : tirer un polynôme (unitaire) de degré $r$ au hasard, tester son irréductibilité, et recommencer jusqu'à trouver un polynôme irréductible. En vertu de l'asymptotique trouvée en \ref{denombrement-polynomes-irreductibles-corps-finis}, parmi les $q^r$ polynômes unitaires de degré $r$ sur $\FF_q$, une proportion d'environ $\frac{1}{r}$ d'entre eux sont irréductibles, donc l'algorithme qu'on vient de décrire réussira en environ $r$ essais en moyenne. Enfin, il convient de remarquer que la connaissance d'un polynôme $h$ irréductible de degré $r$ sur $\FF_p$ permet de représenter $\FF_{p^r}$ comme $\FF_p[X]/(h)$ (les calculs dans $\FF_p = \ZZ/p\ZZ$ sont, pour leur part, faciles) : en combinant avec ce qui vient d'être dit, on dispose des outils algorithmiques permettant d'effectuer des calculs dans tous les corps finis. \end{itemize} \end{remarques2} \begin{exemple2}\label{exemple-numerique-critere-rabin} Montrons sur l'exemple de $h = X^6 -2 X^4 + 3 X^3 - X^2 - X - 2 \in \FF_7[X]$ comment on peut appliquer le critère de Rabin en pratique, même sans ordinateur. On commence par calculer la table des restes modulo $h$ des puissances $X^7, X^{7\times 2}, X^{7\times 3}, \ldots, X^{7\times 6}$ de l'indéterminée : \[ \begin{array}{r@{\,}l} X^7 &\equiv 2X^5 - 3X^4 + X^3 + X^2 + 2X \pmod{h}\\ X^{14} &\equiv -3X^5 - 2X^4 + 2X^3 + 2X^2 + 2X + 2 \pmod{h}\\ X^{21} &\equiv -2X^5 + 3X^4 - 3X^3 - X^2 - 1 \pmod{h}\\ X^{28} &\equiv 3X^5 - 3X^4 - 2X^3 + 2X \pmod{h}\\ X^{35} &\equiv X^5 - 3X^4 - 2X^3 - 2X + 3 \pmod{h}\\ X^{42} &\equiv -3X^5 + X^4 + X^3 - X^2 + X \pmod{h}\\ \end{array} \] (la première ligne se calcule par division euclidienne de $X^7$ par $h$, puis chaque ligne suivante en multipliant par $2X^5 - 3X^4 + X^3 + X^2 + 2X$ et en effectuant une nouvelle division euclidienne par $h$). Il est également utile de préparer une table des valeurs du Frobenius sur le corps de base : ici, $a \mapsto a^7$ sur $\FF_7$ est bien sûr l'identité. Au moyen de ces deux tables, on peut facilement élever n'importe quel polynôme à la puissance $7$ modulo $h$, donc calculer $X^{7^i}$ pour $i$ allant de $1$ à $6$ modulo $h$ : \[ \begin{array}{r@{\,}l} X^7 &\equiv 2X^5 - 3X^4 + X^3 + X^2 + 2X \pmod{h}\\ X^{7^2} &\equiv 2^7 X^{35} - 3^7 X^{28} + X^{21} + X^{14} + 2^7 X^7\\ &\equiv -X^5 - 2X^4 + 3X^3 + 3X^2 + 3X \pmod{h}\\ X^{7^3} &\equiv -X^{35} - 2^7 X^{28} + 3^7 X^{21} + 3^7 X^{14} + 3^7 X^7\\ &\equiv -2X^5 + 3X^4 - X^3 - X^2 + 3X \pmod{h}\\ X^{7^4} &\equiv -2^7 X^{35} + 3^7 X^{28} - X^{21} - X^{14} + 3^7 X^7\\ &\equiv -3X^5 + X^4 + 2X^3 + 2X^2 \pmod{h}\\ X^{7^5} &\equiv -3^7 X^{35} + X^{28} + 2^7 X^{21} + 2^7 X^{14} \\ &\equiv -3 X^5 + X^4 + 2 X^3 + 2 X^2 - 2 X \pmod{h}\\ X^{7^6} &\equiv -3^7 X^{35} + X^{28} + 2^7 X^{21} + 2^7 X^{14} - 2^7 X^7 \\ &\equiv X \pmod{h}\\ \end{array} \] L'égalité $X^{7^6} \equiv X \pmod{h}$ montre que la première partie du critère de Rabin est vérifiée. Pour la seconde partie, il s'agit de continuer l'algorithme d'Euclide pour calculer le pgcd de $X^{7^2} - X \equiv -X^5 - 2X^4 + 3X^3 + 3X^2 + 2X$ et de $X^{7^3} - X\equiv -2X^5 + 3X^4 - X^3 - X^2 + 2X$ avec $h$ : or au prix de nouvelles divisions euclidiennes, on trouve \[ \begin{array}{c} h \equiv -2X^4 + 2X^2 + 2X - 2 \pmod{-X^5 - 2X^4 + 3X^3 + 3X^2 + 2X}\\ -X^5 - 2X^4 + 3X^3 + 3X^2 + 2X \equiv 2X^3 + X + 2 \pmod{-2X^4 + 2X^2 + 2X - 2}\\ -2X^4 + 2X^2 + 2X - 2 \equiv 3 X^2 - 3 X - 2 \pmod{2X^3 + X + 2}\\ 2X^3 + X + 2 \equiv 2 X + 1 \pmod{3 X^2 - 3 X - 2}\\ 3 X^2 - 3 X - 2 \equiv 2 \pmod{2X + 1}\\ \end{array} \] ce qui montre que $X^{7^2} - X$ est premier avec $h$, et pour ce qui est de $X^{7^3} - X$ : \[ \begin{array}{c} h \equiv -2X^4 + X^2 - 3X - 2 \pmod{-2X^5 + 3X^4 - X^3 - X^2 + 2X}\\ -2X^5 + 3X^4 - X^3 - X^2 + 2X \equiv -2X^3 + 3X - 3 \pmod{-2X^4 + X^2 - 3X - 2}\\ -2X^4 + X^2 - 3X - 2 \equiv -2X^3 + 3X - 3 \pmod{-2X^3 + 3X - 3}\\ -2X^3 + 3X - 3 \equiv -2 X^2 - 2 \pmod{-2X^3 + 3X - 3}\\ -2X^3 + 3X - 3 \equiv -2 X - 3 \pmod{-2 X^2 - 2}\\ -2 X^2 - 2 \equiv -3 \pmod{-2 X - 3}\\ \end{array} \] --- ce qui conclut la vérification du critère de Rabin. Tous ces calculs montrent donc que $h = X^6 -2 X^4 + 3 X^3 - X^2 - X - 2$ est irréductible dans $\FF_7[X]$. Par la suite, nous passerons normalement sous silence toutes les vérifications du fait qu'un polynôme univarié à coefficiens dans un corps fini est irréductible. \end{exemple2} Le critère suivant, dans le même esprit que celui de Rabin, et plus simple à énoncer, est plus généralement efficace quand il s'agit de générer des polynômes irréductibles par le procédé expliqué à la fin de \ref{remarques-critere-rabin} : \begin{proposition2}[critère d'irréductibilité de Ben-Or]\label{critere-ben-or} Un polynôme $h \in \FF_q[X]$ de degré $r$ est irréductible si et seulement si $h$ est premier avec $X^{q^i}-X$ pour tout $1 \leq i \leq \frac{r}{2}$ (c'est-à-dire $1 \leq i \leq \lfloor\frac{r}{2}\rfloor$ où $\lfloor\tiret\rfloor$ désigne la partie entière). \end{proposition2} \begin{proof} D'après \ref{factorisation-x-q-r-x}, les facteurs irréductibles de $X^{q^i}-X$ pour un $1\leq i r/s$. \end{proof} \begin{proof}[Seconde démonstration] Soit $h$ un facteur irréductible de $f$ dans $\FF_{q^s}[X]$, et $x$ une racine de $h$ dans $\FF_{q^r}$ (qui existe puisque $f$, donc $h$, est scindé sur $\FF_{q^r}$). Le degré de $x$, c'est-à-dire de $\FF_q(x) = \FF_{q^r}$, sur $\FF_q$ vaut $r$, et par conséquent (\ref{inclusions-corps-finis} ou \refext{Alg}{multiplicativité degré}) son degré sur $\FF_{q^s}$ vaut $r/s$ : c'est donc le degré de $h$ (polynôme minimal de $x$ sur $\FF_{q^s}$). On a vu en \ref{racines-polynome-minimal-corps-fini} que les racines de $f$ (dans $\FF_{q^r}$) sont les $\Frob_q^i(x)$ pour $i$ allant de $0$ à $r-1$, et que celles de $h$ sont les $(\Frob_{q^s})^j(x) = \Frob_q^{js}(x)$ pour $j$ allant de $0$ à $(r/s)-1$. Pour $i$ allant de $0$ à $s-1$, le polynôme $\Frob_q^i(h) \in \FF_{q^s}[X]$ s'annule en $\Frob_q^i(x)$ et en tous les $\Frob_q^{i+js}(x)$ ; il est irréductible puisque $\Frob_q^i$ est un automorphisme de $\FF_{q^s}[X]$ (et que $h$ est irréductible), et tous ces polynômes $\Frob_q^i(h)$ sont premiers entre eux puisque leurs racines dans $\FF_{q^r}$, où ils se scindent, sont disjointes : par conséquent, $f$ est bien égal, à une constante près, au produit des $\Frob_q^i(h)$ (pour $i$ allant de $0$ à $s-1$). \end{proof} Voir \ref{descindage-polynomes-tours-corps-finis} pour une sorte de réciproque de cette affirmation. \begin{proposition2}\label{polynomes-restent-irreductibles-corps-finis} Soit $h \in \FF_q[X]$ irréductible de degré $r$, et soit $s$ premier avec $r$. Alors $h$ vu dans $\FF_{q^s}[X]$ est encore irréductible. \end{proposition2} \begin{proof}[Première démonstration] D'après le critère de Rabin (\ref{critere-rabin}), le polynôme $h$ divise $X^{q^r}-X$, et est premier avec $X^{q^t}-X$ pour tout $t$ diviseur strict de $r$ : on veut prouver la même chose en remplaçant $q$ par $q^s$. Le fait que $X^{q^r}-X$ divise $X^{(q^s)^r}-X$ (et donc que $h$ divise ce dernier) résulte du lemme \ref{lemme-divisibilite-x-q-r-x} ; par ailleurs, un diviseur de $h$ et de $X^{q^{st}}-X$ devrait diviser à la fois $X^{q^r}-X$ et $X^{q^{st}}-X$ donc leur pgcd, qui vaut $X^{q^t}-X$ d'après \ref{lemme-pgcd-x-q-r-x} (puisque le pgcd de $r$ et $st$ est $t$). \end{proof} \begin{proof}[Seconde démonstration] Soit $h_1$ un facteur irréductible de $h$ dans $\FF_{q^s}[X]$, et $x$ une racine de $h_1$ dans $\FF_{q^{rs}}$ (qui existe puisque $h$ est scindé sur $\FF_{q^r}$, donc dans $\FF_{q^{rs}}$, donc $h_1$ est scindé dans $\FF_{q^{rs}}$). Alors $(\Frob_{q^s})^i(x) = \Frob_q^{is}(x)$ est racine de $h_1$ pour tout $i$. Or, $s$ étant premier avec $r$, l'entier $is$ prend toutes les valeurs possibles modulo $r$, donc $\Frob_q^{is}(x)$ parcourt toutes les racines de $h$ (cf. \ref{racines-polynome-minimal-corps-fini}) : ceci montre que toute racine de $h$ est racine de $h_1$ et finalement $h = h_1$ est irréductible dans $\FF_{q^s}[X]$. \end{proof} \begin{corollaire2}\label{corollaire-scindage-partiel-polynomes-corps-finis} Soit $f \in \FF_q[X]$ irréductible de degré $r$, et $s > 0$ un entier naturel, et soit $d = \pgcd(r,s)$. Alors $f$ vu dans $\FF_{q^s}[X]$ est produit de $d$ facteurs irréductibles chacun de degré $r/d$. Si $h$ est l'un de ces facteurs, alors tous sont donnés par les $\Frob_q^i(h)$ (où par là on désigne le polynôme de même degré que $h$, dont les coefficients sont image de ceux de $h$ par $\Frob_q^i$, sans faire agir ce dernier sur l'indéterminée) pour $i$ allant de $0$ à $d-1$. \end{corollaire2} \begin{proof} C'est une conséquence immédiate des propositions \ref{scindage-partiel-polynomes-corps-finis} et \ref{polynomes-restent-irreductibles-corps-finis}, en appliquant la première pour décrire $f$ dans $\FF_{q^d}[X]$ et la seconde pour voir que chacun des facteurs irréductibles reste irréductible en passant de $\FF_{q^d}[X]$ à $\FF_{q^s}[X]$ (vu que $s/d$ est premier avec $r$). \end{proof} La proposition suivante doit être vue comme un complément à \ref{scindage-partiel-polynomes-corps-finis} : \begin{proposition2}\label{descindage-polynomes-tours-corps-finis} Soit $h \in \FF_{q^s}[X]$ unitaire irréductible de degré $t$. Alors le polynôme $f = \prod_{i=0}^{s-1}\Frob_q^i(h)$, de degré $st$, appartient à $\FF_q[X]$, et il est irréductible si et seulement si le ppcm des degrés sur $\FF_q$ des coefficients de $h$ est égal à $s$. \end{proposition2} \begin{proof} Le fait que $f$ appartienne à $\FF_q[X]$ vient de ce que $\Frob_q(f) = f$ (on rappelle que $\Frob_q$ opère uniquement sur les coefficients des polynômes), comme il résulte aisément de $\Frob_q^s(h) = h$. Dire que le ppcm des degrés sur $\FF_q$ des coefficients de $h$ est égal à $s$ signifie (cf. \ref{racines-polynome-minimal-corps-fini}) que $\Frob_q$ a pour période exactement $s$ en agissant sur $h$, c'est-à-dire que tous les $\Frob_q^i(h)$ (pour $i$ allant de $0$ à $s-1$) sont distincts et donc, étant unitaires et irréductibles sur $\FF_{q^s}$, premiers entre eux. Si c'est le cas, alors $f$ est irréductible sur $\FF_q$, car aucun sous-ensemble non trivial de ses facteurs irréductibles $\Frob_q^i(h)$ sur $\FF_{q^s}$ n'est stable par $\FF_q$ donc ne définit de polynôme de $\FF_q[X]$. Réciproquement, si $f$ est irréductible dans $\FF_q[X]$, il a $st$ racines distinctes dans $\FF_{q^{st}}$, donc tous les $\Frob_q^i(h)$ sont distincts. \end{proof} On étudiera en \refext{ACF}{remarque-tours-corps-finis} la question du rapport entre les présentations de $\FF_{q^{st}}$, dans les conditions de la proposition précédente, données par $\FF_q[X]/(f)$ et par $\FF_{q^s}[X]/(h)$. \section{Éléments primitifs et groupe multiplicatif} \subsection{Éléments primitifs} \begin{théorème2}\label{cyclicite-groupe-multiplicatif-corps} Tout sous-groupe fini du groupe multiplicatif d'un corps est cyclique. En particulier, le groupe multiplicatif d'un corps fini est cyclique. \end{théorème2} \begin{exercice2} En déduire une seconde démonstration de \ref{existence-polynome-irreductible-tout-degre-corps-finis}. \XXX \end{exercice2} \begin{démo} Soient $K$ un corps et $G⊆K^×$ un sous-groupe fini. Pour tout entier $n$, l'ensemble $G[n]$ des éléments de $G$ d'ordre divisant $n$ est de cardinal au plus $n$ car il est inclus dans l'ensemble des racines dans $K$ du polynôme $X^n-1$. La conclusion résulte donc du lemme suivant. \end{démo} \begin{lemme2}\label{lemme-detection-groupes-cycliques} Soit $G$ un groupe fini non nécessairement abélien d'ordre $n$ tel que pour tout $d$ divisant $n$ on ait \[\# G[d]≤d\] en notant $G[d]$ l'ensemble des éléments d'ordre divisant $d$. Alors $G$ est cyclique. \end{lemme2} \begin{démo} Pour tout $d$ divisant $n$, notons $X_d$ l'ensemble des éléments d'ordre exactement $d$. On souhaite montrer que $X_n$ est non vide. Commençons par montrer que si un $X_d$ est non vide, il est d'ordre $φ(d)$. En effet, si $x∈X_d$, l'ensemble à $d$ éléments $\{1,x,\dots,x^{d-1}\}$ est inclus dans — donc égal à — $G[d]$. Pour un tel $d$, $G[d]$ est cyclique d'ordre $d$ et $X_d$ est l'ensemble de ses générateurs, donc de cardinal $φ(d)$. Il résulte de la formule $∑_{d|n} φ(d)=n$ et de l'égalité $G=∐_{d|n} X_d$ (le symbole $\coprod$ désignant la réunion disjointe) que chaque $X_d$ est non vide. En particulier c'est le cas de $X_n$. \end{démo} \begin{definition2}\label{element-primitif-corps-fini} Un élément $x \in \FF_q^\times$ qui engendre le groupe multiplicatif $\FF_q^\times$ est dit \emph{primitif}. \end{definition2} Le théorème \ref{cyclicite-groupe-multiplicatif-corps} affirme donc qu'il existe dans (le groupe multiplicatif de) tout corps fini $\FF_q$ des éléments primitifs, et leur nombre est alors $\varphi(q-1)$ (nombre de générateurs d'un groupe cyclique d'ordre $q-1$), où $\varphi$ désigne la fonction indicatrice d'Euler. Plus généralement, le nombre d'éléments d'ordre exactement $d$ dans $\FF_q^\times$ est $\varphi(d)$ si $d|(q-1)$ et $0$ sinon (comparer avec la démonstration du lemme \ref{lemme-detection-groupes-cycliques}). \begin{remarques2}\label{elements-et-polynomes-primitifs} Si $x \in \FF_{q^r}^\times$ est primitif, alors tout élément conjugué à $x$ sur $\FF_q$ (cf. \ref{elements-conjugues-corps-finis} et les remarques qui suivent) est encore primitif (en effet, l'ordre multiplicatif d'un élément est préservé par l'automorphisme de corps $\Frob_q \colon z \mapsto z^q$). Par ailleurs, le degré de $x$ sur $\FF_q$ est alors exactement $r$ (et non un diviseur strict $s$ de $r$) : en effet, si on avait $x \in \FF_{q^s}$ avec $s0$ : alors $\sum_{x\in\FF_q} x^s = \sum_{x\in\FF_q^\times} x^s$, et en appelant $g$ un élément primitif de $\FF_q$, cette somme s'écrit encore $\sum_{i=0}^{q-2} g^{si}$. Si $g^s = 1$, ce qui se produit exactement lorsque $s$ est multiple de $q-1$, la somme vaut $q-1$, c'est-à-dire $-1$ dans $\FF_q$. Sinon, on a $\sum_{i=0}^{q-2} g^{si} = \frac{g^{s(q-1)}-1}{g^s-1} = 0$. \end{proof} \subsection{Polynômes cyclotomiques et corps finis} \subsubsection{} On rappelle que les polynômes cyclotomiques $\Phi_n \in \ZZ[X]$ sont les uniques polynômes unitaires à coefficients rationnels (et en fait, entiers) vérifiant pour tout $n$ la relation $X^n-1 = \prod_{d|n} \Phi_d(X)$ (le produit étant pris sur tous les $d$ divisant $n$). On peut aussi écrire $\Phi_n(X) = \prod_\zeta (X-\zeta)$ pour $\zeta$ parcourant l'ensemble des racines primitives $n$-ièmes de l'unité dans une extension quelconque de $\QQ$ les contenant. Les $\Phi_n$ sont irréductibles dans $\ZZ[X]$ (et deux à deux distincts, donc deux à deux premiers entre eux), et le degré de $\Phi_n$ est $\varphi(n)$. La formule $\Phi_n(X) = \prod_\zeta (X-\zeta)$ pour $\zeta$ parcourant l'ensemble des racines primitives $n$-ièmes de l'unité est encore valable dans n'importe quel corps, de caractéristique ne divisant pas $n$, où il existe une --- et donc $\varphi(n)$ --- racine primitive $n$-ième de l'unité. Si $q$ et $n$ sont premiers entre eux où $q$ est une puissance d'un nombre premier $p$, considérons un $r$ tel que $n|(q^r-1)$ (c'est-à-dire $q^r \equiv 1 \pmod{n}$ ; un tel $r$ existe évidemment : par exemple l'ordre multiplicatif de $q$ modulo $n$ convient) ; dans ces conditions, si $\xi$ est un élément primitif de $\FF_{q^r}$, il est facile de voir que $\zeta = \xi^{(q^r-1)/n}$ est d'ordre multiplicatif exactement $n$ dans $\FF_{q^r}$, c'est-à-dire, est une racine primitive $n$-ième de l'unité. Dans ces conditions (lorsque $n|(q^r-1)$), on a encore $\Phi_n(X) = \prod_\zeta (X-\zeta)$ dans $\FF_{q^r}$, où $\zeta$ parcourt les racines primitives $n$-ièmes de l'unité dans $\FF_{q^r}$, c'est-à-dire les $\varphi(n)$ éléments d'ordre exactement $n$ dans $\FF_{q^r}^\times$. En particulier, les $\Phi_n$ pour $n$ premier avec $q$ sont encore deux à deux premiers entre eux dans $\FF_q[X]$. On a, de façon analogue à \ref{factorisation-x-q-r-x} : \begin{proposition2}\label{factorisation-phi-q-r-1} La décomposition en facteurs irréductibles du polynôme $\Phi_{q^r-1}(X)$ dans $\FF_q[X]$ est donnée comme le produit de tous les polynômes unitaires primitifs de $\FF_q[X]$ de degré $r$ (au nombre de $\frac{1}{r}\varphi(q^r-1)$, cf. \ref{elements-et-polynomes-primitifs}), chacun apparaissant avec multiplicité $1$. \end{proposition2} \begin{proof} D'après ce qui a été dit, $\Phi_{q^r-1}$ est scindé sur $\FF_{q^r}$ et ses racines sont exactement les éléments primitifs de $\FF_{q^r}$ (chacune avec multiplicité $1$) ; et sur $\FF_q$ on a vu que les polynômes minimaux de ces éléments primitifs de $\FF_{q^r}$ sont les polynômes unitaires primitifs de degré $r$ sur $\FF_q$. \end{proof} \begin{exemple2} Dans $\FF_2$, le polynôme $\Phi_{15}(X) = X^8 - X^7 + X^5 - X^4 + X^3 - X + 1 \in \ZZ[X]$ se factorise comme $(X^4 + X + 1)\penalty-100 (X^4 + X^3 + 1)$ : ces deux facteurs sont les $\frac{1}{4} \varphi(15) = 2$ polynômes primitifs de degré $4$ sur $\FF_2$. (Comparer avec \ref{primitifs-sur-f16}.) \end{exemple2} Plus généralement : \begin{proposition2}\label{factorisation-phi-n} Soit $n$ un entier naturel premier avec $q$ (où $q$ est une puissance d'un nombre premier). Alors la décomposition en facteurs irréductibles du polynôme $\Phi_n(X)$ dans $\FF_q[X]$ est formée de $\frac{1}{r}\varphi(n)$ facteurs irréductibles chacun de degré $r$, où $r$ est l'ordre multiplicatif de $q$ modulo $n$ (c'est-à-dire le plus petit entier naturel tel que $q^r \equiv 1 \pmod{n}$). En particulier, (toujours sous l'hypothèse que $n$ et $q$ sont premiers entre eux, cf. \ref{irreductibilite-phi-n-complement}) $\Phi_n(X)$ est irréductible dans $\FF_q[X]$ exactement lorsque $q$ engendre le groupe multiplicatif $(\ZZ/n\ZZ)^\times$. \end{proposition2} \begin{proof} Soit $r$ l'ordre multiplicatif de $q$ modulo $n$. Il existe alors dans $\FF_{q^r}$ une racine primitive $n$-ième de l'unité $\zeta$ : ansi, $\Phi_n$ est scindé sur $\FF_{q^r}$ et on peut écrire $\Phi_n(X) = \prod (X-\zeta^j)$ pour $j$ parcourant (les $\varphi(n)$ éléments de) $(\ZZ/n\ZZ)^\times$. Le degré de $\zeta^j$ sur $\FF_q$ (pour $j \in (\ZZ/n\ZZ)^\times)$) est le plus petit $i$ tel que $\zeta^{j\,q^i} = \zeta^j$, c'est-à-dire tel que $j q^i \equiv j \pmod{n}$, ce qui équivaut à $q^i \equiv 1 \pmod{n}$ (puisque $j$ est inversible modulo $n$), c'est donc exactement $r$. Ainsi, $\Phi_n$ est scindé sur $\FF_{q^r}$, et les polynômes minimaux sur $\FF_q$ de ses racines sur $\FF_{q^r}$ sont chacun de degré $r$ : ceci prouve que $\Phi_n$ s'écrit sur $\FF_q$ comme produit de $\frac{1}{r}\varphi(n)$ polynômes irréductibles de degré $r$. La dernière affirmation signifie simplement que $q$ engendre le groupe multiplicatif $(\ZZ/n\ZZ)^\times$ exactement lorsque son ordre multiplicatif modulo $n$ est $\varphi(n)$. \end{proof} On peut dire (cf. les remarques suivant \ref{racines-polynome-minimal-corps-fini}) que le corps de décomposition de $\Phi_n$ sur $\FF_q$ (toujours sous l'hypothèse que $n$ n'est pas multiple de $p$) est $\FF_{q^r}$ où $r$ est l'ordre multiplicatif de $q$ modulo $n$. Ce corps de décomposition, qui est le corps de rupture d'un quelconque des facteurs irréductibles (tous de degré $r$) de $\Phi_n$ sur $\FF_q$, peut se noter $\FF_q(\zeta_n)$, en désignant par $\zeta_n$ une racine primitive $n$-ième de l'unité dans $\FF_{q^r}$. Il faut cependant se garder de croire que les différents choix possibles de $\zeta_n$ soient interchangeables (plus précisément, qu'ils seraient conjugués sous l'action de $\Frob_q$) : même si le corps $\FF_q(\zeta_n) = \FF_{q^r}$ engendré par $\zeta_n$ est le même quel que soit le choix effectué, le polynôme minimal de $\zeta_n$ sur $\FF_q$, lui, ne l'est pas (c'est justement l'un quelconque des $\frac{1}{r} \varphi(n)$ facteurs irréductibles de $\Phi_n$) ; ceci diffère de la situation sur $\QQ$ où toutes les racines primitives $n$-ièmes de l'unité sont interchangeables (précisément, on dira qu'elles sont conjuguées par le groupe de Galois), non seulement elles engendrent le même corps $\QQ(\zeta_n)$ mais aussi elles ont le même polynôme minimal sur $\QQ$, qui est justement $\Phi_n$. \begin{corollaire2} Le polynôme $Φ_ℓ$ a une racine dans $𝐅_p$ si et seulement si $p ≡ 1 \mod ℓ$. \end{corollaire2} \begin{proposition2} Soit $P ∈ 𝐙[X]$ un polynôme non constant. Il existe une infinité de nombres premiers $p$ tels que $P$ ait une racine dans $𝐅_p$. \end{proposition2} % Variante (plus dure) : scindé % Čebotarev pour l'absence de racine si P irréductible. \begin{démo} C'est une variante de la méthode d'Euclide pour montrer qu'il existe une infinité de nombres premiers. Supposons que les $P(n)$, $n ∈ 𝐍$ n'aient qu'un nombre fini de diviseurs premiers $ℓ₁,ℓ₂,…,ℓ_r$. Pour chaque $n ∈ 𝐍$, l'entier $P(n ℓ₁ℓ₂\ cdots ℓ_r)$ est congru à $P(0)$ modulo chaque $ℓ_i$. Si $P(0)=±1$, il en résulte que $P(nℓ₁ℓ₂\ cdots ℓ_r)$ est premier à chacun des $ℓ_i$. Or, si $n$ est grand, $P(n ℓ₁ℓ₂\ cdots ℓ_r)$ est grand (en valeur absolue) donc a un diviseur premier. Absurde. Dans le cas général, on observe que si $a=P(0)$, on a $P(aX)=aQ(X)$ où $Q(0)=1$. Si $Q$ a une racine modulo un nombre premier $p$, il en est de même de $P$. \end{démo} \begin{corollaire2} \label{Dirichlet faible} Soit $ℓ$ un nombre premier. Il existe une infinité de nombres premiers $p$ congrus à $1$ modulo $ℓ$. \end{corollaire2} \begin{proposition2} Soit $h$ un polynome irréductible unitaire sur $\FF_q$, autre que $X$. Alors il existe un unique $n$ premier à $q$ tel que $h$ divise $\Phi_n$ : ce $n$ divise $q^r-1$ où $r$ est le degré de $h$. Il s'agit exactement de l'ordre multiplicatif d'une racine (quelconque) de $h$ dans $\FF_{q^r}$. \end{proposition2} \begin{proof} On a $X^{q^r-1}-1 = \prod_{n|(q^r-1)} \Phi_n(X)$ par définition des $\Phi_n$, donc $X^{q^r}-X = X\,\prod_{n|(q^r-1)} \Phi_n(X)$. D'après \ref{factorisation-x-q-r-x}, le polynôme irréductible $h$ divise ce produit : il doit donc diviser un des $\Phi_n$ avec $n|(q^r-1)$. Comme les $\Phi_n$ pour $n$ premier à $q$ sont premiers entre eux, il ne peut en diviser un autre. Enfin, dire qu'une racine de $h$ (dans $\FF_{q^r}$) est racine de $\Phi_n$ signifie précisément que son ordre multiplicatif est exactement $n$. \end{proof} \begin{exemples2} \begin{itemize} \item Le polynôme $\Phi_5(X) = X^4+X^3+X^2+X+1 \in \ZZ[X]$ demeure irréductible dans $\FF_2$ car $2$ engendre $(\ZZ/5\ZZ)^\times$. Il n'est, naturellement, pas primitif (puisque ses racines dans $\FF_{2^4}$ sont d'ordre $5$ et non $15$). On retrouve-là un exemple déjà donné en \ref{primitifs-sur-f16}. \item Le polynôme $\Phi_{9}(X) = X^6 + X^3 + 1 \in \ZZ[X]$ demeure irréductible dans $\FF_2$ car $2$ engendre $(\ZZ/9\ZZ)^\times$. Il n'est, naturellement, pas primitif (puisque ses racines dans $\FF_{2^6}$ sont d'ordre $9$ et non $63$). \item Le polynôme $\Phi_{17}(X) = X^{16} + X^{15} + \cdots + X + 1 \in \ZZ[X]$ se factorise dans $\FF_2$ comme produit de deux facteurs de degré $8$ puisque $2$ est d'ordre $8$ dans $(\ZZ/17\ZZ)^\times$ (on a $2^8 \equiv 1 \pmod{17}$). À savoir : $\Phi_{17}(X) = (X^8+X^5+X^4+X^3+1)\penalty-100 (X^8+X^7+X^6+X^4+X^2+X+1)$. Aucun de ces facteurs, naturellement, n'est primitif (puisque leurs racines sont toutes d'ordre $17$ et non $2^8-1 = 255$). \end{itemize} \end{exemples2} \subsubsection{} Lorsque $n$ n'est plus supposé premier avec $p$ (i.e., avec $q$), les choses sont très différentes, et le polynôme $\Phi_n$ n'est généralement plus séparable sur $\FF_q$ comme on va le voir. Par exemple, il est facile de se convaincre par récurrence sur $k$ que $\Phi_{p^k}(X) = (X-1)^{(p-1)p^{k-1}}$ sur $\FF_p$ (ou sur $\FF_q$, donc). \begin{proposition2}\label{factorisation-phi-n-inseparable} Si $n = p^k m$ où $m$ n'est pas multiple de $p$, alors $\Phi_n(X) = \Phi_m(X)^{(p-1)p^{k-1}}$ dans $\FF_p[X]$ (donc dans $\FF_q[X]$). En particulier, sauf éventuellement dans le cas où $p=2$ et $k=1$, le polynôme $\Phi_n(X)$ n'est ni séparable ni irréductible sur $\FF_q[X]$. \end{proposition2} \begin{proof} On procède par récurrence sur $k$ et, à $k$ fixé, par récurrence sur $m$. On a d'une part $X^{p^k m} - 1 = (X^m-1)^{p^k} = \prod_{d|m}\Phi_d(X)^{p^k}$ et d'autre part $X^{p^k m} - 1 = \prod_{d|p^k m} \Phi_d(X) = \prod_{d|m} (\Phi_d(X)\, \prod_{\ell=1}^k \Phi_{p^\ell d}(X))$. Les hypothèses des récurrences permettent de remplacer chaque $\Phi_{p^\ell d}(X)$ par $\Phi_d(X)^{(p-1)p^{\ell-1}}$ sauf le dernier ($\ell=k$ et $d=m$) : pour montrer qu'on a bien aussi $\Phi_{p^k m}(X) = \Phi_m(X)^{(p-1)p^{k-1}}$, il suffit donc de montrer que $\prod_{d|m}\Phi_d(X)^{p^k} = \prod_{d|m} (\Phi_d(X)\, \prod_{\ell=1}^k \Phi_d(X)^{(p-1)p^{\ell-1}})$. Or cela résulte du fait que $1 + \sum_{\ell=1}^k (p-1)p^{\ell-1} = p^k$. \end{proof} \begin{proposition2}\label{irreductibilite-phi-n-complement} Si $q$ est une puissance d'un nombre premier $p$ et $n$ est un entier naturel, le polynôme cyclotomique $\Phi_n$ est irréductible dans $\FF_q$ si et seulement si : \begin{itemize} \item le nombre $q$ engendre le groupe multiplicatif $(\ZZ/n\ZZ)^\times$ (ce qui sous-entend que $q$ est premier avec $n$), \emph{ou bien} \item on a $n=2m$ avec $m$ impair, et $p=2$, et $q$ engendre le groupe multiplicatif $(\ZZ/m\ZZ)^\times$. \end{itemize} \end{proposition2} \begin{proof} D'après \ref{factorisation-phi-n-inseparable}, on sait que si $n$ est multiple de $p$ avec $p>2$, ou que $n$ est multiple de $4$ lorsque $p=2$, alors $\Phi_n$ n'est pas irréductible modulo $p$ (donc dans $\FF_q$). Lorsque $n$ est premier avec $q$, la proposition \ref{factorisation-phi-n} donne le premier cas. Reste enfin le cas où $n = 2m$ avec $m$ impair et $p=2$ : dans ce cas $\Phi_n(X) = \Phi_m(X)$ modulo $2$, donc la proposition \ref{factorisation-phi-n} donne de nouveau le résultat. \end{proof} \begin{exemples2} \begin{itemize} \item Modulo $2$, les polynômes $\Phi_{2m}(X)$ et $\Phi_m(X)$ (pour $m$ impair) sont toujours égaux. (En fait, dans $\ZZ[X]$, on a $\Phi_{2m}(X) = \Phi_m(-X)$ pour $m$ impair, puisque les racines primitives $2m$-ièmes de l'unité sont les $-\zeta$ avec $\zeta$ racine primitive $m$-ième de l'unité.) Ensuite, toujours modulo $2$ et avec $m$ impair, on a $\Phi_{4m}(X) = \Phi_m(X)^2$. \item Le polynôme $\Phi_8(X) = X^4 + 1$, bien qu'irréductible dans $\ZZ[X]$ ou $\QQ[X]$, n'est irréductible dans \emph{aucun} $\FF_q[X]$ : en effet, en caractéristique $p=2$, on a $\Phi_8 = (X-1)^4$, et en caractéristique $p\neq 2$, on a vu en \ref{factorisation-phi-n} que pour que $\Phi_8$ soit irréductible dans $\FF_q$ il faut (et il suffit) que $q$ engendre $(\ZZ/8\ZZ)^\times$, or ce dernier n'est pas cyclique (il a quatre éléments tous d'ordre divisant $2$) : donc $\Phi_8$ se scinde (en quatre facteurs de degré $1$) pour $q \equiv 1 \pmod{8}$, et se factorise en deux facteurs de degré $2$ pour tout autre $q$ impair. (\XXX Peut-on être un chouïa plus explicite sur la factorisation de $\Phi_8$ modulo $p$ ?) \item Si $n$ est multiple de deux nombres premiers impairs distincts $\ell_1,\ell_2$, alors, de même, $\Phi_n$, bien qu'irréductible dans $\ZZ[X]$ ou $\QQ[X]$, n'est irréductible dans aucun $\FF_q$ : en effet, en caractéristique $\ell_1$ ou $\ell_2$, le polynôme $\Phi_n$ n'est pas irréductible (il est une puissance parfaite) ; et en toute autre caractéristique, on sait que pour que $\Phi_n$ soit irréductible dans $\FF_q$ il faut (et il suffit) que $q$ engendre $(\ZZ/n\ZZ)^\times$, or ce dernier n'est pas cyclique car le théorème chinois assure qu'on peut l'écrire comme produit de deux groupes d'ordres pairs (par exemple $(\ZZ/n\ZZ)^\times \cong (\ZZ/n_1\ZZ)^\times \times (\ZZ/n_2\ZZ)^\times$ où $n_1 = \ell_1^k$ et $n_2$ est premier avec $\ell_1$). \end{itemize} \end{exemples2} \subsubsection{Éléments primitifs modulo $n$} On dit qu'un élément $g \in \ZZ/n\ZZ$ est \emph{primitif} modulo $n$ lorsque $g$ est premier avec $n$ (c'est-à-dire $g \in (\ZZ/n\ZZ)^\times$) et que $g$ engendre le groupe multiplicatif $(\ZZ/n\ZZ)^\times$. (Lorsque $n$ est premier, cette terminologie est cohérente avec celle introduite en \ref{element-primitif-corps-fini}.) Autrement dit, dire qu'il existe des éléments primitifs modulo $n$ signifie que $(\ZZ/n\ZZ)^\times$ est cyclique, et lorsqu'il en existe, il en existe exactement $\varphi(\varphi(n))$. On rappelle ou admet le résultat suivant : \begin{proposition2} \begin{itemize} \item Si $p$ est un nombre premier impair, alors $(\ZZ/p\ZZ)^\times$ est cyclique, i.e., il existe des éléments primitifs modulo $p$. (Il en existe exactement $\varphi(p-1)$.) \item Si $p$ est un nombre premier impair et $k\geq 2$, alors $(\ZZ/p^k\ZZ)^\times$ est cyclique, i.e., il existe des éléments primitifs modulo $p^k$. (Il en existe exactement $\varphi(p^{k-1}(p-1))$.) Plus précisément : $g$ est primitif modulo $p^k$ si et seulement si il l'est modulo $p^2$. \item Si $p=2$ et $1\leq k\leq 2$, alors $(\ZZ/2^k\ZZ)^\times$ est (trivialement) cyclique. \item Si $p=2$ et $k \geq 3$, alors $(\ZZ/2^k\ZZ)^\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^{k-2}$ engendré par $5$ (l'ordre maximal possible d'un élément est $2^{k-2}$). \item Si $n$ n'est pas de la forme $2$, $4$, $p^k$ ou $2 p^k$ avec $p$ premier impair, alors $(\ZZ/n\ZZ)^\times$ \emph{n'est pas} cyclique : il peut s'écrire comme produit de deux groupes d'ordre pair. \end{itemize} \end{proposition2} Par ailleurs, on admet provisoirement le théorème suivant, qui sera démontré en \XXX : \begin{theoreme2}[Dirichlet] Si $b \in (\ZZ/n\ZZ)^\times$, alors il existe un nombre premier $p$ tel que $p \equiv b \pmod{n}$. \end{theoreme2} On peut alors remarquer : \begin{proposition2} Pour tout entier naturel $n$, il existe un nombre premier $p$ (ou, de façon équivalente, une puissance $q$ d'un nombre premier) tel que $\Phi_n$ soit irréductible dans $\FF_p$ (resp., dans $\FF_q$) si, et seulement si, $n$ vaut $2$, $4$, $\ell^k$ ou $2\ell^k$ pour $\ell$ premier impair. \end{proposition2} \begin{proof} Démontrons le « si » : si $n$ est d'une des formes indiquées, alors $(\ZZ/n\ZZ)^\times$ est cyclique, donc il existe un élément $g \in (\ZZ/n\ZZ)^\times$ qui soit primitif, et d'après le théorème de Dirichlet, on peut supposer que $g \equiv p \pmod{n}$ avec $p$ premier, et d'après \ref{factorisation-phi-n} le polynôme $\Phi_n$ est irréductible modulo $p$. Montrons maintenant le « seulement si » : si $\Phi_n$ est irréductible dans $\FF_q$, on sait d'après \ref{irreductibilite-phi-n-complement} que soit $q$ est premier avec $n$ et primitif modulo $n$ soit $n=2m$ avec $m$ impair et $q = 2^r$ est primitif modulo $m$. Dans le premier cas, $n$ vaut $2$, $4$, $\ell^k$ ou $2\ell^k$ avec $\ell$ premier impair, et dans le second, $m$ vaut $\ell^k$ avec $\ell$ premier impair, donc $n=2m$ est bien de la forme $2\ell^k$ avec $\ell$ premier impair. \end{proof} \subsection{Trace et norme} On renvoie à \refext{Alg}{trace-et-norme} pour les généralités sur la trace et la norme dans une algèbre quelconque sur un corps. On se préoccupera ici d'une extension $\FF_{q^r}\bo \FF_q$ de corps finis : la \emph{trace} $\Tr_{\FF{q^r}\bo\FF_q}(x)$, la \emph{norme} $\N_{\FF{q^r}\bo\FF_q}(x)$, et le \emph{polynôme caractéristique} $\chi_{\FF{q^r}\bo\FF_q}(x,X)$ d'un élément $x \in \FF_{q^r}$ sont respectivement la trace, la norme, et le polynôme caractéristique de l'application $\FF_q$-linéaire $z \mapsto xz$ de multiplication par $x$ sur $\FF_{q^r}$, ce dernier étant vu comme un $\FF_q$-espace vectoriel de dimension $r$. \begin{proposition2}\label{trace-et-norme-corps-finis} Soit $x \in \FF_{q^r}$ : alors on a \[\chi_{\FF{q^r}\bo\FF_q}(x,X) = \prod_{i=0}^{r-1} (X-\Frob_q^i(x))\] et en particulier \[\Tr_{\FF{q^r}\bo\FF_q}(x) = \sum_{i=0}^{r-1} \Frob_q^i(x)\] \[\N_{\FF{q^r}\bo\FF_q}(x) = \prod_{i=0}^{r-1} \Frob_q^i(x) = x^{(q^r-1)/(q-1)}\] \end{proposition2} \begin{proof} Considérons d'abord le cas où $x$ engendre $\FF_{q^r}$ sur $\FF_q$, c'est-à-dire que son degré est $r$. Alors on a vu en \ref{elements-conjugues-corps-finis} que les conjugués de $x$ sont justement les $\Frob_q^i(x)$ pour $i\in\{0,\ldots,r-1\}$, le polynôme $\prod_{i=0}^{r-1} (X-\Frob_q^i(x))$ étant alors le polynôme minimal de $x$. Puisqu'il est de degré $r$, c'est aussi son polynôme caractéristique, ce qui montre la première formule dans le cas particulier considéré. Dans le cas où $x$ est de degré $s0$ fixé, la fonction $\Legendre{a}{b}$ est périodique admettant $4b$ pour période, et même $b$ si $b \not\equiv 2 \pmod{4}$. \item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique admettant $4|a|$ pour période si $a \not\equiv -1 \pmod{4}$, et même $|a|$ si $a \equiv 0,1 \pmod{4}$. \end{itemize} \end{remarque2} \section{Hypersurfaces diagonales ; réciprocité quadratique} \subsection{Dualité dans les groupes abéliens finis} \subsubsection{}Soit $G$ un groupe. Un morphisme $χ∈\Hom(G,𝐔)$, où $𝐔=\{z∈𝐂, |z|=1\}≅𝐑/𝐙$, est appelé un \emph{caractère} du groupe $G$ ; on note $\chap{G}$ leur ensemble, qui est naturellement un groupe \emph{abélien} : $(χχ')(g)=χ(g)χ'(g)$. C'est le \emph{dual} de $G$. \subsubsection{}Le lecteur trouvera dans la littérature des variantes : on aurait pu considérer $\Hom(G,𝐂^×)$ (on parle alors parfois de \emph{quasi-caractères} ou caractères généralisés), $\Hom(G,E^×)$ (où $E$ est un corps contenant les racines $\# G$-ème de l'unité, ou bien encore l'ensemble $\Hom(G,𝐐/𝐙)$. Enfin, si $G$ est un groupe topologique localement compact, %donc séparé on pourrait considérer plutôt l'ensemble des caractères \emph{continus}. Muni de la topologie dite \emph{compacte ouverte} c'est à nouveau un groupe topologique localement compact (dualité de Pontryagin). Dans le cas des groupes finis, ces notions sont toutes équivalentes. Par commodité nous préférons voir nos caractères comme à valeurs dans le cercle unité complexe. \subsubsection{}Par composition des fonctions, tout morphisme $H→G$ de groupes induit un morphisme de groupes abéliens $\chap{G}→\chap{H}$. \begin{lemme2}\label{lemme-Q-sur-Z-est-injectif} Soit $K→G$ une \emph{injection} de groupes abéliens finis. Le morphisme dual $\chap{G}→\chap{K}$ est une \emph{surjection}. \end{lemme2} On note $K^{\perp}$ son noyau ; en symboles, $K^{\perp}=\{χ∈\chap{G}, χ(K)=\{1\}\}$. Le morphisme $K^\perp→\chap{G/K}$ est une bijection : tout caractère de $G$ trivial sur $K$ induit un caractère de $G/K$ et réciproquement. \begin{démo}[Démonstration du lemme] Soit $χ:K→\mathbf{U}$ un caractère de $K$ ; il faut montrer qu'il s'étend à $G$, \cad qu'il existe un caractère $χ':G→\mathbf{U}$ dont la restriction à $K$ soit $χ$. Supposons $K≠G$ sans quoi le résultat est trivial et considérons $x∈G-K$. Soient $r$ le plus petit entier non nul tel que $x^r∈K$ et $z$ une racine $r$-ème de $χ(x^r)$ dans $𝐂$. On a donc $χ(x^{rα})=z^{rα}$ pour tout $α∈ℕ$. Il en résulte immédiatement que l'application $χ':⟨K,x⟩→\mathbf{U}$, $kx^i\mapsto χ(k)z^i$ est bien définie ; c'est un caractère du groupe $⟨K,x⟩$. De proche en proche, on peut donc étendre le caractère initial à $G$ tout entier. (De façon précise : procéder par récurrence sur l'indice $(G:K)$.) \end{démo} L'énoncé dual est trivial : si $G→H$ est une \emph{surjection}, le morphisme induit $\chap{H}→\chap{G}$ est une injection. (Cet énoncé, de nature ensembliste, est vrai sans hypothèse sur $G$ ou $H$.) Il en résulte que pour toute suite \emph{exacte} de groupes abéliens finis $1→K→G→H→1$, la suite $1→\chap{H}→\chap{G}→\chap{K}→1$ est également exacte. En effet, $K^\perp:=\mathrm{Ker}(\chap{G}→\chap{K})$ est naturellement en bijection avec $\chap{G/K}$. \begin{lemme2} Soit $G$ un groupe fini abélien. Le morphisme d'évaluation $G→\chap{\chap{G}}$, $g\mapsto \big(\mathrm{\acute{e}v}_g:χ\mapsto χ(g)\big)$ est un isomorphisme. \end{lemme2} \begin{démo} On procède à nouveau par récurrence sur $\# G$, en remarquant que l'énoncé est trivial pour un groupe cyclique (exercice). Dans le cas général, on considère comme précédemment le diagramme de suites exactes : $$ \xymatrix{ 1 \ar[d] \ar[r] & K \ar[d] \ar[r] & G \ar[d] \ar[r] & H \ar[d] \ar[r] & 1 \ar[d] \\ 1 \ar[r] & \chap{\chap{K}} \ar[r] & \chap{\chap{G}} \ar[r] & \chap{\chap{H}} \ar[r] & 1 } $$ Par hypothèse de récurrence, $K→\chap{\chap{K}}$ et $H→\chap{\chap{H}}$ sont des isomorphismes ; il en est donc de même de $G→\chap{\chap{G}}$ (chasse au diagramme). \end{démo} \begin{proposition2} Tout groupe abélien fini est isomorphe à un produit de groupes cycliques. \end{proposition2} \begin{démo} Soit $ω=∏ p_i^{r_i}$ le p.g.c.d des ordres d'éléments de $G$. Pour tout $i$, il existe un élément $g_i$ d'ordre un multiple de $p_i^{r_i}$ ; quitte à l'élever à une puissance convenable, on peut le supposer d'ordre exactement $p_i^{r_i}$. Le produit $g=∏g_i$ est alors d'ordre exactement $ω$. Soient $ζ_ω$ une racine primitive $ω$-ème de l'unité dans $𝐂$ et $χ:⟨g⟩→\mathbf{U}$ le caractère défini par $χ(g)=ζ_ω$. Il s'étend en un caractère $χ'$ de $G$. Son noyau $\Ker(χ')$ est d'indice $ω$ (le cardinal de son image) et $\Ker(χ')⋂⟨g⟩=\{e\}$ de sorte que $G≅⟨g⟩×\Ker(χ')$. On peut donc démontrer la proposition par récurrence sur l'ordre du groupe. \end{démo} \begin{corollaire2} Si $G$ un groupe abélien fini il existe un isomorphisme entre $G$ et $\chap{G}$. \end{corollaire2} \begin{démo} Le résultat étant évident pour un groupe cyclique, il suffit de vérifier que le dual d'un produit $K×K'$ est isomorphe au produit $\chap{K}×\chap{K'}$ des duaux. C'est immédiat. (Pour les groupes abéliens, le produit cartésien est la somme directe (comme $𝐙$-module).) \end{démo} \begin{lemme2} \label{lemme-orthogonalite-caracteres} Soient $G$ un groupe abélien fini et $g∈G$. Alors, $∑_{χ∈\chap{G}} χ(g)$ est égal à $0$ si $g≠e$ et $|G|$ sinon. \end{lemme2} \begin{démo} Le résultat est trivial si $g=e$. Supposons $g≠e$. Puisque le morphisme $G→\chap{\chap{G}}$ est un isomorphisme, il est donc injectif : $\mathrm{\acute{e}v}_g≠e$. En d'autres termes, il existe un caractère $χ'∈\chap{G}$ tel que $χ'(g)≠1$. Soit $S=∑_χ χ(g)$. On a $χ'(g)S=∑_χ (χ'χ)(g)=S$. Puisque $χ'(g)≠1$, on a bien $S=0$. \end{démo} \begin{corollaire2} \label{variante-orthogonalite-caracteres} Soit $G$ un groupe abélien fini et $χ∈\chap{G}$. Alors, $∑_{g∈G} χ(g)$ est égal à $0$ si $χ ≠ 1$ et $|G|$ sinon. \end{corollaire2} \begin{démo} Cela résulte de l'égalité $∑_g χ(g)=∑_g \mathrm{\acute{e}v}_g(χ)$, du lemme précédent, et du fait que tout caractère de $\chap{G}$ est de la forme $\mathrm{\acute{e}v}_g$ pour un unique $g∈G$. \end{démo} \subsection{Équation $X^n=g$ dans un groupe abélien fini ; application} Pour tout groupe abélien $G$ (en notation multiplicative) et tout entier $n$, notons $G[n]:=\{g∈G, g^n=1\}$ et $nG=\{g^n, g∈G\}$. La surjection $G→G/nG$ induit une \emph{injection} $\chap{G/nG}↪\chap{G}[n]$ : un caractère composé $G→G/nG→\mathbf{U}$ est tué par $n$. Le premier groupe a pour cardinal $(G:nG)$ ; celui de droite $(\chap{G}:n\chap{G})$. D'après la proposition ci-dessus, $G≅\chap{G}$, de sorte que $(\chap{G}:n\chap{G})=(G:nG)$ et, finalement, $$ \chap{G/nG} ⥲ \chap{G}[n]. $$ Soit $g∈G$ et notons $\sur{g}$ son image dans $G/nG$. Cette image est nulle \ssi pour tout $\sur{χ}∈\chap{G/nG}$, $\sur{χ}(\sur{g})=1$. Soit $χ$ l'image de $\sur{χ}$ par l'isomorphisme précédent ; on a par définition $χ(g)=\sur{χ}(\sur{g})$. \begin{corollaire2} Soient $G$ un groupe abélien fini, $g∈G$ et $n$ un entier. Les conditions suivantes sont équivalentes. \begin{enumerate} \item $g∈nG$ ; \item $\chap{G}[n](g)=\{1\}$. \end{enumerate} \end{corollaire2} \begin{corollaire2} Soient $G$ un groupe abélien fini, $g∈G$ et $n$ un entier. Alors, $$ N(X^n=g)=∑_{χ∈\chap{G}[n]} χ(g), $$ où $N(X^n=g)$ désigne le nombre de solution de l'équation $X^n=g$ dans $G$. \end{corollaire2} \begin{démo} Le terme de gauche est égal à $0$ si $g∉nG$ ; il est égal à $\#G[n]$ dans le cas contraire car deux solutions diffèrent d'un élément de $G[n]$. Notons $\sur{g}$ l'image de $g$ dans $G/nG$. Le terme de droite se réécrit $$ ∑_{\sur{χ}∈\chap{G/nG}} \sur{χ}(\sur{g}). $$ D'après \ref{lemme-orthogonalite-caracteres}, cette somme vaut $0$ si $\sur{g}≠e$ (\cad $g∉nG$) et $\#\chap{G/nG}$ sinon. Puisque $\chap{G/nG}≅\chap{G}[n]≅G[n]$, l'égalité avec le terme de gauche en résulte. \end{démo} \subsubsection{} Soit $F$ un corps \emph{fini}. Rappelons que le groupe multiplicatif $F^×$ est \emph{cyclique} (\ref{cyclicite-groupe-multiplicatif-corps}). %Si $n$ est un entier, la condition $n|d$ %du paragraphe précédent est équivalente à l'égalité $\#μ_n(F)=n$ ou encore à l'inclusion %$μ_n(\sur{F})⊂F$. Fixons un entier $d≥0$, des coefficients $c₀,\dots,c_d,b∈F^×$ et des exposants $n=(n₀,\dots,n_d)$ tous non nuls. On s'intéresse dorénavant au nombre $N=N(c₀X₀^{n₀}+\cdots+c_d X_d^{n_d}=b)$ de solution de cette équation dans $F$ et ses sur-corps. On note $A$ la $F$-algèbre $F^{d+1}$. Soit $L$ la forme linéaire sur $A$ définie par $L(a)=∑_i c_i a_i$, où $a=(a₀,\dots,a_d)∈F^{d+1}$. \subsubsection{}L'égalité suivante est tautologique : $$N=∑_{a∈A\atop L(a)=b} N(X₀^{n₀}=a₀)\cdots N(X_d^{n_d}=a_d).$$ D'après les résultats des paragraphes précédents, chaque entier $N(X_i^{n_i}=a_i)$ est égal à la somme $∑_{χ∈\chap{F^×}[n_i]} χ(a_i)$. \begin{quote} \emph{A priori}, cette formule n'a de sens que pour $a_i≠0$, elle reste pourtant vraie si l'on décrète que $χ(0)$ est nul si $χ≠1$ et égal à un sinon. \end{quote} Ainsi, en développant l'expression $\big(∑_{χ₀^{n₀}=1} χ(a₀)\big)\cdots \big(∑_{χ_d^{n_d}=1} χ(a_d)\big)$ et en sommant sur les $a∈A$ tels que $L(a)=b$, on trouve : $$ (\star)\ N=(\# F)^d+∑_{χ=(χ₀,\dots,χ_d)≠1} \big(∑_{a∈A\atop L(a)=b} χ₀(a₀)\cdots χ_d(a_d)\big), $$ où la première somme porte sur les caractères comme ci-dessus, supposés non tous triviaux. En effet, la contribution de $χ₀=\cdots=χ_d=1$ est égale au cardinal de l'hyperplan affine $L^{-1}(b)$. Par commodité, on notera par la suite $χ₀(a₀)\cdots χ_d(a_d)=:χ(a)$. \begin{lemme2} Si certains des $χ_i$ sont triviaux, mais pas tous, la somme $$∑_{a∈A\atop L(a)=b} χ₀(a₀)\cdots χ_d(a_d)$$ est \emph{nulle}. \end{lemme2} \begin{démo} Soit $χ=(χ₀,\dots,χ_d)$ comme dans l'énoncé et considérons l'algèbre quotient $A↠A'$ de $A$ correspondant aux facteurs non triviaux. Tautologiquement, $χ(a)=χ'(a')$ où $a'$ est l'image de $a$ dans $A'$ et $χ'$ est la famille de caractères (tous) non triviaux correspondante. La somme à évaluer est donc égale à $∑_{a∈A\atop L(a)=b} χ'(a')$. Elle est égale à $∑_{a'∈A'} \big(χ'(a')\cdot \#\{a∈A,a\mapsto a', L(a)=b\}\big)$. Puisque pour tout $a'$, $\{a∈A,a\mapsto a', L(a)=b\}$ est un espace affine non vide (car $A'≠A$) de dimension donc de cardinal indépendants de $a'$, il suffit de montrer que $∑_{a'∈A'} χ'(a')=0$. Puisque les constituants de $χ'$ sont tous non triviaux, elle est égale à $∑_{a'∈{A'}^×} χ'(a')$. D'après \ref{variante-orthogonalite-caracteres}, cette somme est nulle. \end{démo} \subsubsection{Nouveaux caractères}Soit $A↠A'$ comme dans la démonstration. En passant aux unités, on obtient un morphisme induit $A^×↠{A'}^×$ d'où une injection $\chap{{A'}^×}↪\chap{A^×}$. La proposition précédente affirme que la contribution d'un caractère de l'image est nulle. En d'autres termes, seuls contribuent les caractères qui ne sont pas induits par une sous-algèbre quotient \emph{stricte}. (On a vu en \ref{algebre-diagonalisable} que tous ces quotients sont du type envisagé dans la démonstration.) On note $\chap{A^×}^{\mathrm{nouv}}$ l'\emph{ensemble} de ces caractères (par oppositions aux \emph{anciens}, provenant d'une plus petite algèbre). Généralisant quelque peu la notation habituelle, on pose $\chap{A^×}[n]:=\{χ=(χ₀,\dots,χ_d)∈\chap{A^×}, χ_i^{n_i}=1\}$. (Si $n₀=\dots=n_d$, on retombe sur la définition précédente.) Enfin, si $E⊂\chap{A^×}$, on note $E[n]$ (resp. $E^{\mathrm{nouv}}$ resp. $E^{\mathrm{nouv}}[n]$) son intersection avec le sous-ensemble correspondant de $\chap{A^×}$. Remarquons que si $d+1=\dim_F(A)>1$, tout nouveau caractère de $A^×$ est non trivial. \subsubsection{Réécriture de l'égalité ($\star$)} Si l'on pose $a'=ca$ (\cad $a'_i=c_i a_i$ pour $0≤i≤d$), on a bien sûr $χ(a)=χ(c)^{-1}χ(a')$, ce qui complique un peu les choses, mais la condition $L(a)=b$ s'écrit $∑_i a'_i=b$, \cad $\Tr_{A/F}(a')=b$. Utilisant cette remarque et le lemme précédent, on peut donc écrire : $$ N=(\# F)^d+∑_{χ∈\chap{A^×}^{\mathrm{nouv}}[n]\atop χ≠1} χ^{-1}(c)\big( ∑_{a∈A^×\atop \Tr(a)=b} χ(a)\big). $$ Rappelons que le terme $(\# F)^d$ correspond au caractère $χ=1$. Notons $χ_{|F^×}$ la restriction d'un caractère $χ$ de $A^×$ au sous-groupe $F^×$ plongé diagonalement, de sorte que $χ_{|F^×}(x)=∏_i χ_i(x)$. En écrivant $a_i=a₀a'_i$ ($0