Exercices corrigés — Corps finis

La caractéristique existe (finitude) : c'est le plus petit $m>0$ avec $m\cdot 1=0$.

Supposer $m=ab$ avec $1<a,b<m$ et utiliser que $K$ est intègre.

Un corps n'a pas de diviseur de zéro.

La caractéristique d'un corps $K$ est le plus petit entier $m\geq 1$ tel que

s'il en existe un, et $0$ sinon. On note $m\cdot 1$ cette somme.

Sur un corps fini, une telle $m$ existe forcément — c'est le premier point à établir — et l'on veut montrer qu'elle est première.

L'idée : si $m$ se factorisait, on obtiendrait un produit nul de deux éléments non nuls. Or un corps est intègre : c'est là toute la démonstration.

Considérons la suite $1,\ 2\cdot 1,\ 3\cdot 1,\ \dots$ dans $K$. Comme $K$ est fini, elle ne peut pas prendre que des valeurs distinctes : il existe $i<j$ avec

En soustrayant, $(j-i)\cdot 1=0$ avec $j-i\geq 1$. L'ensemble des entiers $m\geq 1$ tels que $m\cdot 1=0$ est donc non vide, et il admet un plus petit élément.

(elle vaut au moins $2$ car $1\neq 0$ dans un corps, par définition.)

Supposons $p=ab$ avec $1<a,b<p$. Dans $K$ :

La dernière égalité mérite un mot : $(ab)\cdot 1$ est la somme de $ab$ termes égaux à $1$, qu'on peut regrouper en $a$ paquets de $b$, d'où le produit — c'est la distributivité.

Un corps est intègre (un produit est nul seulement si l'un des facteurs l'est : si $xy=0$ et $x\neq 0$, multiplier par $x^{-1}$ donne $y=0$). Donc

Mais $a<p$ et $b<p$ contredisent la minimalité de $p$.

Une reformulation plus structurelle, qui resservira. L'application

est un morphisme d'anneaux. Son noyau est un idéal de $\mathbb{Z}$, donc de la forme $p\mathbb{Z}$ — c'est exactement la définition de la caractéristique.

Le premier théorème d'isomorphisme donne

Or un sous-anneau d'un corps est intègre, donc $\mathbb{Z}/p\mathbb{Z}$ l'est aussi, ce qui force $p$ premier. On retrouve le résultat, et l'on obtient en prime le sous-corps premier (exercice A3).

Le rêve du débutant. En caractéristique $p$, $(a+b)^p=a^p+b^p$ (exercice A6). Impossible en caractéristique $0$, et c'est la clé du Frobenius (exercice C1).

Sur $\mathbb{F}_2$ : $-1=1$, donc soustraire c'est additionner. C'est ce qui simplifie tant les calculs binaires.

Contre-exemple si $p$ n'était pas premier. $\mathbb{Z}/6\mathbb{Z}$ n'est pas un corps : $2\times 3=6\equiv 0$ avec $2\neq 0$ et $3\neq 0$. Ni $2$ ni $3$ n'y est inversible.

C'est le point de départ de toute la construction : les corps finis se bâtissent au-dessus des $\mathbb{F}_p$, et de rien d'autre.

Le sous-corps premier $\mathbb{F}_p$ s'injecte dans $K$.

$K$ est un espace vectoriel sur $\mathbb{F}_p$.

Un $\mathbb{F}_p$-espace vectoriel de dimension $n$ a $p^n$ éléments.

On veut montrer que $\lvert K\rvert=p^n$ — donc que seules les puissances de nombres premiers peuvent être des cardinaux de corps finis.

L'argument tient en une observation : $K$ contient $\mathbb{F}_p$ (exercice A3), et $K$ est un espace vectoriel sur $\mathbb{F}_p$. Un espace vectoriel de dimension $n$ sur un corps à $p$ éléments a exactement $p^n$ éléments.

$K$ contient le sous-corps premier $\mathbb{F}_p$ (exercice A3). Prenons pour :

