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 φ(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≥1 entier, on a
∑d∣nφ(d)=n. Autrement dit, on a
1∗φ=id, où 1 est la fonction arithmétique n↦1, φ est la fonction arithmétique n↦φ(n), et id est la fonction arithmétique n↦n.
Démonstration
Nous expliquons ce résultat sur un exemple, à savoir n=12. Examinons les fractions 112,212,…,1212 et mettons-les sous leur forme irréductible. On obtient les 12 fractions suivantes :
112, 16, 14, 13, 512, 12, 712, 23, 34, 56, 1112, 11. 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 φ(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 φ(6)=2. Vu qu'il y a au total 12 fractions, on obtient au total que
12=φ(12)+φ(6)+φ(4)+φ(3)+φ(2)+φ(1)=∑d∣12φ(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:N0→N en disant que
f(n) est le nombre d'éléments de
{1,…,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)=φ(p−1).
On définit également
g:N0→N en disant que
g(n) est le nombre d'éléments
x∈{1,…,p−1} tels que
xn≡1(modp). Il est clair qu'un nombre
x vérifie cette propriété si et seulement si son ordre multiplicatif
op(x) divise
n. Autrement dit, on a l'égalité suivante :
∑d∣nf(d)=g(n), qui peut se réécrire
1∗f=g ou encore
f=μ∗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 Xp−1−1 vu comme un polynôme sur Z/pZ. Rappelons que Z/pZ désigne simplement l'ensemble des éléments {0,1,…,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 Xp−1−1 a tous les éléments 1,2,…,p−1 pour racines. Cela signifie qu'on peut factoriser ce polynôme dans Z/pZ comme
Xp−1−1=(X−1)⋅(X−2)⋅…⋅(X−(p−1)). Or, on sait aussi que Xd−1 divise Xp−1−1 lorsque d divise p−1. Il en découle que Xd−1 se factorise comme (X−a1)⋅(X−a2)⋅…⋅(X−ad) pour certains a1,…,ad∈{1,2,…,p−1} distincts. Autrement dit, les éléments a1,…,ad sont exactement les éléments x de {1,2,…,p−1} tels que xd≡1(modp) et on a bien g(d)=d comme annoncé.
Nous pouvons à présent calculer
f(p−1). On a
f(p−1)=(g∗μ)(p−1)=∑d∣p−1g(d)⋅μ(p−1d)=∑d∣p−1d⋅μ(p−1d)=(id∗μ)(p−1). Or, le lemme nous indique que
1∗φ=id, ou encore que
φ=id∗μ par la formule d'inversion de Möbius. On obtient donc comme désiré que
f(p−1)=φ(p−1).