Problème — Le théorème de la racine primitive : ${\mathbb{F}}_p^{\times }$ est cyclique

1) Un polynôme de degré $d$ a au plus $d$ racines dans un corps. Récurrence sur $d$, portant sur tous les polynômes non nuls à la fois.

Initialisation, $d=0$. Un polynôme non nul de degré $0$ est une constante non nulle : aucune racine.

Hérédité. Soit $d\ge 1$ et $P$ non nul de degré $d$. Si $P$ n'a aucune racine, c'est fini. Sinon, soit $a$ une racine. La division euclidienne par $X-a$, licite car ce polynôme est unitaire, s'écrit $P=(X-a)Q+R$ avec $R$ constant ; en évaluant en $a$, $R=P(a)=0$. Donc $P=(X-a)Q$ avec $\mathrm{deg}Q=d-1$ et $Q\ne 0$.

Soit $b$ une racine de $P$ avec $b\ne a$ : alors $0=P(b)=(b-a)Q(b)$ et $b-a\ne 0$ ; comme $K$ est un corps, donc intègre, il vient $Q(b)=0$. Toutes les racines de $P$ autres que $a$ sont racines de $Q$, qui en a au plus $d-1$ par hypothèse de récurrence. Total : au plus $d$.

⚠️ Ce qui a servi, exactement. L'intégrité du corps, et rien d'autre. On n'a utilisé ni la factorisation en irréductibles sur ${\mathbb{F}}_p$, ni aucune arithmétique de ${\mathbb{F}}_p[X]$ — le programme écarte explicitement l'étude des irréductibles de $\mathbb{K}[X]$ pour un corps autre que $\mathbb{R}$ ou $\mathbb{C}$. Tout le problème ne s'appuiera que sur cet énoncé-ci.

Le contre-exemple hors d'un corps. Dans $\mathbb{Z}/8\mathbb{Z}$, le polynôme $X^2-\overline{1}$, de degré $2$, a quatre racines (exercice 6). C'est l'intégrité qui manque, et l'hérédité ci-dessus s'effondre précisément à la ligne « $(b-a)Q(b)=0$ donc $Q(b)=0$ ».

2) Un groupe cyclique d'ordre $d$ a exactement $\phi (d)$ éléments d'ordre $d$. Soit $G=⟨x⟩$ avec $\mathrm{ord}(x)=\#G=d$ ; ses éléments sont $x^0,\dots ,x^{d-1}$, deux à deux distincts. Pour $m\ge 1$, $${\left(x^k\right)}^m=e⟺x^{km}=e⟺d\mid km.$$ Posons $\delta =k\wedge d$, $d=\delta d^{\prime }$, $k=\delta k^{\prime }$ avec $d^{\prime }\wedge k^{\prime }=1$ : alors $d\mid km⟺d^{\prime }\mid k^{\prime }m⟺d^{\prime }\mid m$ par le lemme de Gauss. Le plus petit tel $m$ est $d^{\prime }$, donc $$\mathrm{ord}\left(x^k\right)=\frac{d}{k\wedge d}.$$ Par conséquent $\mathrm{ord}\left(x^k\right)=d⟺k\wedge d=1$, et il y a $\phi (d)$ tels $k$ dans $\{0,1,\dots ,d-1\}$. $G$ a donc exactement $\phi (d)$ éléments d'ordre $d$ : ce sont exactement ses générateurs.

3) $\psi (d)$ vaut $0$ ou $\phi (d)$. Soit $d\mid p-1$. Si $\psi (d)=0$, rien à montrer. Supposons donc qu'il existe $x$ d'ordre exactement $d$, et posons $H=⟨x⟩$, cyclique de cardinal $d$.

Les éléments de $H$ sont racines de $X^d-\overline{1}$. Pour $y=x^j\in H$, $y^d={\left(x^d\right)}^j=\overline{1}$. Cela fournit $d$ racines distinctes de $X^d-\overline{1}$ dans le corps ${\mathbb{F}}_p$.

