123 Corps finis. Applications.

Corps finis. Applications.

algebra

Soient $p$ un nombre premier, $n$ un nombre entier, et $q = p^{n}$ .

Construction

Caractéristique, sous-corps premier

Définition 1. Soit $A$ un anneau. L’application $f_{A} : Z n \to \mapsto A n fois 1 + \dots + 1$ On note $car (A)$ l’unique $n \in N$ tel que $Ker (f_{A}) = n Z$ : c’est la caractéristique de $A$ .

Exemple 2. La caractéristique de l’anneau $Z / n Z$ est $n$ .

Proposition 3.

Soit $A$ un anneau intègre. Alors, $car (A) = 0 ou p$ avec $p$ premier.
Soit $A$ un anneau fini. Alors, $car (A) \neq = 0$ et $car (A) ∣ ∣ A ∣$ .
Un anneau et un quelconque de ses sous-anneaux ont la même caractéristique.

Remarque 4.

Le Point 1 est en particulier vrai pour un corps.
Si $car (A) = 0$ , $A$ est infini.

Définition 5. Soit $K$ un corps.

$K$ est dit premier s’il n’a pas d’autre sous-corps que lui-même.
Le sous-corps premier de $K$ est le sous-corps de $K$ engendré par $1$ (ie. l’intersection de tous les sous-corps de $K$ ) : c’est un corps premier.

Remarque 6. Un corps et l’un de ses sous-corps ont le même sous-corps premier.

Proposition 7. Soient $K$ un corps et $P$ son corps premier. Alors, si $car (K) = 0$ , $P ≅ Q$ .

Construction de $F_{p}$

p. 3

Proposition 8. Les conditions suivantes sont équivalentes :

$n$ est un nombre premier.
$Z / n Z$ est un anneau intègre.
$Z / n Z$ est un corps.

Notation 9. On note $F_{p} = Z / p Z$ .

p. 81

Proposition 10. Soit $K$ un corps fini.

$car (K)$ est un nombre premier $p$ .
Le sous-corps premier de $K$ est isomorphe à $F_{p}$ .
$∣ K ∣ = p^{m}$ pour $m \geq 2$ .

Exemple 11.

Il n’existe pas de corps fini à $6$ éléments.
$F_{p} (X)$ , est un corps infini de caractéristique $p$ .

p. 8

Proposition 12. Tout corps fini à $p$ éléments est isomorphe à $F_{p}$ .

Construction de $F_{q}$

p. 85

Proposition 13. Soit $K$ un corps de caractéristique $p$ . L’application $Frob : K x \to \mapsto K x^{p}$ est un morphisme de corps.

Si $K$ est fini, c’est un automorphisme.
Si $K = F_{p}$ , c’est l’identité.

Corollaire 14. Dans un corps fini de caractéristique $p$ , chaque élément admet exactement une racine $p$ -ième.

Application 15 (Petit théorème de Fermat). $\forall x \in Z, x^{p} \equiv x mod p$

Théorème 16.

Il existe un corps $K$ à $q$ éléments : c’est le corps de décomposition de $X^{q} - X$ sur $F_{p}$ .
$K$ est unique à isomorphisme près : on le note $F_{q}$ .

Corollaire 17. Le produit des éléments de $F_{q}^{*}$ vaut $- 1$ .

Application 18 (Théorème de Wilson). Soit $n \geq 2$ un entier. Alors, $n est premier ⟺ (n - 1)! + 1 \equiv 0 mod n$

Propriétés

Commutativité

p. 67

Définition 19. L’ensemble des générateurs de $μ_{n}$ , noté $μ_{n}^{*}$ , est formé des racines primitives $n$ -ièmes de l’unité.

Proposition 20.

$μ_{n}^{*} = {e^{\frac{2 ikπ}{n}} ∣ k \in [[0, n - 1]], pgcd (k, m) = 1}$ .
$∣ μ_{n}^{*} ∣ = φ (n)$ , où $φ$ désigne l’indicatrice d’Euler.

