Votre navigateur n'accepte pas le Javascript.La navigation sur ce site risque de ne pas fonctionner correctement.

351. La somme des valeurs de l’indicatrice d’Euler prise sur tous les diviseurs d’un entier naturel n non nul est égale à n

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).}

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.

Aidez-moi sur Facebook !

Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Lisez d'autres articles !

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !