Pour tout entier naturel $n$ non nul, vous notez $\varphi(n)$ le nombre d’entiers naturels inférieurs ou égaux à $n-1$ qui sont premiers avec $n.$

Pour tout $n\in\NN$ vous notez :

A_n = \{k\in\llbracket0, n-1\rrbracket, PGCD(k,n)=1\}.

Alors $\varphi(n)$ désigne le nombre d’éléments de l’ensemble $A_n.$

L’objectif de cet article est de démontrer que :

\boxed{\forall n\in\NN, \quad n = \sum_{d\mid n}\varphi(d).}

Note. Pour tout entier $n$ non nul, la somme $\sum_{d\mid n} \varphi(d)$ désigne la somme $\sum_{\substack{1\leq d\leq n \\ d\mid n}} \varphi(d).$

Visualisez la situation pour $n=60$

Déterminez tous les diviseurs de $60$

Le nombre $60$ s’écrit comme un produit faisant apparaître les puissances des nombres premiers $2$, $3$ et $5$ étant donné que :

60 =2^2\times 3\times 5.

$4 = 2^2$ possède trois diviseurs, $1$, $2$ et $4.$

$3$ possède deux diviseurs, $1$ et $3.$

$5$ possède deux diviseurs, $1$ et $5.$

Utilisant le principe du produit, $60$ possède $3\times 2 \times 2 = 12$ diviseurs obtenus comme suit :

\begin{align*}
1\times 1\times 1 &= 1\\
1\times 1\times 5 &= 5\\
1\times 3\times 1 &= 3\\
1\times 3\times 5 &= 15\\
2\times 1\times 1 &= 2\\
2\times 1\times 5 &= 10\\
2\times 3\times 1 &= 6\\
2\times 3\times 5 &= 30\\
4\times 1\times 1 &= 4\\
4\times 1\times 5 &= 20\\
4\times 3\times 1 &= 12\\
4\times 3\times 5 &= 60.
\end{align*}

Vous notez $D$ l’ensemble des diviseurs de $60$, à savoir :

\boxed{D=\{1, 2,3, 4, 5,6, 10, 12, 15, 20, 30, 60\}.}

Parmi tous les entiers compris entre $0$ et $59$ déterminez leur $PGCD$ avec $60$

Vous remplissez les tableaux suivants :

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 0 & 1& 2& 3& 4& 5& 6& 7& 8 & 9\\
\hline
PGCD(k,60) & 60 & 1 & 2 & 3 & 4 & 5 & 6 & 1 & 4 & 3\\
\hline
\end{array}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 10 & 11& 12& 13& 14& 15& 16& 17& 18 & 19\\
\hline
PGCD(k,60) & 10 & 1 & 12 & 1 & 2 & 15 & 4 & 1 & 6 & 1\\
\hline
\end{array}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 20 & 21& 22& 23& 24& 25& 26& 27& 28 & 29\\
\hline
PGCD(k,60) & 20 & 3 & 2 & 1 & 12 & 5 & 2 & 3 & 4 & 1\\
\hline
\end{array}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 30 & 31& 32& 33& 34& 35& 36& 37& 38 & 39\\
\hline
PGCD(k,60) & 30 & 1 & 4 & 3 & 2 & 5 & 12 & 1 & 2 & 3\\
\hline
\end{array}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 40 & 41& 42& 43& 44& 45& 46& 47& 48 & 49\\
\hline
PGCD(k,60) & 20 & 1 & 6 & 1 & 4 & 15 & 2 & 1 & 12 & 1\\
\hline
\end{array}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
k & 50 & 51& 52& 53& 54& 55& 56& 57& 58 & 59\\
\hline
PGCD(k,60) & 10 & 3 & 4 & 1 & 6 & 5 & 4 & 3 & 2 & 1\\
\hline
\end{array}

Lorsque $k$ décrit l’ensemble $\llbracket 0, 59\rrbracket$ vous constatez que $PGCD(k,60)$ décrit l’ensemble des diviseurs de $60.$

Vous allez classifier les entiers compris entre $0$ et $59$ selon la valeur que prend leur $PGCD$ avec $60.$

Introduisez une partition

A ce stade, il semblerait naturel de considérer, pour tout $d\in D$ l’ensemble suivant :

 \{k\in\llbracket0, 59\rrbracket, PGCD(k,60)=d\}.