• vecteurs : les éléments de $K$, avec l'addition de $K$ ;
• scalaires : les éléments de $\mathbb{F}_p\subset K$, agissant par la multiplication de $K$.

Les axiomes d'espace vectoriel — associativité, distributivité, $1\cdot x=x$ — sont des cas particuliers des axiomes de corps de $K$. Il n'y a rien à vérifier, tout est hérité.

$K$ est donc un $\mathbb{F}_p$-espace vectoriel, et il est de dimension finie puisqu'il est fini (une famille génératrice finie existe : $K$ tout entier).

Soit $n=\dim_{\mathbb{F}_p}K$ et $(e_1,\dots,e_n)$ une base. Tout élément de $K$ s'écrit de façon unique

L'unicité est ce qui rend le comptage possible : l'application $(\lambda_1,\dots,\lambda_n)\mapsto x$ est une bijection de $\mathbb{F}_p^{\,n}$ sur $K$.

($n\geq 1$ car $K$ contient au moins $\{0,1\}$.)

Il n'existe aucun corps à $6$, $10$, $12$, $15$ éléments — ces nombres ne sont pas des puissances de premiers.

⚠️ Ne pas confondre $\mathbb{F}_4$ et $\mathbb{Z}/4\mathbb{Z}$. Le second n'est pas un corps : $2\times 2=4\equiv 0$, donc $2$ est un diviseur de zéro. $\mathbb{F}_4$ se construit autrement — comme quotient $\mathbb{F}_2[X]/(X^2+X+1)$ (exercice A4).

Le théorème dit : si un corps fini existe, son cardinal est $p^n$. La réciproque est vraie aussi, mais elle demande une construction :

• l'existence est l'exercice E4 (corps de décomposition de $X^{p^n}-X$) ;
• l'unicité est l'exercice E5.

C'est ce qui autorise la notation $\mathbb{F}_q$ ou $\mathrm{GF}(q)$ : il n'y a qu'un corps à $q$ éléments, et parler « du » corps à $q$ éléments a un sens.

⚠️ Nuance importante : unique à isomorphisme près, pas unique comme écriture. $\mathbb{F}_2[X]/(X^3+X+1)$ et $\mathbb{F}_2[X]/(X^3+X^2+1)$ sont deux présentations différentes du même $\mathrm{GF}(8)$.

Considérer le morphisme d'anneaux $\mathbb{Z}\to K$, $k\mapsto k\cdot 1$.

Son noyau est $p\mathbb{Z}$ (par définition de la caractéristique).

Appliquer le théorème d'isomorphisme.

Le sous-corps premier de $K$ est le plus petit sous-corps de $K$ — c'est-à-dire l'intersection de tous les sous-corps, ou de façon équivalente le sous-corps engendré par $1$.

On veut montrer qu'en caractéristique $p$, il est isomorphe à $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$.

C'est ce résultat qui permet de dire « $K$ contient $\mathbb{F}_p$ », et donc de le voir comme un $\mathbb{F}_p$-espace vectoriel (exercice A2).

Reprenons $\chi:\mathbb{Z}\to K$, $m\mapsto m\cdot 1$ (exercice A1). C'est l'unique morphisme d'anneaux de $\mathbb{Z}$ vers $K$ — un morphisme unitaire est déterminé par l'image de $1$.

Son noyau est $p\mathbb{Z}$ par définition de la caractéristique.

Le premier théorème d'isomorphisme donne alors

$\operatorname{Im}\chi$ est isomorphe à $\mathbb{Z}/p\mathbb{Z}$, qui est un corps puisque $p$ est premier (exercice A1) : tout $a$ non nul modulo $p$ est premier avec $p$, donc inversible par Bézout.

C'est le plus petit. Tout sous-corps $L$ de $K$ contient $1$ (par définition d'un sous-corps unitaire), donc contient toutes les sommes $m\cdot 1$, donc contient $\operatorname{Im}\chi$.