Il n'y en a pas d'autres. Le polynôme $X^d-\overline{1}$ est non nul de degré $d$ : d'après la question 1, il a au plus $d$ racines. Il en a donc exactement $d$, et $$\left\{y\in {\mathbb{F}}_p^{\times }:y^d=\overline{1}\right\}=H.$$

Conclusion. Tout élément $z$ d'ordre $d$ vérifie $z^d=\overline{1}$, donc appartient à $H$ ; et dans $H$, cyclique d'ordre $d$, il y a exactement $\phi (d)$ éléments d'ordre $d$ (question 2). Donc $\psi (d)=\phi (d)$. En résumé : $\psi (d)\le \phi (d)$ pour tout $d$, avec égalité dès qu'il existe au moins un élément d'ordre $d$.

Le point délicat. C'est ici que l'hypothèse « $p$ premier » entre en jeu, et nulle part ailleurs : elle sert uniquement à garantir que ${\mathbb{F}}_p$ est un corps, donc que la question 1 s'applique. Dans $\mathbb{Z}/8\mathbb{Z}$, le groupe des inversibles $\left\{\overline{1},\overline{3},\overline{5},\overline{7}\right\}$ possède trois éléments d'ordre $2$ alors que $\phi (2)=1$ : la question 3 y est fausse, et de fait ce groupe n'est pas cyclique.

4) Le comptage global, et la conclusion. Chaque élément de ${\mathbb{F}}_p^{\times }$ a un ordre fini, qui divise $p-1$ par le théorème de Lagrange — dont la démonstration est exigible ici, ${\mathbb{F}}_p^{\times }$ étant commutatif. Les ensembles d'éléments d'ordre $d$, pour $d\mid p-1$, partitionnent donc ${\mathbb{F}}_p^{\times }$ : $$\sum _{d\mid p-1}\psi (d)=p-1.$$ D'autre part, l'exercice 7 appliqué à $n=p-1$ donne ${\sum }_{d\mid p-1}\phi (d)=p-1$. Soustrayons : $$\sum _{d\mid p-1}(\phi (d)-\psi (d))=0.$$ Or, d'après la question 3, chaque terme est positif ou nul. Une somme de termes positifs ou nuls qui vaut zéro a tous ses termes nuls : $$\psi (d)=\phi (d)\text{pour tout }d\mid p-1.$$ En particulier $\psi (p-1)=\phi (p-1)\ge 1$ : il existe un élément $g$ d'ordre $p-1$. Le sous-groupe $⟨g⟩$ a alors $p-1$ éléments, autant que le groupe entier, donc $${\mathbb{F}}_p^{\times }=⟨g⟩\text{est cyclique}.$$ Un tel générateur s'appelle une racine primitive modulo $p$, et il y en a exactement $\phi (p-1)$.

Le mécanisme, à retenir. On disposait d'une majoration terme à terme ($\psi \le \phi$) et d'une égalité des sommes ; les deux ensemble forcent l'égalité terme à terme. Aucun élément d'ordre $p-1$ n'a été construit : on a seulement montré qu'il ne pouvait pas ne pas y en avoir.

5) Racines primitives modulo $7$ et modulo $11$.

