Le comptage des ordres : ${\sum }_{d\mid n}\phi (d)=n$

La stratégie, et les outils. Compter deux fois le même ensemble : $\mathbb{Z}/n\mathbb{Z}$ a $n$ éléments, et les trier selon leur ordre donne une somme. Tout le travail est dans le lemme du c). Outils : la caractérisation de l'ordre, le lemme de Gauss, et le fait qu'un groupe cyclique de cardinal $d$ est isomorphe à $\mathbb{Z}/d\mathbb{Z}$, donc a $\phi (d)$ générateurs.

a) L'ordre d'une classe. Pour $m\ge 1$, $m\overline{k}=\overline{0}⟺n\mid mk$. Posons $\delta =k\wedge n$, $n=\delta n^{\prime }$, $k=\delta k^{\prime }$ avec $n^{\prime }\wedge k^{\prime }=1$. Alors $$n\mid mk⟺n^{\prime }\mid m{k}^{\prime }⟺n^{\prime }\mid m,$$ la dernière équivalence étant le lemme de Gauss. Le plus petit $m\ge 1$ convenable est $n^{\prime }$, d'où $\mathrm{ord}\left(\overline{k}\right)=n/(k\wedge n)$. En particulier cet ordre divise $n$ — ce que Lagrange annonçait.

b) Un unique sous-groupe par diviseur. Soit $d\mid n$.

Existence. $H_d=⟨\overline{n/d}⟩$ a pour cardinal $\mathrm{ord}\left(\overline{n/d}\right)=n/\left((n/d)\wedge n\right)=n/(n/d)=d$.

Unicité. Tout sous-groupe de $(\mathbb{Z}/n\mathbb{Z},+)$ est de la forme $⟨\overline{k}⟩$ avec $k\mid n$ — c'est l'exercice 4, où sous-groupes et idéaux coïncident — et son cardinal vaut $n/k$. De $n/k=d$ on tire $k=n/d$, donc $H=H_d$.

c) Le cœur : $\#A_d=\phi (d)$. Soit $x\in A_d$. Le sous-groupe $⟨x⟩$ a pour cardinal l'ordre de $x$, soit $d$ ; par l'unicité du b), $⟨x⟩=H_d$, c'est-à-dire $x$ est un générateur de $H_d$. Réciproquement, tout générateur de $H_d$ est d'ordre $\#H_d=d$. Donc $A_d$ est exactement l'ensemble des générateurs de $H_d$. Or $H_d$ est cyclique de cardinal $d$, donc isomorphe à $\mathbb{Z}/d\mathbb{Z}$ ; un isomorphisme envoie générateurs sur générateurs, et $\mathbb{Z}/d\mathbb{Z}$ en possède $\phi (d)$. D'où $\#A_d=\phi (d)$.

d) Le décompte. Chaque élément a un ordre et un seul, et cet ordre divise $n$ : la famille ${\left(A_d\right)}_{d\mid n}$ est une partition de $\mathbb{Z}/n\mathbb{Z}$. En sommant les cardinaux, $$n=\#\left(\mathbb{Z}/n\mathbb{Z}\right)=\sum _{d\mid n}\#A_d=\sum _{d\mid n}\phi (d).$$

e) La variante arithmétique, et les contrôles.

Le même comptage, sans groupe. Trions les entiers $k\in \{1,\dots ,n\}$ selon la valeur de $k\wedge n$. Dire que $k\wedge n=n/d$ (avec $d\mid n$) revient à écrire $k=(n/d)j$ où $1\le j\le d$ et $j\wedge d=1$ : il y a $\phi (d)$ tels $k$. Sommer sur les diviseurs $d$ de $n$ redonne $n$. C'est la même bijection, lue dans $\{1,\dots ,n\}$ au lieu du groupe.

Contrôle sur $n=12$. Répartition des douze classes selon leur ordre, calculé par le a) : ordre $1$, la classe $\overline{0}$, et $\phi (1)=1$ ; ordre $2$, la classe $\overline{6}$, et $\phi (2)=1$ ; ordre $3$, les classes $\overline{4}$ et $\overline{8}$, et $\phi (3)=2$ ; ordre $4$, les classes $\overline{3}$ et $\overline{9}$, et $\phi (4)=2$ ; ordre $6$, les classes $\overline{2}$ et $\overline{10}$, et $\phi (6)=2$ ; ordre $12$, les classes $\overline{1},\overline{5},\overline{7},\overline{11}$, et $\phi (12)=4$. Total : $1+1+2+2+2+4=12$ ✓.

Second contrôle. $2026=2\times 1013$ avec $1013$ premier ; ses diviseurs sont $1,2,1013,2026$ et $$\phi (1)+\phi (2)+\phi (1013)+\phi (2026)=1+1+1012+1012=2026✓.$$

Ce que l'exercice installe. L'identité est le prototype des raisonnements sur le treillis cyclique : un sous-groupe par diviseur, $\phi (d)$ générateurs pour celui de cardinal $d$. Retenez surtout la forme du raisonnement — partitionner selon une quantité attachée à chaque élément, puis compter de deux façons — et ce qu'elle permet : si, dans un groupe de cardinal $n$, le nombre d'éléments d'ordre $d$ est seulement connu au plus égal à $\phi (d)$ pour chaque $d\mid n$, alors, les deux sommes valant $n$, toutes les inégalités sont des égalités. C'est exactement l'argument du problème de la séance.