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.

Les multiples $1,2\cdot1,3\cdot1,\dots$ ne peuvent être tous distincts ($K$ fini) : il existe un plus petit $m>0$ avec $m\cdot 1=0$. C'est la caractéristique.

D'abord $m\geq 2$ : dans un corps $1\neq 0$, donc $1\cdot 1=1\neq 0$. Ensuite, si $m=ab$ avec $1<a,b<m$, alors $(a\cdot 1)(b\cdot 1)=(ab)\cdot 1=m\cdot 1=0$ ; mais par minimalité de $m$ on a $a\cdot 1\neq 0$ et $b\cdot 1\neq 0$ (car $0<a,b<m$), ce qui contredit l'intégrité du corps. $m$ n'a donc pas de factorisation non triviale : $m=p$ est premier.

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.

$K$ contient le sous-corps premier $\mathbb{F}_p=\{0,1,\dots,(p-1)\cdot1\}$. $K$ est alors un espace vectoriel sur $\mathbb{F}_p$ (l'addition de $K$, la multiplication externe par $\mathbb{F}_p$). Étant fini, il est de dimension finie $n$.

Une base $(e_1,\dots,e_n)$ donne une bijection $K\cong\mathbb{F}_p^{\,n}$ (coordonnées) : chaque vecteur $\sum\lambda_i e_i$ a $p$ choix par coordonnée, soit $\lvert K\rvert=p^n$.

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.

L'application $\psi:\mathbb{Z}\to K,\ k\mapsto k\cdot 1$ est un morphisme d'anneaux. Son noyau est $\{k:k\cdot 1=0\}=p\mathbb{Z}$ (car $p$ = caractéristique).

Par le théorème d'isomorphisme, $\operatorname{im}\psi\cong\mathbb{Z}/p\mathbb{Z}=\mathbb{F}_p$. Comme $p$ est premier, $\mathbb{F}_p$ est un corps : c'est le plus petit sous-corps de $K$.

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

$\alpha^2=\alpha+1$ ; $\alpha^3=\alpha\cdot\alpha^2=\alpha(\alpha+1)=\alpha^2+\alpha=(\alpha+1)+\alpha=1$ (car $2\alpha=0$). Donc $\alpha$ est d'ordre $3$, primitif.

$\alpha\cdot\alpha=\alpha+1$ ; $\alpha(\alpha+1)=\alpha^2+\alpha=1$ ; $(\alpha+1)^2=\alpha^2+1=(\alpha+1)+1=\alpha$. Le groupe $\mathbb{F}_4^\times=\{1,\alpha,\alpha^2\}$ est cyclique d'ordre $3$.

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$).

$0^q=0$.

$x\in\mathbb{F}_q^\times$, groupe d'ordre $q-1$. Par Lagrange, $x^{q-1}=1$, donc $x^q=x\cdot x^{q-1}=x$.

$x^q=x$ pour tout $x\in\mathbb{F}_q$. Pour $q=p$ premier, on retrouve Fermat $x^p\equiv x\pmod p$.

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

$(a+b)^p=\sum_{k=0}^{p}\binom{p}{k}a^k b^{p-k}$.

Pour $0<k<p$, $\binom{p}{k}=\dfrac{p!}{k!(p-k)!}$ est un entier ; or $p\mid p!$ tandis que $p\nmid k!$ et $p\nmid(p-k)!$ ($p$ premier, $0<k,p-k<p$). Donc $p\mid\binom{p}{k}$, et en caractéristique $p$ ces termes sont nuls.

Il ne reste que $k=0$ et $k=p$ : $(a+b)^p=a^p+b^p$. (Par récurrence, $(a+b)^{p^n}=a^{p^n}+b^{p^n}$.)

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.

$\mathbb{F}_q^\times$ est abélien d'ordre $N=q-1$. Pour $d\mid N$, les éléments d'ordre divisant $d$ sont des racines de $X^d-1$ ; dans un corps, ce polynôme a au plus $d$ racines, donc $\#\{x:x^d=1\}\leq d$.

Notons $\psi(d)$ le nombre d'éléments d'ordre exactement $d$ ($d\mid N$). Si $\psi(d)>0$, prenons $x$ d'ordre $d$ : $\langle x\rangle$ a $d$ éléments, tous racines de $X^d-1$ ; comme il y en a au plus $d$, $\langle x\rangle$ contient tous les éléments d'ordre divisant $d$, et ceux d'ordre exactement $d$ sont ses $\varphi(d)$ générateurs. Donc $\psi(d)\in\{0,\varphi(d)\}$, en particulier $\psi(d)\leq\varphi(d)$. Or $\sum_{d\mid N}\psi(d)=N=\sum_{d\mid N}\varphi(d)$ : l'inégalité terme à terme jointe à l'égalité des sommes force $\psi(d)=\varphi(d)$ pour tout $d$ — en particulier $\psi(N)=\varphi(N)\geq 1$.

