Introduction à la théorie des corps finis Brique cqfd

Hugues Randriam

10 décembre 2004

1 Prérequis et rappels sur les structures fondamentales de l’algèbre

On rappelle brièvement les définitions des structures de base de l’algèbre qu’on utilisera continuellement.

Un groupe est un ensemble muni d’une loi de composition interne associative qui admet un élément neutre et pour laquelle tout élément est inversible. Le groupe est dit commutatif (ou abélien) si sa loi l’est.

Un anneau est un ensemble muni de deux lois de composition interne, appelées addition et multiplication, qui vérifient les propriétés suivantes :

– l’addition définit sur l’anneau une structure de groupe abélien, dont l’élément neutre est appelé l’élément nul (ou zéro, noté 0) de l’anneau

– la multiplication est associative, admet un élément neutre (appelé élément unité de l’anneau, noté 1) et est distributive par rapport à l’addition.

L’anneau est dit commutatif si sa multiplication l’est.

Dans ce cours on n’étudiera que des anneaux commutatifs. L’algèbre noncommutative est très riche et intéressante, mais on aura déjà suffisamment à faire avec la théorie commutative. Ainsi, dans la suite du texte, et sauf mention du contraire, tous les anneaux considérés seront commutatifs.

Dans un anneau A, les éléments inversibles forment un groupe pour la multiplication, noté A^{×}.

Un corps est un anneau dans lequel un élément est inversible si et seulement s’il est non nul (remarquons que cette définition implique 0 ≠ 1).

Un anneau A est dit intègre si 0 ≠ 1 et si le produit de deux éléments non nuls est non nul. Cela équivaut à demander qu’il existe un corps admettant A comme sous-anneau. Un corps minimal pour l’inclusion parmi ceux qui possèdent cette propriété est appelé corps de fractions de A.

Soit A un anneau. On appellera A-module la donnée d’un groupe abélien V et d’une application

\begin{matrix}A × V & ⟶ & V \\ (a, v) & ↦ & av \end{matrix}

appelée multiplication scalaire, telle que, notant 0_{A} l’élément nul de A, 1_{A} son élément unité, et 0_{V} l’élément neutre de V, pour tous a, b ∈ A et v, w ∈ V on ait 0_{A}v = 0_{V}, a0_{V} = 0_{V}, 1_{A}v = v, (ab)v = a(bv), (a + b)v = av + bv, et a(v + w) = av + aw.

Dans le cas particulier où l’anneau A est un corps K, on parlera indifféremment de K-module ou de K-espace vectoriel.

Un morphisme (ou homomorphisme) entre deux groupes, deux anneaux, deux corps, ou deux K-espaces vectoriels, est une application entre ces deux ensembles qui respecte leurs structures (envoie élément neutre sur élément neutre, respecte addition, multiplication,...).

Exemple 1.1. — Les nombres réels forment un groupe (abélien) pour l’addition, (ℝ, +, 0). Les nombres réels non nuls forment un groupe (abélien) pour la multiplication, (ℝ^{×}, ×, 1). L’exponentielle (peu importe la base) de ℝ dans ℝ^{×} est un morphisme de groupes, car on a bien exp(0) = 1 et exp(x + y) = exp(x) exp(y) pour tous x et y dans ℝ.

Un morphisme entre deux K-espaces vectoriels est aussi appelé une application K-linéaire.

Une famille d’éléments d’un K-espace vectoriel V est dite génératrice si tout élément de V peut s’écrire comme combinaison linéaire (finie, à coefficients dans K) d’entre eux. Une famille d’éléments de V est dite libre si toute combinaison linéaire non triviale de ces éléments est non nulle. Une telle famille est appelée base de V si elle est à la fois libre et génératrice ; cela revient à demander que tout élément de V puisse s’écrire d’une unique façon comme combinaison linéaire de ces éléments. De toute famille génératrice d’un espace vectoriel on peut extraire une base, et toute famille libre peut se compléter en une base.

Toutes les bases de V ont même cardinal (éventuellement infini), appelé dimension de V (sur K). Dans ce cours on considérera principalement des espaces de dimension finie.

Exemple 1.2. — Les applications K-linéaires d’un K-espace vectoriel de dimension m dans un K-espace vectoriel de dimension n forment un K-espace vectoriel de dimension mn.

Un morphisme d’un objet dans lui-même est appelé endomorphisme. Un morphisme bijectif (et dont l’inverse est alors aussi un morphisme) est appelé isomorphisme. Un morphisme qui est à la fois un endomorphisme et un isomorphisme est appelé automorphisme.

Exemple 1.3. — La conjugaison complexe de ℂ dans lui-même est un automorphisme de corps. En effet, elle est son propre inverse, et on a bien \overline{0} = 0, \overline{1} = 1, \overline{x + y} = \overline{x} + \overline{y}, et \overline{xy} = \overline{x}.\overline{y} pour tous x et y dans ℂ.

2 Généralités sur les extensions de corps

Définition 2.1. — Soit L un corps. Un sous-corps de L est une partie de L qui contient 0 et 1, est stable par addition et multiplication, et telle que ces opérations la munissent d’une structure de corps.

On dira de façon équivalente que K est un sous-corps de L ou que L est une extension de K.

Un morphisme entre deux extensions L_{1} et L_{2} d’un même corps K est un morphisme de corps de L_{1} dans L_{2} dont la restriction à K est l’identité.

Proposition 2.2. — Soit f : K ⟶ L un morphisme de corps. Alors f est injectif.

Démonstration. Il suffit de montrer que si x n’est pas nul, f(x) non plus. Or tout x non nul admet un inverse x^{−1}, et on a

f(x)f(x^{−1}) = f(xx^{−1}) = f(1_{K}) = 1_{L} ≠ 0_{L}

donc f(x) ≠ 0_{L}.

Interprétation de la proposition : f injectif permet d’identifier K à son image f(K) qui est un sous-corps de L; ainsi tout morphisme de corps permet de considérer le corps d’arrivée comme une extension du corps de départ.

Si K ⊂ L est une extension de corps, on peut considérer L comme un Kespace vectoriel : la structure de groupe abélien de ce K-espace vectoriel est définie par l’addition usuelle de L, et la multiplication scalaire K × L ⟶ L est définie par la restriction de la multiplication usuelle de L.

Définition 2.3. — Le degré de l’extension K ⊂ L, noté [K : L], est la dimension de L considéré comme K-espace vectoriel :

[L : K] = dim_{K} L.

Une extension de degré fini sera aussi parfois appelée une extension finie.

Proposition 2.4 (multiplicativité du degré). — Soient K ⊂ L ⊂ M trois corps extensions l’un de l’autre. Alors

[M : K] = [M : L][L : K].