Définition 21. On appelle $n$ -ième polynôme cyclotomique le polynôme $Φ_{n} = ξ \in μ_{n}^{*} \prod (X - ξ)$

Théorème 22.

$X^{n} - 1 = \prod_{d ∣ n} Φ_{d}$ .
$Φ_{n} \in Z [X]$ .
$Φ_{n}$ est irréductible sur $Q$ .

theoreme-de-wedderburn

[GOU21]
p. 100

Théorème 23 (Wedderburn). Tout corps fini est commutatif.

Sous-corps

[ULM18]
p. 122

Théorème 24. Tout sous-corps de $F_{q}$ est de cardinal $p^{d}$ avec $d ∣ n$ . Réciproquement, pour tout $d ∣ n$ , $F_{q}$ admet un unique sous-corps de cardinal $p^{d}$ .

Exemple 25. Les sous-corps de $F_{2^{12}}$ sont $F_{2^{6}}$ , $F_{2^{4}}$ , $F_{2^{3}}$ , $F_{2^{2}}$ et $F_{2}$ .

Corollaire 26. Le polynôme $X^{q} - X \in F_{p} [X]$ est produit de tous les polynômes irréductibles unitaires de $F_{p} [X]$ dont le degré divise $n$ .

Corollaire 27. Il existe des polynômes irréductibles de tout degré dans $F_{q} [X]$ .

Corollaire 28. Un corps de rupture d’un polynôme irréductible de $F_{q} [X]$ sur $F_{q}$ est aussi un corps de décomposition pour ce polynôme sur $F_{q}$ .

Groupe multiplicatif

[GOZ]
p. 83

Théorème 29. Tout sous-groupe fini du groupe multiplicatif d’un corps commutatif est cyclique.

Corollaire 30. Le groupe multiplicatif d’un corps fini est cyclique.

Corollaire 31. $F_{q}^{*} ≅ Z / (q - 1) Z$

Groupe des automorphismes

Théorème 32. Le groupe des automorphismes de $F_{q}$ est cyclique, engendré par $Frob$ , et d’ordre $n$ .

Proposition 33. Pour chaque application $f : F_{q} \to F_{q}$ , il existe un unique polynôme $P \in F_{q} [X]$ de degré inférieur ou égal à $q - 1$ tel que $P = u \in F_{q} \sum f (u) (1 - (X - u)^{q - 1})$

Proposition 34. Les sous-groupes additifs de $F_{q}$ sous les sous- $F_{q}$ -espaces vectoriels. Ils sont au nombre de $s = 0 \sum n \frac{( p ^{n} - 1 ) ( p ^{n - 1} - 1 ) \dots ( p ^{n - s + 1} - 1 )}{( p ^{s} - 1 ) ( p ^{s - 1} - 1 ) \dots ( p - 1 )}$

Carrés

p. 93

Proposition 35. On note $F_{q}^{2} = {x^{2} ∣ x \in F_{q}}$ et $F_{q}^{* 2} = F_{q}^{2} \cap F_{q}^{*}$ . Alors $F_{q}^{* 2}$ est un sous-groupe de $F_{q}^{*}$ .

Proposition 36.

Si $p = 2$ , $F_{q}^{2} = F_{q}$ , donc $F_{q}^{* 2} = F_{q}^{*}$ .
Si $p > 2$ , alors :
- $F_{q}^{* 2}$ est le noyau de l’endomorphisme de $F_{q}^{*}$ défini par $x \mapsto x^{\frac{q - 1}{2}}$ .
- $F_{q}^{* 2}$ est un sous-groupe d’indice $2$ de $F_{q}^{*}$ .
- $∣ F_{q}^{* 2} ∣ = \frac{q - 1}{2}$ et $∣ F_{q}^{2} ∣ = \frac{q + 1}{2}$ .
- $(- 1) \in F_{q}^{* 2} ⟺ q \equiv 1 mod 4$ .

p. 155

On suppose, pour la suite de cette sous-section, $p > 2$ .

Définition 37. On définit le symbole de Legendre $(\frac{x}{p})$ pour $x \in F_{p}^{*}$ par : $(\frac{x}{p}) = \pm 1 avec (\frac{x}{p}) = 1 ⟺ x \in F_{p}^{* 2}$