En prenant $d = 60$ cet ensemble serait $\{k\in\llbracket0, 59\rrbracket, PGCD(k,60)=60\}$ et il ne contiendrait qu’un seul élément, or il serait souhaitable qu’il en contienne $\varphi(60).$

Du coup, il convient de considérer, pour tout $d\in D$ l’ensemble :

\Omega_d =  \{k\in\llbracket0, 59\rrbracket, PGCD(k,60)=60/d\}.

Cette définition permet de s’assurer que l’ensemble $\Omega_{60}$ contient exactement $\varphi(60)$ éléments.

Vous remarquez que la famille $(\Omega_d)_{d\in D}$ est une partition de l’ensemble $\llbracket 0, 59\rrbracket.$

En effet, vous avez :

\begin{align*}
\Omega_{1} &= \{0\} \\
\Omega_{2} &= \{30\} \\
\Omega_{3} &= \{20,40\} \\
\Omega_{4} &= \{15, 45\} \\
\Omega_{5} &= \{12, 24, 36, 48\} \\
\Omega_{6} &= \{10, 50\} \\
\Omega_{10} &= \{6, 18, 42, 54\} \\
\Omega_{12} &= \{5, 25, 35, 55\} \\
\Omega_{15} &= \{4, 8, 16, 28, 32, 44, 52, 56\} \\
\Omega_{20} &= \{3, 9, 21, 27, 33, 39, 51, 57 \} \\
\Omega_{30} &= \{2, 14, 22, 26, 34, 38, 46, 58\} \\
\Omega_{60} &= \{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59\} \\
\end{align*}

En évaluant la fonction $\varphi$ sur les diviseurs de $60$, vous obtenez le tableau suivant :

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
d & 1 & 2& 3& 4& 5& 6& 10& 12& 15 & 20 & 30 & 60\\
\hline
\varphi(d) & 1 & 1 & 2 & 2 & 4 & 2 & 4& 4 & 8 & 8 &8 & 16\\
\hline
\end{array}

Vous constatez alors que :

\forall d\in D, \Omega_d\text{ possède }\varphi(d)\text{ éléments.}

Il s’ensuit que :