Démonstration. Considérons des éléments e_{i} ∈ M qui forment une base de M sur L et, de même, des f_{j} ∈ L formant une base de L sur K. Alors tout élément m ∈ M s’écrit de façon unique comme combinaison linéaire (finie) m = ∑_{i} l_{i}e_{i} pour des l_{i} dans L, et de même chaque l_{i} s’écrit de façon unique l_{i} = ∑_{j} k_{i,j}f_{j} pour des k_{i,j} dans K. Ainsi m s’écrit de façon unique m = ∑_{i,j} k_{i,j}e_{i}f_{j} de sorte que les e_{i}f_{j} forment une base de M sur K.

Soient K ⊂ L une extension de corps de degré fini n, et e_{1}, …, e_{n} ∈ L une base de L sur K. Deux éléments x et y de L s’écrivent de façon unique x = ∑_{i=1}^{n} λ_{i}e_{i} et y = ∑_{i=1}^{n} μ_{i}e_{i} avec les λ_{i} et μ_{i} dans K. Il est encore facile d’exprimer la somme de x et y dans la base : on a x + y = ∑_{i=1}^{n}(λ_{i} + μ_{i})e_{i}.

Pour le produit, on a xy = ∑_{i,j=1}^{n} λ_{i}μ_{j}e_{i}e_{j}, et on voit qu’il peut être utile de savoir exprimer chaque produit e_{i}e_{j} dans la base.

Définition 2.5. — Les constantes de structure de la base (e_{1}, …, e_{n}) de L sur K sont les α_{i,j,k} ∈ K, pour i, j, k ∈ {1, …, n}, définis par

e_{i}e_{j} = ∑_{k=1}^{n} α_{i,j,k}e_{k}.

Avec les notations qui précèdent, on a donc

xy = ∑_{k=1}^{n} ν_{k}e_{k}

avec

ν_{k} = ∑_{i,j=1}^{n} α_{i,j,k}λ_{i}μ_{j}.

On vérifie que la commutativité de la multiplication implique

α_{i,j,k} = α_{j,i,k}

et l’associativité

∑_{p=1}^{n} α_{i,j,p}α_{p,k,l} = ∑_{q=1}^{n} α_{i,q,l}α_{j,k,q}

pour tous i, j, k, l. L’existence d’un élément unité et de l’inverse peuvent s’exprimer dans les mêmes termes.

Exemple 2.6. — Prenant K = ℝ et L = ℂ on a n = [ℂ : ℝ] = 2, et choisissant la base formée de e_{1} = 1 et e_{2} = i = \sqrt{−1} on trouve α_{1,1,1} = α_{1,2,2} = α_{2,1,2} = 1, α_{1,1,2} = α_{1,2,1} = α_{2,1,1} = α_{2,2,2} = 0, et α_{2,2,1} = −1.

La multiplication de L pouvant se lire sur les constantes de structure, il importe de trouver une base pour laquelle celles-ci sont particulièrement simples.

Définition 2.7. — Soit L une extension finie de K, de degré n. On dit que L est une extension élémentaire, ou simple (ou encore parfois primitive), de K s’il existe x ∈ L tel que (1, x, x^{2}, …, x^{n−1}) soit une base de L sur K.

On dit alors que x est un générateur de L sur K.

Quelques remarques :

– La définition équivaut à demander qu’il existe un élément x ∈ L tel que les éléments de L soient exactement les valeurs en x des polynômes à coefficients dans K de degré inférieur ou égal à n − 1.

– En particulier l’élément x^{n} de L doit être égal à la valeur en x d’un polynôme à coefficients dans K de degré inférieur ou égal à n − 1 : il existe a_{0}, a_{1}, …, a_{n−1} ∈ K tels que x^{n} = a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0}. Notant alors P (X) = X^{n} − a_{n−1}X^{n−1} − ⋯ − a_{1}X − a_{0}, on a P (x) = 0.

– Si y = F (x) ∈ L et z = G(x) ∈ L, alors y+z = (F +G)(x) et yz = H(x) où H est le reste de la division euclidienne de F G par P. En effet, si F G = P Q + H, on a yz = F (x)G(x) = P (x)Q(x) + H(x) = H(x) puisque H(x) = 0.

Définition 2.8. — Soient K un corps et P ∈ K[X] un polynôme de degré n. L’anneau quotient K[X]/P est construit comme suit :

– en tant que groupe abélien, c’est l’ensemble des polynômes à coefficients dans K de degré inférieur ou égal à n − 1, muni de l’addition usuelle ;

– si F et G sont deux éléments de K[X]/P, leur produit dans K[X]/P est le reste de la division euclidienne par P du produit usuel F G.

Des remarques qui précèdent il découle immédiatement le résultat suivant :

Lemme 2.9. — Soient K ⊂ L une extension élémentaire de degré n et x un générateur de L sur K. Il existe alors un polynôme P ∈ K[X] de degré n annulant x, et l’application de K[X]/P dans L qui envoie F sur F (x) est un isomorphisme d’anneaux.

On peut encore préciser le lemme comme suit.

Théorème 2.10. — Soit K un corps.

1. Soit P ∈ K[X] un polynôme de degré n. Les assertions suivantes sont équivalentes :

– l’anneau quotient K[X]/P est intègre

– le polynôme P est irréductible

– l’anneau quotient K[X]/P est un corps.

Si l’une de ces conditions équivalentes est vérifiée, K[X]/P est alors une extension élémentaire de K, de degré n.

2. Inversement, si L est une extension finie de K, alors L est élémentaire si et seulement s’il existe un polynôme irréductible P ∈ K[X] tel que L soit isomorphe à K[X]/P en tant qu’extension de K (on peut choisir par exemple le polynôme P et l’isomorphisme donnés dans le lemme).

Démonstration. Supposons K[X]/P intègre et P non irréductible, de sorte que P = F G avec deg F ≤ n − 1 et deg G ≤ n − 1. Le produit de F et G dans K[X]/P est le reste de la division euclidienne par P du produit usuel F G, c’est-à-dire 0. Puisque K[X]/P est supposé intègre, on doit donc avoir F = 0 ou G = 0, ce qui est absurde. Si maintenant P est irréductible et si A est un polynôme non nul de degré inférieur ou égal à n − 1, alors le théorème de Bézout fournit B et Q de degrés inférieurs ou égaux à n − 1 et tels que AB + P Q = 1, de sorte que B est un inverse de A dans K[X]/P. Ainsi K[X]/P est un corps. Tout corps étant intègre, on a démontré l’équivalence des trois assertions. Ceci étant fait, K[X]/P est une extension élémentaire de K puisqu’elle admet X comme générateur.