Le sous-corps premier est donc bien $\operatorname{Im}\chi\simeq\mathbb{F}_p$.

On écrit couramment $\mathbb{F}_p\subset K$, en identifiant l'entier $m$ à l'élément $m\cdot 1$ de $K$. C'est un abus commode mais réel : les éléments de $K$ ne sont pas des entiers.

Exemple sur $\mathrm{GF}(4)=\mathbb{F}_2[X]/(X^2+X+1)$ : ses quatre éléments sont $0,1,\alpha,\alpha+1$ (exercice A4). Son sous-corps premier est $\{0,1\}\simeq\mathbb{F}_2$, et $\alpha$ n'y est pas.

Autre exemple : dans $\mathrm{GF}(8)$, le sous-corps premier est encore $\{0,1\}$ — et c'est le seul sous-corps propre, puisque les sous-corps de $\mathrm{GF}(2^3)$ correspondent aux diviseurs de $3$, à savoir $1$ et $3$ (exercice D1).

Les trois premiers exercices s'emboîtent :

L'ordre logique est A1 puis A3 puis A2, même si l'énoncé les présente autrement : A2 a besoin de A3, qui a besoin de A1.

Et l'on obtient au passage une information sur les morphismes : tout morphisme de corps entre corps finis fixe le sous-corps premier, puisqu'il envoie $1$ sur $1$, donc $m\cdot 1$ sur $m\cdot 1$. C'est ce qui donne son sens au groupe de Galois de l'exercice C6 — le groupe des automorphismes fixant $\mathbb{F}_p$ est en réalité le groupe de tous les automorphismes.

La relation $\alpha^2+\alpha+1=0$ donne $\alpha^2=\alpha+1$ (caractéristique $2$).

Les $4$ éléments sont $0,1,\alpha,\alpha+1$.

Réduire chaque produit modulo $\alpha^2=\alpha+1$.

$\mathrm{GF}(4)=\mathbb{F}_2[X]/(X^2+X+1)$. C'est un corps parce que $X^2+X+1$ est irréductible sur $\mathbb{F}_2$ (exercice E1) : un polynôme de degré $2$ est réductible si et seulement s'il a une racine, et

(modulo $2$). Aucune racine, donc irréductible — et c'est le seul irréductible de degré $2$ sur $\mathbb{F}_2$ (exercice D4 : $N_2(2)=1$).

Les éléments du quotient sont les restes de la division par $X^2+X+1$, donc les polynômes de degré $\leq 1$ :

Quatre éléments ✓ — cohérent avec $\lvert K\rvert=p^n=2^2$.

Dans le quotient, $X^2+X+1=0$, donc

(en caractéristique $2$, $-1=1$ : les signes disparaissent.)

C'est la seule règle à connaître : elle permet de ramener toute puissance de $\alpha$ à un polynôme de degré $\leq 1$.

(car $2\alpha=0$ en caractéristique $2$.)

$\alpha$ est donc d'ordre $3$ dans le groupe multiplicatif, qui a $4-1=3$ éléments : $\alpha$ est primitif, et $\mathrm{GF}(4)^\times=\{1,\alpha,\alpha^2\}$ est cyclique (exercice B1).

Contrôle par le théorème de Lagrange : l'ordre divise $\lvert K^\times\rvert=3$, qui est premier, donc l'ordre est $1$ ou $3$. Comme $\alpha\neq 1$, c'est $3$ ✓.

Les trois calculs non triviaux :

Les inverses se lisent sur la table — ce sont les positions du $1$ :

Contrôles de cohérence : chaque ligne et chaque colonne est une permutation des trois éléments (conséquence de $x\mapsto ax$ bijective pour $a\neq 0$), et la table est symétrique (commutativité) ✓. En notation exponentielle, elle se réduit à $\alpha^i\alpha^j=\alpha^{i+j\bmod 3}$.

C'est l'erreur la plus fréquente, et elle se voit sur la structure additive.