\begin{align*}
60&=\sum_{d\in D} \text{nombre d'éléments de }\Omega_d \\
&= \sum_{d\in D}\varphi(d)\\
&= \sum_{d\mid 60}\varphi(d).
\end{align*} 

Traitez le cas général

Soit $n$ un entier naturel non nul fixé.

Introduisez les notations

Vous notez $D$ l’ensemble des diviseurs de $n$, défini par :

D = \{d\in\NN, d\mid n\}.

Enfin, pour tout $d\in D$ vous notez $\Omega_d$ l’ensemble suivant :

\Omega_d = \{k\in\llbracket 0, n-1\rrbracket, PGCD(k,n)=n/d\}.

Pour tout $d\in D$ déterminez le nombre d’éléments de l’ensemble $\Omega_d$

Soit $d\in D.$ Alors $\frac{n}{d}$ est un entier non nul.

Par définition, $\varphi(d)$ est le nombre d’éléments de l’ensemble :

A_d = \{k\in\llbracket0, d-1\rrbracket, PGCD(k,d)=1\}.

Vous considérez la fonction $f$ suivante qui va de $A_d$ dans $\Omega_d$, définie par :

\forall x\in A_d, f(x) = \frac{n}{d}x.

Montrez que $f$ est bien définie

Soit $x\in A_d.$ Alors $x$ est un entier compris entre $0$ et $d-1$ et $PGCD(x,d)=1.$ Comme $\frac{n}{d}$ est un entier naturel, il en est de même de $\frac{n}{d}x.$ Or, $x < d.$ Après multiplication par $\frac{n}{d}$ vous avez $\frac{n}{d}x < n$ donc $\frac{n}{d}x\in\llbracket 0, n-1\rrbracket.$

Le $PGCD$ étant multiplicatif, l’égalité $PGCD(x,d)=1$ fournit $PGCD\left(\frac{n}{d}x, n\right) = \frac{n}{d}$ après multiplication par $\frac{n}{d}.$ Ainsi, $f(x)\in \Omega_d$ et la fonction $f$ est bien définie.

Montrez que $f$ est bijective

Soient $x$ et $y$ deux éléments de $A_d$ tels que $f(x) = f(y)$, alors $\frac{n}{d}x = \frac{n}{d}y$ d’où $nx = ny$ après multiplication par $d$, puis $x=y$ après division par $n$ qui est non nul. Donc $f$ est injective.

Soit maintenant $y$ un élément de $\Omega_d.$ $y$ est un entier compris entre $0$ et $n-1$, de sorte que $PGCD(y,n) = \frac{n}{d}.$ Par définition du $PGCD$, l’entier $\frac{n}{d}$ divise $y$. En notant $q\in\N$ le quotient de la division de $y$ par $\frac{n}{d}$, vous avez $y = \frac{n}{d}q.$

Si $q\geq d$ alors $\frac{n}{d}q\geq n$ et $y\geq n$ ce qui est impossible, donc $q < d$ et par suite $q\in\llbracket 0, d-1\rrbracket.$

L’égalité $PGCD(y,n) = \frac{n}{d}$ fournit $PGCD\left( \frac{n}{d}q , n\right) = \frac{n}{d}$ qui devient $PGCD(nq, dn = n)$ après multiplication par $n.$ Or $PGCD(nq, dn) = nPGCD(q,d)$ donc $nPGCD(q,d) = n$ d’où $PGCD(q,d)=1$ après division par $n$ qui est non nul. Ainsi, $q\in A_d.$ Comme $y = \frac{n}{d}q$, vous avez $f(q) = y$ et la surjectivité de $f$ est démontrée.

La fonction $f$ étant à la fois injective et surjective, elle est bijective.

Concluez

Les ensembles $A_d$ et $\Omega_d$ étant en bijection, ils ont le même nombre d’éléments.

Pour tout $d\in D$ :

\boxed{\varphi(d) = \text{nombre d'élements de }\Omega_d.}

Démontrez que la famille $(\Omega_d)_{d\in D}$ est une partition de $\llbracket 0, n-1\rrbracket$

Sur l’égalité $\bigcup_{d\in D} \Omega_d = \llbracket 0, n-1\rrbracket$

Soit $d\in D$ par définition de $\Omega_d$ l’inclusion $\Omega_d\subset \llbracket 0, n-1\rrbracket$ est satisfaite.

Donc :

\bigcup_{d\in D} \Omega_d \subset  \llbracket 0, n-1\rrbracket.

Soit $k$ un élément de $\llbracket 0, n-1\rrbracket.$ Vous notez $d’ = PGCD(k,n).$ Par définition du $PGCD$, $d’ \mid n$ donc il existe un entier naturel $d$ tel que $n = dd’.$ Si $d=0$ alors $n=0$ ce qui est absurde, donc $d\in\NN$ et $d\mid n$ donc $d\in D.$ Comme $PGCD(k,n) = \frac{n}{d}$ il s’ensuit que $k\in \Omega_d.$

Ainsi :

\llbracket 0, n-1\rrbracket \subset \bigcup_{d\in D} \Omega_d.

Par double inclusion, vous avez obtenu :

\boxed{\bigcup_{d\in D} \Omega_d = \llbracket 0, n-1\rrbracket.}

L’union $\bigcup_{d\in D} \Omega_d$ est disjointe

Soient maintenant $d_1$ et $d_2$ deux éléments de $D$ tels que $\Omega_{d_1} \cap \Omega_{d_2} \neq \emptyset.$

Il existe $x\in \Omega_{d_1} \cap \Omega_{d_2}.$ Comme $x\in \Omega_{d_1}$ vous déduisez $PGCD(x,n) = \frac{n}{d_1}.$

Comme $x\in \Omega_{d_2}$, vous avez aussi $PGCD(x,n)=\frac{n}{d_2}.$

Vous déduisez :

PGCD(x,n)=\frac{n}{d_1}=\frac{n}{d_2}.

Du coup, il vient $d_1 = d_2.$

Par contraposée, il a été prouvé ce qui suit :

\boxed{\forall (d_1,d_2)\in D^2, \quad d_1\neq d_2\implies \Omega_{d_1}\cap\Omega_{d_2} = \emptyset.}

Démontrez la relation annoncée dans le cas général

La famille $(\Omega_d)_{d\in D}$ est une partition de l’ensemble $\llbracket 0, n-1\rrbracket$ qui possède $n$ éléments.

Par somme, il vient :

 \begin{align*}
n&=\sum_{d\in D} \text{nombre d'éléments de }\Omega_d \\
&= \sum_{d\in D}\varphi(d).
\end{align*} 

Concluez

La propriété suivante a été démontrée :

\boxed{\forall n\in\NN, \quad n = \sum_{d\mid n}\varphi(d).}