Si maintenant L est une extension élémentaire de K, x un générateur, et P un polynôme de degré n qui annule x, l’application donnée dans le lemme étant un isomorphisme d’anneaux, et L étant un corps, K[X]/P est aussi un corps, de sorte que l’irréductibilité de P résulte de la première partie du théorème. L’isomorphisme entre K[X]/P et L est alors un isomorphisme de corps, et puisqu’il laisse les éléments de K inchangés, c’est même un isomorphisme d’extensions de K.

Pour l’étude de la structure de K[X]/P pour un polynôme P quelconque, on consultera l’exercice 7.1.

Proposition 2.11. — Soient K ⊂ L une extension finie de corps et x un élément de L. Alors il existe un unique polynôme irréductible P à coefficients dans K et de coefficient dominant 1 qui annule x.

Si l’on note K[x] le plus petit sous-anneau de L qui contient K et x, alors K[x] est un corps, et plus précisément c’est une extension élémentaire de K isomorphe à K[X]/P.

Démonstration. Notons n le plus petit entier naturel tel que (1, x, …, x^{n−1}) soit une famille libre dans le K-espace vectoriel L (on a donc n ≤ [L : K]). Alors x^{n} est combinaison linéaire à coefficients dans K de ces éléments : x^{n} = a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0}. Alors on a P (x) = 0 où P (X) = X^{n} − a_{n−1}X^{n−1} − ⋯ − a_{1}X − a_{0}, et K[x] s’identifie à K[X]/P. Cet anneau étant intègre (puisque sous-anneau d’un corps), l’irréductibilité de P et le reste de la proposition découlent du théorème précédent.

Définition 2.12. — Le polynôme irréductible P ainsi défini dans la proposition est appelé le polynôme minimal de x sur K.

Un polynôme à coefficients dans K annule x si et seulement s’il est multiple de P.

Proposition 2.13. — Toute extension finie de corps s’obtient par composition d’extensions élémentaires.

Démonstration. On procède par récurrence. Soit K ⊂ L une extension finie de corps. Si L = K, l’assertion à prouver est triviale. Sinon, soit x ∈ L, x ∉ K. Alors on a K ⊂ K[x] ⊂ L où K[x] est une extension élémentaire de K, et où L est une extension de K[x] de degré strictement inférieur à [L : K]. On peut donc conclure en appliquant l’hypothèse de récurrence à l’extension K[x] ⊂ L.

Si L est une extension finie de K et si x_{1}, …, x_{r} ∈ L, on note K[x_{1}, …, x_{r}] le plus petit sous-anneau de L qui contient K et x_{1}, …, x_{r}. Les faits qui précèdent et une récurrence immédiate montrent que K[x_{1}, …, x_{r}] est un corps. On dit que c’est le sous-corps de L engendré par x_{1}, …, x_{r} sur K.

Proposition 2.14. — Soient K un corps et P ∈ K[X] un polynôme non constant. Alors il existe une extension finie L de K dans laquelle P admet une racine.

Démonstration. Sans perte de généralité on peut supposer P irréductible. Alors l’extension élémentaire L = K[X]/P de K convient, puisque l’élément X de L est bien racine de P.

Proposition 2.15. — Soient K un corps et P ∈ K[X] un polynôme de degré r ≥ 1. Alors il existe une extension finie L de K dans laquelle P se décompose en produit de facteurs linéaires : il existe c ∈ K et α_{1}, …, α_{r} ∈ L tels que

P (X) = c(X − α_{1}) … (X − α_{r}).

Démonstration. On procède par récurrence sur r. Par la proposition précédente il existe une extension finie K_{1} de K telle que P admette une racine α_{1} dans K_{1}. Notant alors P (X) = (X − α_{1})P_{1}(X) avec P_{1} ∈ K_{1}[X], on conclut en appliquant l’hypothèse de récurrence avec K_{1} et P_{1} à la place de K et P.

Définition 2.16. — On appelle corps de décomposition de P sur K une extension L de K de degré minimal dans laquelle P se décompose en produit de facteurs linéaires.

Avec les notations de la proposition, la minimalité du degré signifie que le corps de décomposition L est engendré par les racines de P : on a L = K[α_{1}, …, α_{r}].

Proposition 2.17. — Soit σ : K_{1} ⟶^{∼} K_{2} un isomorphisme de corps, P_{1} un polynôme non constant à coefficients dans K_{1}, P_{2} = σ(P_{1}), L_{1} un corps de décomposition de P_{1} sur K_{1} et L_{2} un corps de décomposition de P_{2} sur K_{2}. Alors L_{1} et L_{2} sont isomorphes, et plus précisément, il existe un isomorphisme de L_{1} sur L_{2} qui étend σ.

En particulier, prenant K_{1} = K_{2} = K et σ l’identité, on voit que le corps de décomposition d’un polynôme est unique (à isomorphisme près).

Démonstration. On procède par récurrence sur le degré de P_{1}. Soit Q_{1} un facteur irréductible de P_{1}. Par définition d’un corps de décomposition, Q_{1} admet une racine x_{1} dans L_{1}, et Q_{2} = σ(P_{2}) une racine x_{2} dans L_{2}. Par la proposition 2.11, K′_{1} = K_{1}[x_{1}] est naturellement isomorphe à K_{1}[X]/P_{1}, et K′_{2} = K_{2}[x_{2}] à K_{2}[X]/P_{2}, les isomorphismes envoyant x_{1} et x_{2} sur X. L’isomorphisme σ de K_{1} sur K_{2} s’étend naturellement en un isomorphisme de K_{1}[X]/P_{1} sur K_{2}[X]/P_{2}, et donc de K′_{1} sur K′_{2}, noté σ′, qui vérifie σ′(x_{1}) = x_{2}. Ecrivant P_{1}(X) = (X − x_{1})R_{1}(X) avec R_{1} ∈ K′_{1}[X], P_{2}(X) = (X − x_{2})R_{2}(X) avec R_{2} = σ′(R_{1}) ∈ K′_{2}[X], et remarquant que L_{1} est un corps de décomposition de R_{1} sur K′_{1}, et L_{2} de R_{2} sur K′_{2}, on peut conclure en appliquant l’hypothèse de récurrence.

3 Construction des corps finis et étude de leurs propriétés élémentaires

On supposera connue la théorie des anneaux quotient ℤ/nℤ, en particulier le fait que ℤ/nℤ est intègre (et même, est un corps) si et seulement si n est un nombre premier.

Proposition 3.1. — Soit K un corps. Alors ou bien K est une extension du corps ℚ des nombres rationnels, ou bien K est une extension de ℤ/pℤ pour un nombre premier p uniquement déterminé.

Définition 3.2. — Dans le premier cas de la proposition on dit que K est de caractéristique 0, et dans le second que K est de caractéristique p.