Proposition 38. $x \mapsto (\frac{x}{p})$ est un morphisme de groupes non constant et, $\forall x \in F_{p}^{* 2}, (\frac{x}{p}) = x^{\frac{p - 1}{2}}$

Théorème 39 (Loi de réciprocité quadratique). Soit $q \neq = p$ un premier impair. Alors, $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{( p - 1 ) ( q - 1 )}{4}}$

Remarque 40. Cela signifie qu’il est équivalent d’avoir $p$ résidu quadratique modulo $q$ ou $q$ résidu quadratique modulo $p$ , sauf si $p \equiv q \equiv 3 mod 4$ auquel cas ces propositions s’excluent mutuellement.

Proposition 41. $(\frac{2}{p}) = (- 1)^{\frac{( p - 1 ) ^{2}}{8}}$

Exemple 42. $(\frac{17}{41}) = (- 1)^{8 \times 20} (\frac{41}{27}) = (\frac{7}{17}) = (- 1)^{3 \times 8} (\frac{17}{7}) = (\frac{3}{7}) = (- 1)^{3} (\frac{7}{3}) = - (\frac{1}{3}) = - 1$

Applications

Irréductibilité de polynômes

p. 57

Théorème 43. Soit $P \in K [X]$ un polynôme irréductible sur un corps $K$ .

Il existe un corps de rupture de $P$ .
Si $L = K [α]$ et $L^{'} = K [β]$ sont deux corps de rupture de $P$ , alors il existe un unique $K$ -isomorphisme $φ : L \to L^{'}$ tel que $φ (α) = β$ .
$K [X] / (P)$ est un corps de rupture de $P$ .

p. 10

Lemme 44 (Gauss).

Le produit de deux polynômes primitifs est primitif (ie. dont le PGCD des coefficients est égal à $1$ ).
$\forall P, Q \in Z [X] ∖ {0}$ , $γ (PQ) = γ (P) γ (Q)$ (où $γ (P)$ est le contenu du polynôme $P$ ).

Théorème 45 (Critère d’Eisenstein). Soit $P = \sum_{i = 0}^{n} a_{i} X^{i} \in Z [X]$ de degré $n \geq 1$ . On suppose qu’il existe $p$ premier tel que :

$p ∣ a_{i}$ , $\forall i \in [[0, n - 1]]$ .
$p ∤ a_{n}$ .
$p^{2} ∤ a_{0}$ .

Alors $P$ est irréductible dans $Q [X]$ .

[PER]
p. 67

Application 46. Soit $n \in N^{*}$ . Il existe des polynômes irréductibles de degré $n$ sur $Z$ .

[GOZ]
p. 12

Théorème 47 (Critère d’irréductibilité modulo $p$ ). Soit $P = \sum_{i = 0}^{n} a_{i} X^{i} \in Z [X]$ de degré $n \geq 1$ . Soit $p$ un premier. On suppose $p ∤ a_{n}$ .

Si $\overline{P}$ est irréductible dans $(Z / p Z) [X]$ , alors $P$ est irréductible dans $Q [X]$ .

Exemple 48. Le polynôme $X^{3} - 127 X^{2} + 3608 X + 19$ est irréductible dans $Z [X]$ .

Entiers sommes de deux carrés

[I-P]
p. 137

Notation 49. On note $N : Z [i] a + ib \to \mapsto N a^{2} + b^{2}$ et $Σ$ l’ensemble des entiers qui sont somme de deux carrés.

Remarque 50. $n \in Σ ⟺ \exists z \in Z [i] tel que N (z) = n$ .

Théorème 51 (Deux carrés de Fermat). Soit $n \in N^{*}$ . Alors $n \in Σ$ si et seulement si $v_{p} (n)$ est pair pour tout $p$ premier tel que $p \equiv 3 mod 4$ (où $v_{p} (n)$ désigne la valuation $p$ -adique de $n$ ).

En algèbre linéaire

[I-P]
p. 203