Dans $\mathrm{GF}(4)$, tout élément vérifie $x+x=0$ : le groupe additif est le groupe de Klein, pas le groupe cyclique d'ordre $4$.

👉 La règle générale : $\mathbb{Z}/n\mathbb{Z}$ n'est un corps que si $n$ est premier. Pour $q=p^n$ avec $n\geq 2$, il faut passer par un quotient de polynômes — c'est tout l'objet de l'exercice E4.

Traiter d'abord $x=0$.

Pour $x\neq 0$, utiliser que $\mathbb{F}_q^\times$ a $q-1$ éléments.

Appliquer le théorème de Lagrange (ou $g^{\lvert G\rvert}=e$).

Pour tout $x\in\mathbb{F}_q$ avec $q=p^n$ :

C'est la généralisation du petit théorème de Fermat ($a^p\equiv a\pmod p$), qui en est le cas $n=1$.

Ce résultat est le pivot du chapitre : il dit que $\mathbb{F}_q$ est exactement l'ensemble des racines de $X^q-X$, ce qui donnera la factorisation de l'exercice C5, l'existence (E4) et le comptage des irréductibles (D3).

$\mathbb{F}_q^\times$ est un groupe multiplicatif à $q-1$ éléments.

Le théorème de Lagrange affirme que l'ordre d'un élément divise l'ordre du groupe. Donc si $d$ est l'ordre de $x$, on a $d\mid q-1$, et

En multipliant par $x$ :

(avec $q\geq 2$, donc pas de $0^0$.) Le cas est trivial, mais il faut le dire : c'est ce qui permet d'écrire « pour tout $x\in\mathbb{F}_q$ » et non « pour tout $x$ non nul ».

C'est cette formulation complète qui rend le polynôme $X^q-X$ intéressant : il a exactement $q$ racines dans $\mathbb{F}_q$, donc toutes ses racines y sont.

Sur $\mathrm{GF}(4)$, il faut $x^4=x$ :

(en utilisant $\alpha^3=1$, exercice A4.) De même $(\alpha+1)^4=(\alpha+1)$, puisque $\alpha+1=\alpha^2$ et $(\alpha^2)^4=\alpha^8=(\alpha^3)^2\alpha^2=\alpha^2$ ✓.

Sur $\mathrm{GF}(8)$, il faut $x^8=x$, c'est-à-dire $x^7=1$ pour $x\neq 0$. Or $\alpha$ y est d'ordre $7$ (exercice B2), donc $\alpha^7=1$ ✓, et tout élément non nul est une puissance de $\alpha$.

Sur $\mathbb{F}_5$ (cas $n=1$, Fermat) : $2^5=32=30+2\equiv 2\pmod 5$ ✓.

1. Le polynôme $X^q-X$ est scindé sur $\mathbb{F}_q$ et à racines simples :

car il a $q$ racines distinctes et son degré est $q$ (exercice C5).

2. Les carrés. $x^{q-1}=1$ pour $x\neq 0$, donc $(x^{(q-1)/2})^2=1$ lorsque $q$ est impair, d'où $x^{(q-1)/2}=\pm 1$. C'est le critère d'Euler, qui distingue les carrés des non-carrés (exercice B5).

3. Le Frobenius est d'ordre $n$. $x\mapsto x^p$ itéré $n$ fois donne $x\mapsto x^{p^n}=x^q=x$, c'est-à-dire l'identité. Donc l'ordre de $\varphi$ divise $n$ — et vaut exactement $n$ (exercice C2).

👉 Chacune de ces trois conséquences ouvre une section du chapitre. $x^q=x$ est le théorème le plus rentable de la page.

Développer par la formule du binôme.

Étudier la divisibilité de $\binom{p}{k}$ par $p$ pour $0<k<p$.

En caractéristique $p$, $p\cdot c=0$.

L'identité est fausse sur $\mathbb{R}$ — d'où son surnom, freshman's dream : c'est l'erreur classique de l'étudiant qui « distribue » l'exposant.

