Dans cette section nous allons prouver un résultat énoncé dans le chapitre sur les résidus quadratiques. Rappelons d'abord la définition suivante :
Le résultat qui nous intéresse est celui que nous avons énoncé comme suit. Nous allons en effet pouvoir le démontrer grâce aux outils développés dans ce chapitre.
Proposition
Soit $p$ un nombre premier. Il existe exactement $\varphi(p-1)$ racines primitives modulo $p$.
Pour démontrer ce résultat nous aurons besoin du petit lemme suivant, qui peut être montré de diverses manières. Nous en donnons une démonstration assez intuitive.
Lemme
Pour tout $n \geq 1$ entier, on a
$$\sum_{d \mid n} \varphi(d) = n.$$ Autrement dit, on a
$$1 * \varphi = \mathrm{id},$$ où $1$ est la fonction arithmétique $n \mapsto 1$, $\varphi$ est la fonction arithmétique $n \mapsto \varphi(n)$, et $\mathrm{id}$ est la fonction arithmétique $n \mapsto n$.
Démonstration
Nous expliquons ce résultat sur un exemple, à savoir $n = 12$. Examinons les fractions $\frac 1{12}, \frac 2{12}, \ldots, \frac{12}{12}$ et mettons-les sous leur forme irréductible. On obtient les $12$ fractions suivantes :
$$\frac 1 {12},\ \frac 1 6,\ \frac 1 4,\ \frac 1 3,\ \frac 5 {12},\ \frac 1 2,\ \frac 7 {12},\ \frac 2 3,\ \frac 3 4,\ \frac 5 6,\ \frac {11}{12},\ \frac 1 1.$$ Parmi ces fractions, nous en observons quatre ayant $12$ pour dénominateur. Et ces quatre fractions ont $1, 5, 7$ et $11$ pour numérateurs, qui sont bien sûr les nombres inférieurs à $12$ et premiers avec $12$. C'est donc logique qu'ils soient au nombre de $\varphi(12) = 4$. Pareillement, il y a deux fractions ayant $6$ pour dénominateur, et les numérateurs sont $1$ et $5$, qui sont les nombres inférieurs à $6$ et premiers avec $6$. Ils sont donc au nombre de $\varphi(6) = 2$. Vu qu'il y a au total $12$ fractions, on obtient au total que
$$12 = \varphi(12) + \varphi(6) + \varphi(4) + \varphi(3) + \varphi(2) + \varphi(1) = \sum_{d \mid 12} \varphi(d).$$ Et cette preuve fonctionne bien sûr pour n'importe quel $n$ à la place de $12$.
Nous pouvons maintenant passer à la preuve de la proposition sur le nombre de racines primitives modulo $p$.
Démonstration de la proposition
Soit $p$ un nombre premier fixé.
On définit $f \colon \mathbb N_0 \to \mathbb N$ en disant que $f(n)$ est le nombre d'éléments de $\{1,\ldots,p-1\}$ dont l'ordre multiplicatif modulo $p$ est exactement $n$. Remarquons déjà que $f(1) = 1$ puisque le seul élément d'ordre multiplicatif $1$ est $1$. Notre but est de montrer que $f(p-1) = \varphi(p-1)$.
On définit également $g \colon \mathbb N_0 \to \mathbb N$ en disant que $g(n)$ est le nombre d'éléments $x \in \{1,\ldots,p-1\}$ tels que $x^n \equiv 1 \pmod p$. Il est clair qu'un nombre $x$ vérifie cette propriété si et seulement si son ordre multiplicatif $o_p(x)$ divise $n$. Autrement dit, on a l'égalité suivante :
$$\sum_{d\mid n} f(d) = g(n),$$ qui peut se réécrire
$$1 * f = g$$ ou encore
$$f = \mu * g$$ en utilisant la formule d'inversion de Möbius. On voit donc qu'en trouvant une formule pour $g$, on pourra en déduire une formule pour $f$. En fait, vu qu'on s'intéresse surtout à $f(p-1)$, on aura seulement besoin des valeurs $g(d)$ pour $d$ un diviseur de $p-1$.
- Le petit théorème de Fermat nous donne directement $g(p-1) = p-1$.
- Si maintenant $d$ est un diviseur de $p-1$, alors on peut montrer qu'on a également $g(d) = d$. Pour ce faire, le plus simple est probablement d'étudier le polynôme $X^{p-1}-1$ vu comme un polynôme sur $\mathbb Z / p \mathbb Z$. Rappelons que $\mathbb Z / p \mathbb Z$ désigne simplement l'ensemble des éléments $\{0,1,\ldots,p-1\}$ munis de l'addition et de la multiplication modulo $p$. Il s'agit d'un corps, et parler de polynômes à coefficients dans ce corps est donc tout à fait acceptable (comme expliqué dans le chapitre sur les polynômes). Le théorème de Fermat nous indique que ce polynôme $X^{p-1}-1$ a tous les éléments $1,2,\ldots,p-1$ pour racines. Cela signifie qu'on peut factoriser ce polynôme dans $\mathbb Z / p \mathbb Z$ comme
$$X^{p-1}-1 = (X-1)\cdot (X-2)\cdot \ldots \cdot (X-(p-1)).$$ Or, on sait aussi que $X^d-1$ divise $X^{p-1}-1$ lorsque $d$ divise $p-1$. Il en découle que $X^d-1$ se factorise comme $(X-a_1)\cdot (X-a_2) \cdot \ldots \cdot (X-a_d)$ pour certains $a_1, \ldots, a_d \in \{1,2,\ldots,p-1\}$ distincts. Autrement dit, les éléments $a_1,\ldots,a_d$ sont exactement les éléments $x$ de $\{1,2,\ldots,p-1\}$ tels que $x^d \equiv 1 \pmod p$ et on a bien $g(d) = d$ comme annoncé.
Nous pouvons à présent calculer $f(p-1)$. On a
$$f(p-1) = (g * \mu)(p-1) = \sum_{d\mid p-1} \,g(d)\cdot\mu\left(\frac {p-1}d\right) = \sum_{d\mid p-1}\,d\cdot\mu\left(\frac {p-1}d\right) = (\mathrm{id} * \mu)(p-1).$$ Or, le lemme nous indique que $1 * \varphi = \mathrm{id}$, ou encore que $\varphi = \mathrm{id} * \mu$ par la formule d'inversion de Möbius. On obtient donc comme désiré que
$$f(p-1) = \varphi(p-1).$$