Möbius Inversion Formula

The Möbius inversion formula is one of the most powerful tools in elementary number theory, allowing us to invert summatory relations over divisors.

DefinitionMöbius Function

The Möbius function $\mu: \mathbb{N} \to \{-1, 0, 1\}$ is defined as:

\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^k & \text{if } n = p_1 p_2 \cdots p_k \text{ (distinct primes)} \\ 0 & \text{if } n \text{ has a squared prime factor} \end{cases}

TheoremMöbius Inversion Formula

Let $f$ and $g$ be arithmetic functions. Then:

g(n) = \sum_{d|n} f(d) \quad \text{for all } n \geq 1

if and only if:

f(n) = \sum_{d|n} \mu(n/d) g(d) = \sum_{d|n} \mu(d) g(n/d)

In terms of Dirichlet convolution: $g = f * 1$ if and only if $f = g * \mu$ .

ExampleEuler's Totient Function

Since $\sum_{d|n} \varphi(d) = n$ , Möbius inversion gives:

\varphi(n) = \sum_{d|n} \mu(n/d) \cdot d = n \sum_{d|n} \frac{\mu(d)}{d}

For $n = p_1^{a_1} \cdots p_r^{a_r}$ , this becomes:

\varphi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right)

ExampleCounting Primitive Roots

Let $f(n)$ count ordered pairs $(a,b)$ with $\gcd(a,b) = 1$ and $a, b \leq n$ . Then $f(n) = \sum_{d|n} \varphi(d)^2$ .

By Möbius inversion:

\varphi(n)^2 = \sum_{d|n} \mu(n/d) f(d)

Remark

The Möbius function satisfies the fundamental identity:

\sum_{d|n} \mu(d) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n > 1 \end{cases}

This is equivalent to $\mu * 1 = \delta$ , showing $\mu$ is the inverse of the constant function under Dirichlet convolution.

The Möbius inversion formula has numerous applications beyond number theory, appearing in combinatorics (inclusion-exclusion), lattice theory, and algebraic topology. It exemplifies how algebraic structure (the convolution ring of arithmetic functions) leads to concrete computational tools.