Elle devient vraie en caractéristique $p$ parce que tous les termes intermédiaires du binôme portent un facteur $p$, donc s'annulent. Toute la démonstration consiste à établir ce fait sur les coefficients binomiaux.

Lemme. Pour $p$ premier et $1\leq k\leq p-1$, $p$ divise $\binom pk$.

Écrivons la relation classique

(elle se vérifie en développant les factorielles.) Le membre de droite est divisible par $p$, donc $p\mid k\binom pk$.

Or $1\leq k\leq p-1$, donc $p\nmid k$. Comme $p$ est premier, le lemme d'Euclide donne

⚠️ La primalité est indispensable. Pour $p=4$ : $\binom 42=6$ n'est pas divisible par $4$. Et de fait, $(a+b)^4\neq a^4+b^4$ dans $\mathbb{Z}/4\mathbb{Z}$ — qui n'est d'ailleurs pas un corps.

Chaque coefficient du milieu est un multiple de $p$, donc nul dans $K$ : $\binom pk\cdot y=0$ pour tout $y$, puisque $p\cdot 1=0$.

Exemple sur $\mathbb{F}_2$ : $(a+b)^2=a^2+2ab+b^2=a^2+b^2$, le terme croisé $2ab$ disparaissant.

Sur $\mathbb{F}_3$ : $(a+b)^3=a^3+3a^2b+3ab^2+b^3=a^3+b^3$.

En appliquant l'identité $n$ fois :

Et pour la soustraction : $(a-b)^p=a^p+(-b)^p=a^p-b^p$ si $p$ est impair (car $(-1)^p=-1$), et $=a^p+b^p=a^p-b^p$ si $p=2$ (car $-1=1$). L'identité vaut donc dans les deux cas.

L'application

est un morphisme de corps :

C'est le Frobenius, et il est au cœur de tout le lot C. Le point remarquable est que l'additivité — la propriété qu'on n'attend jamais d'une puissance — est précisément ce que le rêve du débutant fournit.

👉 Sur $\mathbb{R}$, $x\mapsto x^2$ n'est ni additive ni injective. En caractéristique $p$, $x\mapsto x^p$ est additif et injectif, et sur un corps fini c'est un automorphisme (exercice C1). C'est l'une des différences les plus frappantes entre les deux mondes.

Dans un corps, $X^d-1$ a au plus $d$ racines.

En déduire que $\#\{x\in\mathbb{F}_q^\times:x^d=1\}\leq d$ pour tout $d$.

Un groupe abélien fini d'ordre $N$ vérifiant cette borne pour tout $d\mid N$ est cyclique.

c'est-à-dire : il existe $g$ tel que tout élément non nul s'écrive $g^k$. Un tel $g$ est dit primitif.

Pourquoi ce n'est pas évident : le groupe multiplicatif d'un anneau quelconque n'est généralement pas cyclique. $(\mathbb{Z}/8\mathbb{Z})^\times=\{1,3,5,7\}$ ne l'est pas — tous ses éléments non neutres sont d'ordre $2$. C'est le fait d'être un corps qui change tout, par une propriété très particulière : un polynôme de degré $d$ a au plus $d$ racines.

L'argument compte les éléments par leur ordre, et montre qu'il n'y a pas assez de place pour éviter l'ordre maximal.

Notons $\psi(d)$ le nombre d'éléments de $\mathbb{F}_q^\times$ d'ordre exactement $d$. Comme tout ordre divise $q-1$ (Lagrange), on a

Par ailleurs, l'identité classique sur l'indicatrice d'Euler donne

Il suffit donc de montrer $\psi(d)\leq\varphi(d)$ pour tout $d$ : deux sommes égales dont chaque terme du premier membre est majoré par le terme correspondant du second forcent l'égalité terme à terme.

Si $\psi(d)=0$, l'inégalité est acquise.