Démonstration. On dispose naturellement d’un homomorphisme d’anneaux f de ℤ dans K qui envoie 1 ∈ ℤ sur l’élément unité de K. Si f est injectif, alors K contient son image f(ℤ) qui est isomorphe à ℤ, et son corps de fractions qui est isomorphe à ℚ. Sinon il existe un plus petit entier non nul p tel que f(p) = 0. Alors l’image f(ℤ) est isomorphe à ℤ/pℤ, et est intègre (puisque sous-anneau d’un corps), de sorte que p est premier.

Proposition 3.3. — Soit K un corps fini. Alors le cardinal de K est une puissance d’un nombre premier. Plus précisément, il existe p premier tel que K soit une extension de ℤ/pℤ, et le cardinal de K vaut p^{r} où r = [K : ℤ/pℤ] est le degré de cette extension.

Démonstration. Le corps K étant fini, il ne peut contenir ℚ, donc est nécessairement extension d’un ℤ/pℤ. Notant r = [K : ℤ/pℤ], K est alors un ℤ/pℤ-espace vectoriel de dimension r, donc de cardinal p^{r}.

Lemme 3.4. — Soit K un corps de caractéristique p. Alors pour tous a, b ∈ K on a (a + b)^{p} = a^{p} + b^{p}, et plus généralement, pour tout entier r ≥ 1,

(a + b)^{p^{r}} = a^{p^{r}} + b^{p^{r}}.

Démonstration. La formule du binôme donne

(a + b)^{p} = a^{p} + b^{p} + ∑_{i=1}^{p−1} \binom{p}{i}a^{i}b^{p−i}.

Or, pour 1 ≤ i ≤ p − 1, l’entier \binom{p}{i} = \frac{p!}{i!(p−i)!} est divisible par p donc nul dans ℤ/pℤ. Ceci prouve le cas r = 1 du lemme, et le cas général en découle par une récurrence évidente.

Théorème 3.5. — Soient p un nombre premier et r ≥ 1 un entier.

1. Le corps de décomposition du polynôme X^{p^{r}} − X sur ℤ/pℤ est de cardinal p^{r}.

2. Inversement, si K est un corps fini de cardinal p^{r}, alors K est corps de décomposition de X^{p^{r}} − X sur ℤ/pℤ. Plus précisément, les racines de X^{p^{r}} − X sont exactement les éléments de K avec multiplicité 1.

Démonstration. Notons K le corps de décomposition de X^{p^{r}} − X sur ℤ/pℤ, de sorte qu’on ait

X^{p^{r}} − X = ∏_{i=1}^{p^{r}}(X − α_{i})

pour des α_{i} ∈ K qui engendrent K sur ℤ/pℤ.

Montrons d’abord que les α_{i} sont tous distincts (i.e. que X^{p^{r}} − X est à racines simples). Dans le cas contraire, si α_{i} = α_{j} = α, alors on peut écrire

X^{p^{r}} − X = (X − α)^{2}Q(X)

d’où en dérivant et en utilisant le fait que p est nul dans ℤ/pℤ,

−1 = p^{r}X^{p^{r}−1} − 1 = 2(X − α)Q(X) + (X − α)^{2}Q′(X),

de sorte que (X − α) divise 1, ce qui est absurde.

Les α_{i} forment donc p^{r} éléments deux à deux distincts de K. Montrons maintenant que l’ensemble E des α_{i} est un sous-corps de K (d’où l’on déduira, par minimalité du corps de décomposition, que ce sous-corps est K tout entier). On a clairement 0^{p^{r}} = 0 et 1^{p^{r}} = 1, donc 0 et 1 font bien partie de E. Par le lemme, si α et β sont dans E, alors

(α + β)^{p^{r}} = α^{p^{r}} + β^{p^{r}} = α + β,

donc α + β ∈ E. De la même façon, (αβ)^{p^{r}} = α^{p^{r}}β^{p^{r}} = αβ donc αβ ∈ E. Ainsi E est stable par addition et multiplication. Si α ∈ E est non nul, alors (α^{−1})^{p^{r}} = (α^{p^{r}})^{−1} = α^{−1}, donc E ∖ {0} est stable par inverse. Enfin, reste à voir que si α est dans E, alors −α aussi. Si p = 2 c’est évident, puisqu’alors −α = α, et sinon p est impair, de sorte que (−α)^{p^{r}} = −α^{p^{r}} = −α, ce qu’il fallait démontrer. Ceci termine la preuve de la première assertion du théorème.

Soit maintenant K un corps de cardinal p^{r}. Alors K^{×} est un groupe abélien de cardinal p^{r} − 1, donc par le théorème de Lagrange tout élément x de K^{×} vérifie x^{p^{r}−1} = 1. Ainsi tout élément non nul de K est racine de X^{p^{r}−1} − 1, donc de X^{p^{r}} − X. Par ailleurs 0 est aussi clairement racine de X^{p^{r}} − X. Les p^{r} éléments distincts de K sont donc tous racines de X^{p^{r}} − X, qui est de degré p^{r}, de sorte qu’on peut écrire

X^{p^{r}} − X = ∏_{x∈K}(X − x),

et K est bien corps de décomposition de X^{p^{r}} − X.

Corollaire 3.6. — Tout corps fini est de cardinal une puissance d’un nombre premier. Inversement, si q = p^{r} est une puissance d’un nombre premier, il existe un corps fini de cardinal q, et celui-ci est unique à isomorphisme près.

Démonstration. C’est une conséquence immédiate du théorème, l’unicité résultant de l’unicité du corps de décomposition.

On notera 𝔽_{q}, ou parfois aussi GF (q), l’unique corps à q éléments. Si q = p est un nombre premier, on a donc 𝔽_{p} = ℤ/pℤ. On prendra garde à l’inverse que si q = p^{r} avec r ≥ 2, alors 𝔽_{q} n’est pas isomorphe à ℤ/qℤ, ce dernier anneau n’étant même pas intègre.

Décrivons explicitement 𝔽_{q} pour les petites valeurs de q :

– 𝔽_{2} = ℤ/2ℤ = \{0, 1\}  \begin{matrix}+ & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}  \begin{matrix}× & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}

– 𝔽_{3} = ℤ/3ℤ = \{0, 1, 2\} = \{0, 1, −1\}  \begin{matrix}+ & 0 & 1 & 2 \\ 0 & 0 & 1 & 2 \\ 1 & 1 & 2 & 0 \\ 2 & 2 & 0 & 1 \end{matrix}  \begin{matrix}× & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 \\ 2 & 0 & 2 & 1 \end{matrix}

– 𝔽_{4} n’est pas égal à ℤ/4ℤ! En tant que corps de caractéristique 2, il contient 𝔽_{2} = {0, 1}, et deux autres éléments, qu’on notera α et β. On vérifie que les seules tables d’addition et de multiplication possibles sont les suivantes :