Donc $\mathbb{F}_q^\times$ possède un élément d'ordre $q-1$ : c'est un élément primitif, et $\mathbb{F}_q^\times=\langle g\rangle$ est cyclique.

$\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$.

$\alpha^0=1$, $\alpha^1=\alpha$, $\alpha^2=\alpha^2$, $\alpha^3=\alpha+1$, $\alpha^4=\alpha^2+\alpha$, $\alpha^5=\alpha^2+\alpha+1$, $\alpha^6=\alpha^2+1$, puis $\alpha^7=1$.

Les $7$ puissances sont distinctes et énumèrent $\mathbb{F}_8^\times$ : $\alpha$ est d'ordre $7$, donc primitif. (Comme $7$ est premier, tout élément $\neq 1$ est primitif.)

$\langle x\rangle$ est un sous-groupe de $\mathbb{F}_q^\times$.

Appliquer Lagrange.

Dans un groupe cyclique d'ordre $N$, le nombre de générateurs est $\varphi(N)$.

$\langle x\rangle$ est un sous-groupe de $\mathbb{F}_q^\times$ (ordre $q-1$) ; par Lagrange, $\operatorname{ord}(x)=\lvert\langle x\rangle\rvert$ divise $q-1$.

$\mathbb{F}_q^\times$ étant cyclique d'ordre $q-1$, ses générateurs (éléments d'ordre $q-1$) sont au nombre de $\varphi(q-1)$.

L'application fixe $0$ ; étudier sa restriction au groupe cyclique $\mathbb{F}_q^\times$.

Dans un groupe cyclique d'ordre $N$, $x\mapsto x^k$ est bijective $\iff\gcd(k,N)=1$.

$\gcd(3,7)=1$ pour $\mathrm{GF}(8)$.

Écrivons $\mathbb{F}_q^\times=\langle g\rangle$, ordre $N=q-1$. $x\mapsto x^k$ correspond, en exposant, à $j\mapsto kj\bmod N$, bijective $\iff k$ inversible modulo $N\iff\gcd(k,N)=1$.

