École AVOSZ

Connectez-vous

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

Yannis TRIANTAPHYLIDES

, ,

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 ce contenu 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\comma$ $3$ et $5$ étant donné que :

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

L’entier $4 = 2^2$ possède trois diviseurs, $1\comma$ $2$ et $4.$

L’entier $3$ possède deux diviseurs, $1$ et $3.$

L’entier $5$ possède deux diviseurs, $1$ et $5.$

En 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\comma$ à savoir :

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

Pour tous les entiers compris entre $0$ et $59\comma$ 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 classer les entiers compris entre $0$ et $59$ selon la valeur que prend leur $\pgcd$ avec $60.$

Introduisez une partition

À 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\comma$ 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\comma$ 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 naturel non nul et $n = \frac{n}{d}\times d.$

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\comma$ 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 \lt d.$ Après multiplication par $\frac{n}{d}$ vous avez $\frac{n}{d}x \lt n$ donc $\frac{n}{d}x\in\llbracket 0, n-1\rrbracket.$

Pour tout entier naturel non nul $c$ et pour tous entiers $u$ et $v\comma$ vous avez $\pgcd(cu, cv) = c\,\pgcd(u,v).$ Avec $c = \frac{n}{d}\comma$ $u=x$ et $v=d\comma$ l’égalité $\pgcd(x,d)=1$ fournit $\pgcd\left(\frac{n}{d}x, n\right) = \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)\comma$ alors $\frac{n}{d}x = \frac{n}{d}y$ d’où $nx = ny$ après multiplication par $d\comma$ 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.$ L’entier $y$ est compris entre $0$ et $n-1\comma$ et $\pgcd(y,n) = \frac{n}{d}.$ Par définition du $\pgcd\comma$ l’entier $\frac{n}{d}$ divise $y$. En notant $q\in\N$ le quotient de la division exacte de $y$ par $\frac{n}{d}\comma$ 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 \lt 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 $d.$ Or $\pgcd(nq, dn) = n\,\pgcd(q,d)$ donc $n\,\pgcd(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\comma$ 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\comma$ vous avez :

\boxed{\varphi(d) = \text{nombre d'éléments 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\comma$ $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}\comma$ 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)\\ &= \sum_{d\mid n}\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).}