\begin{matrix}+ & 0 & 1 & α & β \\ 0 & 0 & 1 & α & β \\ 1 & 1 & 0 & β & α \\ α & α & β & 0 & 1 \\ β & β & α & 1 & 0 \end{matrix}  \begin{matrix}× & 0 & 1 & α & β \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & α & β \\ α & 0 & α & β & 1 \\ β & 0 & β & 1 & α \end{matrix}

On vérifie que ces opérations sont associatives et commutatives et que la multiplication est distributive par rapport à l’addition. Le corps 𝔽_{4} est bien corps de décomposition de X^{4} − X sur 𝔽_{2} puisqu’on a 0^{4} = 0, 1^{4} = 1, α^{4} = α et β^{4} = β, de sorte que

X^{4} − X = X(X − 1)(X − α)(X − β).

On vérifie enfin qu’on a α^{2} = α + 1, de sorte que α est racine de X^{2} + X + 1 (l’autre racine est β), d’où l’on tire une représentation

𝔽_{4} ≃ 𝔽_{2}[X]/X^{2} + X + 1.

– 𝔽_{5} = ℤ/5ℤ

– Il n’y a pas de corps de cardinal 6.

– 𝔽_{7} = ℤ/7ℤ

– 𝔽_{8} est une extension de degré 3 de 𝔽_{2}, qu’on va décrire plus précisément.

Considérons un élément x ∈ 𝔽_{8} ∖ 𝔽_{2}, et notons K = 𝔽_{2}[x]. On a alors [K : 𝔽_{2}] > 1 et [𝔽_{8} : K][K : 𝔽_{2}] = [𝔽_{8} : 𝔽_{2}] = 3, donc nécessairement [K : 𝔽_{2}] = 3, et K = 𝔽_{8}. Ainsi 𝔽_{8} est une extension élémentaire de 𝔽_{2}, et tout élément de 𝔽_{8} ∖ 𝔽_{2} en est un générateur ; le polynôme minimal P d’un tel élément est irréductible de degré 3 sur 𝔽_{2}, et on a alors 𝔽_{8} ≃ 𝔽_{2}[X]/P.

Quels sont les polynômes irréductibles de degré 3 sur 𝔽_{2} ? Il y a 8 polynômes de degré 3 sur 𝔽_{2}, parmi lesquels 6 sont multiples de X ou de X + 1. Éliminant ceux-ci, il reste X^{3} + X + 1 et X^{3} + X^{2} + 1, qui sont irréductibles. On dispose donc de deux isomorphismes,

𝔽_{8} ≃ 𝔽_{2}[X]/X^{3} + X + 1 et 𝔽_{8} ≃ 𝔽_{2}[X]/X^{3} + X^{2} + 1,

qui vont donner deux descriptions différentes du même corps 𝔽_{8}.

Notons α une racine de X^{3} + X + 1 dans 𝔽_{8}. Les éléments de 𝔽_{8} sont les polynômes en α de degré au plus 2 :

𝔽_{8} = {0, 1, α, α + 1, α^{2}, α^{2} + 1, α^{2} + α, α^{2} + α + 1}.

Utilisant la relation α^{3} = α + 1 on peut décomposer successivement les puissances de α dans la base (1, α, α^{2}) de 𝔽_{8} sur 𝔽_{2}. On peut aussi faire la même chose en partant d’une racine β de X^{3} + X^{2} + 1, qui vérifie donc β^{3} = β^{2} + 1.

On trouve :

\begin{aligned}& α^{2} & α & 1 \\ 1 & 0 & 0 & 1 \\ α & 0 & 1 & 0 \\ α^{2} & 1 & 0 & 0 \\ α^{3} & 0 & 1 & 1 \\ α^{4} & 1 & 1 & 0 \\ α^{5} & 1 & 1 & 1 \\ α^{6} & 1 & 0 & 1 \end{aligned}  \begin{aligned}& β^{2} & β & 1 \\ 1 & 0 & 0 & 1 \\ β & 0 & 1 & 0 \\ β^{2} & 1 & 0 & 0 \\ β^{3} & 1 & 0 & 1 \\ β^{4} & 1 & 1 & 1 \\ β^{5} & 0 & 1 & 1 \\ β^{6} & 1 & 1 & 0 \end{aligned}

et α^{7} = β^{7} = 1.

Le corps 𝔽_{8} étant unique à isomorphisme près, ces deux descriptions doivent être équivalentes. On vérifie que les racines de X^{3} + X + 1 sont {α, α^{2}, α^{4}}, et celles de X^{3} +X^{2} +1, {α^{3}, α^{5}, α^{6}}. On peut donc prendre pour β n’importe lequel de ces trois derniers éléments. Choisissant par exemple le premier, on voit que la correspondance β ↦ α^{3}, β^{2} ↦ α^{6}, β^{3} ↦ α^{2}, β^{4} ↦ α^{5}, β^{5} ↦ α, β^{6} ↦ α^{4} respecte l’addition et la multiplication, de sorte que les écritures en termes de α et en termes de β sont bien deux représentations équivalentes de la même structure de corps.

4 Polynômes primitifs et structure multiplicative des corps finis

Un phénomène agréable dans l’exemple étudié précédemment est que tous les éléments de 𝔽_{8}^{∗} sont des puissances de α. L’exponention i ↦ α^{i} définit un morphisme surjectif de groupes de ℤ sur 𝔽_{7}^{∗} qui, puisque α est d’ordre 7, définit par passage au quotient un isomorphisme

\begin{matrix}ℤ/7ℤ & ⟶ & 𝔽_{8}^{∗} \\ i mod 7 & ↦ & α^{i}. \end{matrix}

Plus généralement :

Définition 4.1. — Soient q une puissance d’un nombre premier et 𝔽_{q} le corps fini à q éléments. On dira qu’un élément γ ∈ 𝔽_{q} est (multiplicativement) primitif s’il est d’ordre q − 1 dans 𝔽_{q}^{∗}.

Puisque 𝔽_{q}^{∗} est d’ordre q−1, cela revient à demander que tout élément non nul de 𝔽_{q} soit une puissance de γ, ou encore que l’application d’exponentiation

\begin{matrix}ℤ/(q − 1)ℤ & ⟶ & 𝔽_{q}^{∗} \\ i mod q − 1 & ↦ & γ^{i} \end{matrix}

soit un isomorphisme de groupes. L’isomorphisme inverse est appelé logarithme en base γ :

log_{γ} : 𝔽_{q−1}^{∗} ⟶^{∼} ℤ/(q − 1)ℤ.

Proposition 4.2. — Soient p un nombre premier et n ≥ 1 un entier. On suppose que 𝔽_{p^{n}} admet un élément primitif γ. Alors 𝔽_{p^{n}} est une extension élémentaire de 𝔽_{p} et γ en est un générateur. En particulier, le polynôme minimal de γ est de degré n.

