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 WilsonSoit $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

Théorème de WedderburnTout 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 $\forall x \in F_{q}, P (x) = f (x)$ . Il est donné par $P = u \in F_{q} \sum f (u) (1 - (X - u)^{q - 1})$

Proposition 34

Les sous-groupes additifs de $F_{q}$ sont les sous- $F_{p}$ -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é quadratiqueSoit $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}{17}) = (\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

Lemme de 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}$ , $γ (P Q) = γ (P) γ (Q)$ (où $γ (P)$ est le contenu du polynôme $P$ ).

Théorème 45

Critère d’EisensteinSoit $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 FermatSoit $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

Théorème de 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) ∣ = \frac{∣ SL ( E ) ∣}{pgcd ( m , q - 1 )} = \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 SingletonSoit $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$