Processing .

Théorie > Théorie des nombres > Fonctions arithmétiques

Exemple d'application

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 :

Définition
On dit que a est une racine primitive modulo n si son ordre multiplicatif modulo n vaut φ(n), c'est-à-dire si le plus petit nombre k1 tel que ak1(modn) est k=φ(n).

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 φ(p1) 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 n1 entier, on a
dnφ(d)=n. Autrement dit, on a
1φ=id,1 est la fonction arithmétique n1, φ est la fonction arithmétique nφ(n), et id est la fonction arithmétique nn.

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)=d12φ(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:N0N en disant que f(n) est le nombre d'éléments de {1,,p1} 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(p1)=φ(p1).

On définit également g:N0N en disant que g(n) est le nombre d'éléments x{1,,p1} tels que xn1(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 :
dnf(d)=g(n), qui peut se réécrire
1f=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(p1), on aura seulement besoin des valeurs g(d) pour d un diviseur de p1.

  • Le petit théorème de Fermat nous donne directement g(p1)=p1.

  • Si maintenant d est un diviseur de p1, alors on peut montrer qu'on a également g(d)=d. Pour ce faire, le plus simple est probablement d'étudier le polynôme Xp11 vu comme un polynôme sur Z/pZ. Rappelons que Z/pZ désigne simplement l'ensemble des éléments {0,1,,p1} 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 Xp11 a tous les éléments 1,2,,p1 pour racines. Cela signifie qu'on peut factoriser ce polynôme dans Z/pZ comme
    Xp11=(X1)(X2)(X(p1)). Or, on sait aussi que Xd1 divise Xp11 lorsque d divise p1. Il en découle que Xd1 se factorise comme (Xa1)(Xa2)(Xad) pour certains a1,,ad{1,2,,p1} distincts. Autrement dit, les éléments a1,,ad sont exactement les éléments x de {1,2,,p1} tels que xd1(modp) et on a bien g(d)=d comme annoncé.
Nous pouvons à présent calculer f(p1). On a
f(p1)=(gμ)(p1)=dp1g(d)μ(p1d)=dp1dμ(p1d)=(idμ)(p1). 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(p1)=φ(p1).

Remarque
Dans la preuve ci-dessus, on peut même voir que f(d)=φ(d) pour tout d diviseur de p1. (Il suffit de remplacer p1 par un de ses diviseurs dans les trois dernières lignes de la preuve.) Cela signifie que le nombre d'éléments de {1,,p1} dont l'ordre multiplicatif est d est exactement φ(d). Pour exemple, modulo 11, il y a φ(10)=4 éléments d'ordre multiplicatif 10, φ(5)=4 éléments d'ordre multiplicatif 5, φ(2)=1 élément d'ordre multiplicatif 2, et φ(1)=1 élément d'ordre multiplicatif 1.