Définition 4.3. — Un polynôme de degré n à coefficients dans 𝔽_{p} est dit primitif s’il est polynôme minimal d’un élément primitif de 𝔽_{p^{n}}.

Remarquons qu’un polynôme primitif est donc par définition irréductible.

Lemme 4.4. — Soient G un groupe abélien et m_{1}, …, m_{n} des entiers deux à deux premiers entre eux. Si, pour tout i, G contient un élément d’ordre m_{i}, alors G contient un élément d’ordre m_{1} … m_{n}.

Définition 4.5. — Soit G un groupe abélien fini. On appelle exposant de G, noté ω(G), le plus petit commun multiple des ordres des éléments de G :

ω(G) = ppcm_{g∈G} ω(g).

Lemme 4.6. — Soit G un groupe abélien fini. Alors G admet un élément d’ordre ω(G).

On rappelle qu’un groupe abélien fini G est dit cyclique s’il est isomorphe au groupe ℤ/#Gℤ. Cela revient à demander que G possède un élément d’ordre #G.

Théorème 4.7. — Soit G un groupe abélien fini tel que pour tout n divisant #G, il y ait dans G au plus n éléments d’ordre divisant n. Alors G est cyclique.

Corollaire 4.8. — Soit K un corps. Alors tout sous-groupe fini de K^{∗} est cyclique.

Corollaire 4.9. — Tout corps fini admet un élément primitif. Pour tout nombre premier p et pour tout entier n ≥ 1, il existe un polynôme primitif (donc, a fortiori, irréductible) de degré n à coefficients dans 𝔽_{p}.

Blah table de Zech.

Blah sous-groupes de puissances.

5 Extensions de corps finis : propriétés relatives, Frobenius, racines conjuguées, norme et trace

On a vu que tout corps fini contenait un sous-corps premier 𝔽_{p} = ℤ/pℤ. On se propose maintenant d’étudier les extensions 𝔽_{q} ⊂ 𝔽_{q′} de corps finis en général.

Lemme 5.1. — Soient m et n deux entiers naturels, m supposé non nul, et r le reste de la division euclidienne de n par m. Alors dans ℤ[X] on a

X^{n} − 1 ≡ X^{r} − 1 mod X^{m} − 1.

Démonstration. Écrivons n = dm + r. Alors

(X^{n} − 1) − (X^{r} − 1) = X^{n} − X^{r}
= X^{r}(X^{dm} − 1)

= X^{r}(X^{m} − 1)(X^{(d−1)m} + X^{(d−2)m} + ⋯ + X^{m} + 1)

est bien divisible par X^{m} − 1.

Lemme 5.2. — Soient m, n et p trois entiers naturels, m et p non nuls. Alors X^{p^{m}} − X divise X^{p^{n}} − X si et seulement si m divise n.

Démonstration. Simplifiant par X, la première condition équivaut à demander que X^{p^{m}−1} − 1 divise X^{p^{n}−1} − 1, ce qui par le lemme précédent èquivaut à ce que p^{m} − 1 divise p^{n} − 1. Appliquant à nouveau ce lemme, en évaluant en p les polynômes considérés, on trouve

p^{n} − 1 ≡ p^{r} − 1 mod p^{m} − 1,

de sorte que p^{m} − 1 divise p^{n} − 1 si et seulement si m divise n.

Théorème 5.3. — Soient p un nombre premier, n un entier non nul, q′ = p^{n}, et q un entier naturel. Alors 𝔽_{q′} admet un sous-corps de cardinal q si et seulement si q = p^{m} avec m divisant n (i.e. si et seulement si q′ est une puissance de q), et un tel sous-corps est alors unique : ses éléments sont les racines de X^{q} − X.

Corollaire 5.4. — Soient q une puissance d’un nombre premier et d ≥ 1 un entier naturel. Alors 𝔽_{q} admet une extension élémentaire de degré d (isomorphe à 𝔽_{q^{d}}). Autrement dit, 𝔽_{q}[X] admet des polynômes irréductibles en tout degré.

Démonstration. En effet, q^{d} est encore une puissance de nombre premier, et par le théorème, 𝔽_{q} est un sous-corps de 𝔽_{q^{d}}. Ceci étant, n’importe quel élément primitif de 𝔽_{q^{d}}^{∗} engendre alors 𝔽_{q^{d}} comme extension de 𝔽_{q}.

Exemple 5.5. — Les corps 𝔽_{4} et 𝔽_{8} sont des extensions de 𝔽_{2}, mais il n’existe pas d’inclusion de 𝔽_{4} dans 𝔽_{8}. Le plus petit corps fini contenant simultanément 𝔽_{4} et 𝔽_{8} est 𝔽_{64}.

Soient q une puissance d’un nombre premier et d ≥ 1 un entier naturel. Considérons l’application

\begin{aligned}φ : & 𝔽_{q^{d}} & ⟶ & 𝔽_{q^{d}} \\ & x & ↦ & x^{q}. \end{aligned}

On a alors φ(0) = 0, φ(1) = 1 et, pour tous x, y ∈ 𝔽_{q^{d}}, φ(x + y) = x + y et φ(xy) = φ(x)φ(y) (l’avant-dernière égalité résultant du lemme 3.4). Ainsi φ est un endomorphisme du corps 𝔽_{q^{d}}. Ceci implique que φ est injectif (proposition 2.2), donc bijectif puisque 𝔽_{q^{d}} est fini. En fait pour tout x ∈ 𝔽_{q^{d}} on a φ^{d}(x) = x^{q^{d}} = x, de sorte que φ^{d} est l’identité de 𝔽_{q^{d}}, et l’on voit que l’inverse de φ est φ^{d−1}. Remarquons par ailleurs que 𝔽_{q^{d}} contient 𝔽_{q} comme sous-corps, et qu’un élément x de 𝔽_{q^{d}} appartient à 𝔽_{q} si et seulement s’il vérifie x^{q} = x, autrement dit, si et seulement s’il est laissé invariant par φ. Les éléments de 𝔽_{q} étant invariants sous φ, on conclut que φ est un automorphisme de 𝔽_{q^{d}} vu comme extension de 𝔽_{q}.

Définition 5.6. — L’application ainsi définie, notée φ_{𝔽_{q^{d}}/𝔽_{q}} ou Frob_{𝔽_{q^{d}}/𝔽_{q}}, est appelée automorphisme de Frobenius de 𝔽_{q^{d}} sur 𝔽_{q}.

Proposition 5.7. — Les corps intermédiaires entre 𝔽_{q} et 𝔽_{q^{d}} sont les 𝔽_{q^{k}} pour k divisant d. Pour un tel k on a