Sur $\mathrm{GF}(8)$, $N=7$ et $\gcd(3,7)=1$ : $x\mapsto x^3$ est bijective. (Sur $\mathrm{GF}(4)$, $\gcd(3,3)=3\neq 1$ : $x\mapsto x^3$ n'est pas bijective.)

Considérer $\sigma:\mathbb{F}_q^\times\to\mathbb{F}_q^\times,\ x\mapsto x^2$.

$\sigma$ est un morphisme de groupes ; déterminer son noyau.

$\lvert\operatorname{im}\sigma\rvert=\lvert\mathbb{F}_q^\times\rvert/\lvert\ker\sigma\rvert$.

$\sigma(x)=x^2$ est un morphisme de $\mathbb{F}_q^\times$. Son noyau $\{x:x^2=1\}$ : $x^2-1=(x-1)(x+1)=0$ donne $x=\pm 1$, distincts car $q$ impair ($1\neq -1$). Donc $\lvert\ker\sigma\rvert=2$.

L'image (les carrés non nuls) a pour cardinal $\dfrac{\lvert\mathbb{F}_q^\times\rvert}{\lvert\ker\sigma\rvert}=\dfrac{q-1}{2}$.

Apparier chaque $x$ avec son inverse $x^{-1}$ (produit $1$).

Les éléments égaux à leur inverse vérifient $x^2=1$, soit $(x-1)(x+1)=0$.

Distinguer $q$ impair ($1\neq -1$) et $q$ pair (caractéristique $2$, $-1=1$).

$x=x^{-1}\iff x^2=1\iff(x-1)(x+1)=0\iff x\in\{1,-1\}$ (corps). Si $q$ est impair ($1\neq -1$), ce sont $2$ éléments distincts ; si $q$ est pair (caractéristique $2$), $-1=1$ et seul $1$ convient.

Tous les autres éléments se regroupent en paires $\{x,x^{-1}\}$ de produit $1$. Il reste donc le produit des auto-inverses : $q$ impair $\Rightarrow 1\cdot(-1)=-1$ ; $q$ pair $\Rightarrow 1$. Pour $q=p$ premier impair, on retrouve Wilson : $(p-1)!\equiv -1\pmod p$.

Sens réciproque : si $m=ab$ non trivial, exhiber des diviseurs de zéro.

Sens direct : si $m$ irréductible et $a\not\equiv 0$, alors $\gcd(a,m)=1$.

Utiliser Bézout pour l'inverse.

Si $m=ab$ avec $0<\deg a,\deg b<\deg m$, alors $\bar a\bar b=\bar m=\bar 0$ ; et $\bar a,\bar b\neq\bar 0$ car $m\nmid a$ et $m\nmid b$ (degrés non nuls $<\deg m$). Ce sont des diviseurs de zéro : pas un corps.

Soit $\bar a\neq\bar 0$ (donc $m\nmid a$). $m$ étant irréductible, $\gcd(a,m)=1$ : par Bézout, $au+mv=1$, d'où $\bar a\,\bar u=\bar 1$. Tout élément non nul est inversible : c'est un corps.

Un polynôme de degré $2$ ou $3$ est irréductible $\iff$ il n'a pas de racine.

Évaluer le polynôme en chaque élément du corps de base.

Une racine $\Rightarrow$ un facteur de degré $1$.

$X^2+X+1$ : $f(0)=1$, $f(1)=1$ — pas de racine, irréductible. $X^2+1$ : $f(1)=1+1=0$ — racine $1$, donc $X^2+1=(X+1)^2$, réductible.

$X^2+1$ sur $\mathbb{F}_3$ : $f(0)=1,f(1)=2,f(2)=5=2$ — pas de racine, irréductible ($-1$ n'est pas un carré mod $3$). $X^2+2$ sur $\mathbb{F}_5$ : les carrés sont $\{0,1,4\}$, et $-2=3\notin\{1,4\}$ — pas de racine, irréductible.

$\alpha^{-1}=\alpha^{q-2}=\alpha^6$ (ou via Bézout).

Utiliser la table des logarithmes (cf. B2).

Réduire les produits modulo $\alpha^3=\alpha+1$.

$\alpha^7=1$ donc $\alpha^{-1}=\alpha^6=\alpha^2+1$ (table B2). Vérification : $\alpha\cdot(\alpha^2+1)=\alpha^3+\alpha=(\alpha+1)+\alpha=1$. ✓

$(\alpha^2+1)(\alpha+1)=\alpha^3+\alpha^2+\alpha+1=(\alpha+1)+\alpha^2+\alpha+1=\alpha^2$ (car $\alpha+\alpha=0$, $1+1=0$). En logarithmes : $\alpha^6\cdot\alpha^3=\alpha^9=\alpha^2$.

Considérer un corps de décomposition de $X^q-X$ ($q=p^n$) sur $\mathbb{F}_p$ (existence admise).

Vérifier que $X^q-X$ est séparable (sa dérivée vaut $-1$ en caractéristique $p$).

Montrer que l'ensemble de ses racines est un sous-corps à $q$ éléments.

Soit $q=p^n$ et $L$ un corps de décomposition de $f=X^q-X$ sur $\mathbb{F}_p$ (existence admise, comme en E5). En caractéristique $p$, $q\cdot 1=0$, donc $f'=qX^{q-1}-1=-1$ : $f$ est séparable et possède $q$ racines distinctes dans $L$.

Soit $F=\{x\in L:x^q=x\}$ (les $q$ racines de $f$). $F$ est l'ensemble des points fixes de $\varphi^n$ (où $\varphi:x\mapsto x^p$) ; $\varphi^n$ étant un morphisme de corps (rêve du débutant itéré, A6), $F$ est stable par $+,\times$ et passage à l'inverse : c'est un sous-corps de $L$, de cardinal exactement $q=p^n$.

Montrer que tout corps à $q$ éléments est corps de décomposition de $X^q-X$ sur $\mathbb{F}_p$.

Utiliser que tout élément vérifie $x^q=x$ (lot A).

Invoquer l'unicité du corps de décomposition.

Soit $K$ un corps à $q$ éléments. Tout $x\in K$ vérifie $x^q=x$ (A5), donc $X^q-X=\prod_{x\in K}(X-x)$ se scinde dans $K$ ; comme ses $q$ racines sont exactement les $q$ éléments de $K$, on a $K=\mathbb{F}_p(\text{racines})$ : $K$ est le corps de décomposition de $X^q-X$ sur $\mathbb{F}_p$.

Deux corps de décomposition d'un même polynôme sur $\mathbb{F}_p$ sont isomorphes (résultat admis). Donc deux corps à $q$ éléments sont isomorphes : on note $\mathbb{F}_q$.

$X^2+1$ est irréductible sur $\mathbb{F}_3$ (E2).

Les $9$ éléments sont $a+bi$, $a,b\in\mathbb{F}_3$.

Réduire avec $i^2=2$ et les coefficients modulo $3$.

$X^2+1$ irréductible sur $\mathbb{F}_3$ $\Rightarrow$ corps à $9$ éléments $\{a+bi:a,b\in\{0,1,2\}\}$, avec $i^2=-1=2$.

$(1+i)(2+i)=2+i+2i+i^2=2+3i+2=4+0\cdot i=1$ (car $3i=0$, $4=1$ mod $3$). $i^2=2$, $i^4=(i^2)^2=2^2=4=1$ : $i$ est d'ordre $4$ (non primitif, car $\lvert\mathbb{F}_9^\times\rvert=8$).