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 !