φ_{𝔽_{q^{d}}/𝔽_{q^{k}}} = (φ_{𝔽_{q^{d}}/𝔽_{q}})^{k}

et un élément x de 𝔽_{q^{d}} appartient à 𝔽_{q^{k}} si et seulement s’il est invariant sous φ_{𝔽_{q^{d}}/𝔽_{q^{k}}}, autrement dit, s’il vérifie x^{q^{k}} = x.

Démonstration. C’est une conséquence directe du théorème 5.3 et de la définition du Frobenius.

Lemme 5.8. — Soit φ un automorphisme d’une extension L d’un corps K. Alors pour tous P ∈ K[X] et x ∈ L on a

φ(P (x)) = P (φ(x)).

Démonstration. Notons P (X) = ∑_{i} a_{i}X^{i}, avec a_{i} ∈ K, de sorte que φ(a_{i}) = a_{i}. Alors

φ(P (x)) = φ(∑_{i} a_{i}x^{i})

= ∑_{i} φ(a_{i})φ(x)^{i}

= ∑_{i} a_{i}φ(x)^{i}

= P (φ(x)),

ce qu’il fallait démontrer.

Théorème 5.9. — Soient q une puissance d’un nombre premier et d ≥ 1 un entier.

1. Si x est un élément de 𝔽_{q^{d}}, le plus petit entier non nul k tel que x^{q^{k}} = x est un diviseur de d. Le polynôme

P (X) = (X − x)(X − x^{q})(X − x^{q^{2}}) … (X − x^{q^{k−1}}),

à coefficients dans 𝔽_{q^{d}}, est en fait à coefficients dans 𝔽_{q}, et est irréductible sur 𝔽_{q}; c’est donc le polynôme minimal de x sur 𝔽_{q}.

2. Inversement, soient P ∈ 𝔽_{q}[X] un polynôme irréductible, et k son degré. Alors P admet une racine x dans 𝔽_{q^{d}} si et seulement si k divise d, et alors P y admet toutes ses racines, qui sont x, x^{q}, ..., x^{q^{k−1}}.

Démonstration. Les entiers j tels que x^{q^{j}} = x forment un sous-groupe additif de ℤ. Ce sous-groupe contenant d, son générateur positif k est un diviseur de d. Puisque x^{q^{k}} = x, le Frobenius φ_{𝔽_{q^{d}}/𝔽_{q}} induit une permutation de {x, x^{q}, …, x^{q^{k−1}}}, donc laisse P inchangé. Les éléments de 𝔽_{q^{d}} invariants sous le Frobenius étant précisément ceux qui appartiennent au sous-corps 𝔽_{q}, on voit que P est bien à coefficients dans 𝔽_{q}. Supposons maintenant P = QR avec Q et R unitaires à coefficients dans 𝔽_{q}. Puisque x est racine de P, on peut supposer par exemple x racine de Q. Alors, par le lemme (appliqué avec pour φ le Frobenius), x^{q}, x^{q^{2}}, ..., x^{q^{k−1}} sont aussi racines de Q, et la minimalité de k implique que les k racines ainsi obtenues sont toutes distinctes. On a donc Q = P, ce qui prouve l’irréductibilité. Plaçons-nous maintenant sous les hypothèses de la seconde assertion. On peut sans perte de généralité supposer P unitaire. Si P admet une racine x dans 𝔽_{q^{d}}, alors P est le polynôme minimal de x sur 𝔽_{q}, et on conclut à l’aide du point précédent. Inversement, si P est de degré k divisant d, considérons une extension 𝔽_{q^{λd}} de 𝔽_{q^{d}} dans laquelle P admette une racine x. Alors 𝔽_{q}[x] ≃ 𝔽_{q}[X]/P est un sous-corps de cardinal q^{k} de 𝔽_{q^{λd}} et donc, par le résultat d’unicité dans le théorème 5.3, coïncide avec l’unique sous-corps de cardinal q^{k} de 𝔽_{q^{d}}. Ainsi on a x ∈ 𝔽_{q^{d}}, et on conclut comme précédemment.

Corollaire 5.10. — Les groupe des automorphismes de 𝔽_{q^{d}} au-dessus de 𝔽_{q} est cyclique de cardinal d, engendré par le Frobenius.

Démonstration. On rappelle que 𝔽_{q^{d}} est une extension élémentaire de 𝔽_{q}. Soient x un générateur de cette extension et φ un automorphisme de 𝔽_{q^{d}} au-dessus de 𝔽_{q}. Tout élément de 𝔽_{q^{d}} peut s’écrire sous la forme Q(x) où Q est un polynôme à coefficients dans 𝔽_{q}, et alors, par le lemme, l’image de cet élément par φ est Q(φ(x)). Ainsi φ est déterminé par sa valeur en x. Mais par ailleurs, toujours par le lemme, φ doit permuter les racines du polynôme minimal de x, qui sont précisément les images de x sous les puissances du Frobenius. Ainsi φ est bien une puissance du Frobenius.

Définition 5.11. — Soit K ⊂ L une extension finie de corps. On dit que deux éléments de L sont conjugués sur K s’ils ont même polynôme minimal sur K.

Corollaire 5.12. — Deux éléments x et y de 𝔽_{q^{d}} sont conjugués sur 𝔽_{q} si et seulement s’il existe j tel que y = x^{q^{j}}.

Soit K ⊂ L une extension finie de corps. Si x est un élément de L, la multiplication par x est un endomorphisme K-linéaire du K-espace vectoriel L.

Définition 5.13. — Avec ces notations, on définit la trace de x, notée Tr_{L/K}(x), et la norme de x, notée N_{L/K}(x), comme la trace et le déterminant de cette application linéaire.

Remarque 5.14. — Après choix d’une base de L sur K, la construction qui précède permet de voir les éléments de L comme des matrices carrées de taille n = [L : K] à coefficients dans K, l’addition et la multiplication de L correspondant à l’addition et à la multiplication usuelle des matrices, et les éléments de K ⊂ L s’identifiant aux matrices diagonales.

Exemple 5.15. — ℝ ⊂ ℂ Proposition 5.16. — Soit K ⊂ L une extension de corps. Alors la trace est une application K-linéaire de L dans K, et la norme induit un homomorphisme de groupes de L^{∗} dans K^{∗}. Plus précisément, pour λ ∈ K et x, y ∈ L, on a :

– Tr(x + y) = Tr(x) + Tr(y)

– Tr(λx) = λ Tr(x)

– Tr(1) = [L : K]

– N(xy) = N(x)N(y)

– N(λ) = λ^{[L:K]}.

Lemme 5.17. — F ⊂ K ⊂ L x ∈ K Tr_{L/F} (x) = [L : K] Tr_{K/F} (x) N_{L/F} (x) = N_{K/F} (x)^{[L:K]}