Sinon, soit $x$ d'ordre $d$. Les $d$ éléments $1,x,\dots,x^{d-1}$ sont distincts et vérifient tous $y^d=1$ : ce sont donc $d$ racines du polynôme $X^d-1$.

Or un polynôme de degré $d$ sur un CORPS a au plus $d$ racines — c'est ici que l'intégrité intervient de façon décisive. Donc

Tout élément d'ordre $d$ est donc dans $\langle x\rangle$, groupe cyclique d'ordre $d$, qui en contient exactement $\varphi(d)$ (les $x^k$ avec $\gcd(k,d)=1$).

Des deux sommes égales et de $\psi(d)\leq\varphi(d)$, on tire $\psi(d)=\varphi(d)$ pour tout $d\mid q-1$.

En particulier pour $d=q-1$ :

Il existe donc au moins un élément d'ordre $q-1$, c'est-à-dire un générateur :

et le nombre d'éléments primitifs est exactement $\varphi(q-1)$ (exercice B3).

Les deux derniers ne sont pas des corps — et c'est exactement pour cela que l'argument des racines ne s'y applique pas : dans $\mathbb{Z}/8\mathbb{Z}$, le polynôme $X^2-1$ a quatre racines ($1,3,5,7$), ce qui est impossible sur un corps.

Ce que le théorème achète : une table de logarithmes. Chaque élément non nul s'écrit $\alpha^k$, et la multiplication devient une addition d'exposants modulo $q-1$ (exercice B2). C'est ce qui rend l'arithmétique dans $\mathrm{GF}(2^8)$ implantable par deux tables de $256$ octets — le cœur de l'AES et de Reed-Solomon (exercice D6).

$\alpha^3=\alpha+1$ ; calculer les puissances successives.

$\lvert\mathbb{F}_8^\times\rvert=7$ est premier : tout élément $\neq 1$ est d'ordre $7$.

Réduire chaque puissance modulo $\alpha^3=\alpha+1$.

$\mathrm{GF}(8)=\mathbb{F}_2[X]/(X^3+X+1)$, avec $\alpha=\bar X$. On veut montrer que $\alpha$ est primitif (d'ordre $7$) et dresser la table des puissances.

Cette table est l'outil de calcul du chapitre : elle transforme la multiplication en addition d'exposants, et donne les inverses par lecture directe.

La relation fondamentale, issue du quotient :

(caractéristique $2$ : les signes disparaissent.)

On multiplie par $\alpha$ à chaque pas, en réduisant par $\alpha^3=\alpha+1$ dès qu'un $\alpha^3$ apparaît.

(le $\alpha$ et le $\alpha$ s'annulent, caractéristique $2$.)

Le contrôle qui valide la table : les sept écritures binaires sont toutes distinctes et couvrent les sept vecteurs non nuls de $\mathbb{F}_2^{\,3}$. Si deux coïncidaient, la table serait fausse ou $\alpha$ ne serait pas primitif.

L'ordre de $\alpha$ divise $\lvert\mathrm{GF}(8)^\times\rvert=7$ (Lagrange). Or $7$ est premier, donc l'ordre vaut $1$ ou $7$.

Comme $\alpha\neq 1$, l'ordre est $7$ :

Cas particulier heureux : quand $q-1$ est premier, tout élément $\neq 0,1$ est primitif — il n'y a rien à vérifier. En général il faut tester que $\alpha^{(q-1)/\ell}\neq 1$ pour chaque facteur premier $\ell$ de $q-1$.

Nombre d'éléments primitifs : $\varphi(7)=6$, c'est-à-dire tous les éléments sauf $1$ (exercice B3).

La table fait passer de la notation polynomiale à la notation exponentielle, et la multiplication devient une addition modulo $7$ :

Exemple. $(\alpha^2+1)(\alpha+1)$. Lisons la table : $\alpha^2+1=\alpha^6$ et $\alpha+1=\alpha^3$. Donc

Contrôle par le calcul direct :