MöbiusInversionsformel

The Möbius inversion formula is a fundamental result in number theory that relates a function to its sum over divisors. Specifically, if we have an arithmetic function $f(n)$ and define another function $g(n)$ as the sum of $f(d)$ over all positive divisors $d$ of $n$, then $g(n) = \sum_{d|n} f(d)$. The Möbius inversion formula states that if this relationship holds, then $f(n)$ can be recovered from $g(n)$ using the Möbius function $\mu(n)$ as follows: $f(n) = \sum_{d|n} \mu(d)g(d/n)$.

The Möbius function $\mu(n)$ is defined for positive integers $n$. It is equal to 1 if $n$ is a square-free positive integer with an even number of prime factors. It is equal to -1 if $n$ is a square-free positive integer with an odd number of prime factors. It is equal to 0 if $n$ has a squared prime factor.

This formula is particularly useful for inverting sums involving multiplicative functions. For example, it can be used to derive properties of the Euler totient function $\phi(n)$, which counts the number of positive integers less than or equal to $n$ that are relatively prime to $n$. The sum of $\phi(d)$ over all divisors $d$ of $n$ is equal to $n$. Using the Möbius inversion formula, one can then express $\phi(n)$ in terms of $n$ and the Möbius function. The formula has applications in various areas of mathematics, including combinatorics, graph theory, and theoretical computer science.