Théorème 5.18. — Trace somme puissances Frobenius, norme produit...

Corollaire 5.19. — F ⊂ K ⊂ L corps finis Tr_{L/F} = Tr_{K/F} ∘ Tr_{L/K} N_{L/F} = N_{K/F} ∘ N_{L/K}

Définition 5.20. — caractère

Lemme 5.21 (d’indépendance des caractères). —

Proposition 5.22. — corps finis, norme et trace surjectives

6 Algorithme de factorisation de Berlekamp

Blah.

7 Exercices

Exercice 7.1 a) Soient K un corps, F et G deux polynômes à coefficients dans K premiers entre eux, et P = F G. Considérons l’application

f : K[X]/P ⟶  K[X]/F × K[X]/G
H mod P ↦ (H mod F, H mod G).

i. Montrer que f est un homomorphisme d’anneaux et de K-espaces

vectoriels. ii. Quel est le noyau de f ? Quelles sont les dimensions sur K des espaces

de départ et d’arrivée ? En déduire que f est bijectif. iii. Trouver des éléments de K[X]/P dont l’image par f est (1, 0) ou

(0, 1) (on pourra utiliser une relation de Bézout entre F et G). Expliciter l’isomorphisme inverse de f.

b) Soit P ∈ K[X] se décomposant en produit P = P_{1}^{e_{1}} … P_{r}^{e_{r}}, les P_{i} étant irréductibles et deux à deux distincts, et les e_{i} non nuls. i. Montrer qu’on a un isomorphisme d’anneaux et de K-espaces vecto-

riels

K[X]/P ≃ K[X]/P_{1}^{e_{1}} × ⋯ × K[X]/P_{r}^{e_{r}}

qui envoie X sur (X, …, X). Expliciter l’isomorphisme inverse. ii. On rappelle qu’un élément a d’un anneau est dit idempotent s’il

vérifie a^{2} = a, ce qui équivaut à demander que la multiplication par a soit un projecteur. Montrer que le nombre d’idempotents de K[X]/P est égal à 2^{r} (on pourra commencer par montrer que dans un anneau de la forme K[X]/Q^{e} avec Q irréductible et e ≥ 1, les seuls idempotents sont 0 et 1).

iii. On rappelle qu’un élément a d’un anneau est dit nilpotent si une certaine puissance de a est nulle. Un anneau est dit réduit s’il n’admet pas d’élément nilpotent non nul. Montrer que K[X]/P est réduit si et seulement s’il est isomorphe à un produit de corps, ou encore si et seulement si P est sans facteurs multiples dans K[X].

Exercice 7.2 a) Donner la liste des polynômes irréductibles de degré 1, 2,

3 et 4 sur 𝔽_{2}.

b) Soit γ un élément de 𝔽_{16} racine du polynôme X^{4} +X +1. Écrire les puissances de γ comme des polynômes en γ de degré au plus 3 à coefficients dans 𝔽_{2}. En déduire que X^{4} + X + 1 est primitif sur 𝔽_{2}.

c) Quels sont les sous-groupes du groupe multiplicatif 𝔽_{16}^{∗}?

d) Quels sont les sous-corps de 𝔽_{16} ?

e) Parmi les polynômes obtenus à la question a), quels sont ceux qui admettent des racines dans 𝔽_{16} ? Pour chacun, dire quelles sont ces racines.

f) Quels sont les polynômes primitifs de degré 4 sur 𝔽_{2} ?

g) Quel est le degré minimal possible d’un polynôme non nul à coefficients dans 𝔽_{2} qui s’annule en γ^{5}, γ^{6} et γ^{7} ?

Exercice 7.3 a) Combien y a-t-il de polynômes irréductibles de degré 3 sur 𝔽_{3} ? Parmi ceux-ci, combien sont-ils primitifs, et combien ne le sont-ils pas ? b) Même question pour les polynômes de degré 5 sur 𝔽_{2}.

c) Même question pour les polynômes de degré 6 sur 𝔽_{2}.

d) Même question pour les polynômes de degré 12 sur 𝔽_{2}.

Soit d un entier. On rappelle qu’un élément x d’un corps K est dit être une racine primitice d-ième de l’unité si on a x^{d} = 1 mais x^{c} ≠ 1 pour tout diviseur strict c de d.

On définit le d-ième polynôme cyclotomique Φ_{d}, à coefficients dans ℤ, par la formule

Φ_{d}(X) = \frac{X^{d} − 1}{ppcm(X^{c} − 1)_{c|d,c≠d}} .

On note φ la fonction indicatrice d’Euler.

Exercice 7.4 a) Montrer que Φ_{d} est de degré φ(d).

b) Soit K un corps. Montrer qu’un élément x de K est une racine primitive d-ième de l’unité si et seulement si Φ_{d}(x) = 0.

Exercice 7.5 Soient q ≥ 2 une puissance d’un nombre premier et n ≥ 1 un entier.

a) Notons S l’ensemble des polynômes irréductibles sur 𝔽_{q} de degré divisant

n. Montrer :

∏_{P ∈S} P (X) = X^{q^{n}} − X.

b) Notons T l’ensemble des polynômes primitifs de degré n sur 𝔽_{q}. Montrer :

∏_{P ∈T} P (X) = Φ_{q^{n}−1}(X).

Exercice 7.6 Soient q ≥ 2 une puissance d’un nombre premier et d un entier premier à q. Quels sont les entiers k tels que 𝔽_{q^{k}} contienne une racine primitive d-ième de l’unité ?

Exercice 7.7 Soient q ≥ 2 une puissance d’un nombre premier et P un polynôme à coefficients dans 𝔽_{q}. a) Soit d un diviseur de q − 1. Notons U l’ensemble des racines non nulles

de P dans 𝔽_{q} qui sont des puissances d-ièmes. Montrer :

pgcd(P (X), X^{\frac{q−1}{d}} − 1) = ∏_{α∈U}(X − α).

b) Soit n ≥ 1 un entier. Notons V l’ensemble des racines de P dans 𝔽_{q^{n}}.

Montrer que le polynôme

∏_{α∈V}(X − α)

sur 𝔽_{q^{n}} est en fait à coefficients dans 𝔽_{q}. Donner une formule permettant de calculer facilement ce polynôme.

Exercice 7.8 Soient q ≥ 2 une puissance d’un nombre premier et n un entier. Soit x un élément primitif de 𝔽_{q^{n}}. Montrer que la norme N_{𝔽_{q^{n}}/𝔽_{q}}(x) de x est un élément primitif de 𝔽_{q}.

Exercice 7.9 Factoriser le polynôme

X^{11} + X^{10} + X^{9} + X^{8} + X^{7} + X^{5} + X^{3} + X + 1

sur 𝔽_{2}.