La formule d’inversion est un résultat de la théorie des nombres qui concerne les fonctions arithmétiques (fonctions définies sur les entiers positifs). Elle repose sur une fonction clé : la fonction de Möbius, notée $\mu(n)$.
La fonction $\mu(n)$ est définie pour tout entier $n \ge 1$ par :
- $\mu(1) = 1$.
- $\mu(n) = (-1)^k$ si $n$ est le produit de $k$ nombres premiers distincts (on dit que $n$ est « sans facteur carré »).
- $\mu(n) = 0$ si $n$ a un facteur premier au carré (par exemple, $\mu(4)=0$, $\mu(12)=0$).
Cette fonction a une propriété fondamentale : la somme de $\mu(d)$ sur tous les diviseurs $d$ d’un entier $n$ est presque toujours nulle. $$ \sum_{d|n} \mu(d) = \begin{cases} 1 & \text{si } n = 1 \\ 0 & \text{si } n > 1 \end{cases} $$
Soient $f$ et $g$ deux fonctions arithmétiques.
Si $g$ est définie à partir de $f$ par la somme sur les diviseurs : $$ g(n) = \sum_{d|n} f(d) $$ Alors on peut « inverser » la relation pour retrouver $f$ à partir de $g$ en utilisant la fonction de Möbius : $$ f(n) = \sum_{d|n} \mu(d) g\left(\frac{n}{d}\right) $$
Idée de la Démonstration
La démonstration est un calcul élégant qui consiste à substituer l’expression de $g$ dans la formule d’inversion et à manipuler les sommes.
- On part de la formule à prouver : $\sum_{d|n} \mu(d) g(n/d)$.
- On remplace $g(n/d)$ par sa définition : $g(n/d) = \sum_{k|(n/d)} f(k)$. $$ \sum_{d|n} \mu(d) \left( \sum_{k|(n/d)} f(k) \right) $$
- La condition $d|n$ et $k|(n/d)$ est équivalente à $k|n$ et $d|(n/k)$. On peut donc intervertir l’ordre des sommations : $$ \sum_{k|n} f(k) \left( \sum_{d|(n/k)} \mu(d) \right) $$
- On utilise la propriété fondamentale de la fonction de Möbius : la somme intérieure $\sum_{d|(n/k)} \mu(d)$ vaut 1 si $n/k = 1$ (c’est-à-dire $n=k$), et 0 sinon.
- Ainsi, tous les termes de la somme sur $k$ sont nuls, sauf celui pour lequel $k=n$. La somme se réduit donc à un seul terme : $f(n) \cdot 1 = f(n)$.
Application Classique : L’indicateur d’Euler
- L’indicateur d’Euler, $\phi(n)$, compte le nombre d’entiers inférieurs à $n$ et premiers avec $n$. Une identité classique (prouvée par Gauss) est : $$ n = \sum_{d|n} \phi(d) $$
- Cette formule est exactement de la forme $g(n) = \sum_{d|n} f(d)$, avec $g(n)=n$ et $f(d)=\phi(d)$.
- En appliquant la formule d’inversion de Möbius, on obtient directement une formule explicite pour calculer $\phi(n)$ : $$ \phi(n) = \sum_{d|n} \mu(d) \frac{n}{d} = n \sum_{d|n} \frac{\mu(d)}{d} $$