Lemme 52. Soient $p \geq 3$ un nombre premier et $V$ un espace vectoriel sur $F_{p}$ de dimension finie. Les dilatations engendrent $GL (V)$ .

theoreme-de-frobenius-zolotarev

Théorème 53 (Frobenius-Zolotarev). Soient $p \geq 3$ un nombre premier et $V$ un espace vectoriel sur $F_{p}$ de dimension finie. $\forall u \in GL (V), ϵ (u) = (\frac{det ( u )}{p})$ où $u$ est vu comme une permutation des éléments de $V$ .

[ULM21]
p. 124

On se place pour la suite de cette sous-section dans le cadre d’un espace vectoriel $E$ de dimension $m$ sur le corps $F_{q}$ .

Proposition 54. Les groupes précédents sont finis, et :

$∣ GL (E) ∣ = q^{\frac{m ( m - 1 )}{2}} ((q^{m} - 1) \dots (q - 1))$ .
$∣ PGL (E) ∣ = ∣ SL (E) ∣ = \frac{∣ GL ( E ) ∣}{q - 1}$ .
$∣ PSL (E) ∣ = ∣ SL (E) ∣ = \frac{∣ GL ( E ) ∣}{( q - 1 ) pgcd ( m , q - 1 )}$ .

[ROM21]
p. 157

Application 55. Pour tout entier $p \in [[1, m]]$ , il y a $\frac{\prod _{k = m - (p - 1)}^{n} ( q ^{k} - 1 )}{\prod _{k = 1}^{p} ( q ^{k} - 1 )}$ sous-espaces vectoriels de dimension $p$ dans $E$ .

Codes correcteurs

[BMP]
p. 190

Définition 56. On appelle :

Mot un vecteur à coefficients dans $F_{q}$ .
Code correcteur de taille $m$ un sous-ensemble de $F_{q}^{m}$ .
Code linéaire de taille $m$ et de dimension $r$ un sous-espace vectoriel de dimension $r$ de $F_{q}^{m}$ .
Code cyclique de taille $m$ , un code linéaire stable par décalage circulaire.

Exemple 57. Soit un code linéaire $C$ de taille $m$ et de dimension $r$ . On peut décrire $C$ avec une matrice $G \in M_{m \times r} (F_{q})$ , dont les colonnes forment une base de $C$ , de la manière suivante : $C = {G x ∣ x \in F_{q}^{m}}$ $G$ est la matrice génératrice de $C$ . Le codage consiste alors à transformer un mot $m$ du message d’origine en un mot $c \in C$ .

Définition 58.

Le poids d’un mot $x \in F_{q}^{m}$ , noté $ω (x)$ est le nombre de coefficients non nuls de $x$ .
La distance de Hamming entre deux mots $x, y \in F_{q}^{m}$ , est définie par $d_{H} (x, y) = ω (x - y)$ .

Cette distance permet de mesurer la qualité d’un code comme l’atteste la remarque ci-dessous.

Remarque 59. $d_{H}$ est une distance, elle quantifie la notion de mot le plus proche.

Définition 60. Un code $C$ est dit $t$ -correcteur si les boules de centre un mot du code et de rayon $t$ (pour $d_{H}$ ) sont disjointes : les mots de $C$ sont à une distance d’au moins $2 t + 1$ les uns des autres.

Proposition 61. Soit $C$ un code correcteur. On note $d$ la distance minimale de $C$ : $d = x, y \in C x \neq = y min {d_{H} (x, y)}$ Alors $C$ est $t$ -correcteur si et seulement si $d \geq 2 t + 1$ .

Exemple 62. On considère le code $C$ de taille $7$ et de dimension $4$ sur $F_{2}$ dont la matrice génératrice est $G = 1101000011010000110100001101$ $C$ est un code linéaire, dont chacun des mots non nuls est de poids supérieur à $3$ : il est $1$ -correcteur.

Proposition 63 (Borne de Singleton). Soit $C$ un code linéaire de longueur $m$ , de dimension $r$ et de distance minimale $d$ . Alors, $d = x \in C ∖ {0} min {ω (x)} \leq m + 1 - r$