Modulo $7$. Le cardinal est $6$, donc un ordre divise $6$ : pour montrer qu'un élément est d'ordre $6$, il suffit d'éliminer les diviseurs stricts maximaux, c'est-à-dire de vérifier $x^2\ne \overline{1}$ et $x^3\ne \overline{1}$. Pour $\overline{3}$ : $3^2=9\equiv 2\ne 1$ et $3^3=27\equiv 6\ne 1$. Donc $3$ est une racine primitive modulo $7$. Contrôle en déroulant : $3^1=3$, $3^2=2$, $3^3=6$, $3^4=4$, $3^5=5$, $3^6=1$ — les six éléments non nuls apparaissent. Les générateurs sont les $3^k$ avec $k\wedge 6=1$, soit $k\in \{1,5\}$ : ce sont $\overline{3}$ et $3^5=\overline{5}$, et il y en a $\phi (6)=2$ ✓. (À l'inverse, $\overline{2}$ n'en est pas une : $2^3=8\equiv 1$, donc $\overline{2}$ est d'ordre $3$.)

Modulo $11$. Le cardinal est $10$ ; il suffit de vérifier $x^2\ne \overline{1}$ et $x^5\ne \overline{1}$. Pour $\overline{2}$ : $2^2=4\ne 1$ et $2^5=32\equiv 10\ne 1$. Donc $2$ est une racine primitive modulo $11$. Contrôle : $2^1=2$, $2^2=4$, $2^3=8$, $2^4=5$, $2^5=10$, $2^6=9$, $2^7=7$, $2^8=3$, $2^9=6$, $2^{10}=1$ modulo $11$. Les générateurs sont les $2^k$ avec $k\wedge 10=1$, soit $k\in \{1,3,7,9\}$ : ce sont $\overline{2}$, $\overline{8}$, $\overline{7}$ et $\overline{6}$ — quatre racines primitives, et $\phi (10)=4$ ✓.

6) Le nombre de solutions de $x^k=\overline{1}$, et le théorème. Soit $g$ une racine primitive : tout élément de ${\mathbb{F}}_p^{\times }$ s'écrit de façon unique $g^j$ avec $0\le j\le p-2$. Posons $\delta =k\wedge (p-1)$, $p-1=\delta n^{\prime }$, $k=\delta k^{\prime }$ avec $n^{\prime }\wedge k^{\prime }=1$. Alors $${\left(g^j\right)}^k=\overline{1}⟺(p-1)\mid jk⟺n^{\prime }\mid j{k}^{\prime }⟺n^{\prime }\mid j,$$ la dernière équivalence étant le lemme de Gauss. Les entiers $j\in \{0,\dots ,p-2\}$ multiples de $n^{\prime }$ sont $0,n^{\prime },2n^{\prime },\dots ,(\delta -1)n^{\prime }$ : il y en a exactement $(p-1)/n^{\prime }=\delta$. Donc l'équation $x^k=\overline{1}$ a exactement $k\wedge (p-1)$ solutions dans ${\mathbb{F}}_p^{\times }$.

Contrôle. $p=7$, $k=4$ : $4\wedge 6=2$, on attend deux solutions. Les puissances quatrièmes valent $1^4=1$, $2^4=16\equiv 2$, $3^4=81\equiv 4$, $4^4=256\equiv 4$, $5^4=625\equiv 2$, $6^4=1296\equiv 1$ : les solutions sont $\overline{1}$ et $\overline{6}$, exactement deux ✓. (À comparer avec l'exercice 6 : dans $\mathbb{Z}/8\mathbb{Z}$, qui n'est pas un corps, $x^2=\overline{1}$ avait quatre solutions alors que $2\wedge 4=2$.)

Le théorème obtenu — théorème de la racine primitive (Gauss, 1801). Pour tout nombre premier $p$, le groupe multiplicatif ${\left(\mathbb{Z}/p\mathbb{Z}\right)}^{\times }={\mathbb{F}}_p^{\times }$ est cyclique, d'ordre $p-1$. Il possède exactement $\phi (p-1)$ générateurs, appelés racines primitives modulo $p$ ; et pour tout entier $k\ge 1$, l'équation $x^k=\overline{1}$ y admet exactement $k\wedge (p-1)$ solutions.

Ce que le problème installe. Trois idées qui dépassent ce chapitre. D'abord, dans un corps, le degré borne le nombre de racines, et cette borne est un instrument de démonstration, pas une information — c'est elle qui a rendu la question 3 possible. Ensuite, une inégalité terme à terme jointe à une égalité des sommes force l'égalité partout ; on retrouvera cet argument pour les dimensions des sous-espaces propres, dont la somme vaut celle de l'espace si et seulement si l'endomorphisme est diagonalisable. Enfin, une existence peut s'obtenir sans construction : personne ici n'a exhibé de racine primitive, on a seulement montré qu'il y en a $\phi (p-1)$ — et de fait, il n'existe à ce jour aucune formule donnant la plus petite.