## Möbius Inversion

Suppose for some (not necessarily multiplicative) number-theoretic function $f$

$F(n) = \sum_{d|n} f(d) .$

Can we make $f(n)$ the subject of this equation?

We’ll see that we can find a function $\mu$ such that

$f(n) = \sum_{d|n} \mu(n/d) F(d) = \sum_{d|n} \mu(d) F(n/d) .$

and we call this process Möbius inversion. Note we have

$\array { \sum_{d|n} \mu(d) F(n/d) &=& \sum_{d|n}\mu(d) \sum_{r|\frac{n}{d}} f(r) \\ &=& \sum_{d r |n} \mu(d)f(r) \\ &=& \sum_{r |n} f(r) \sum_{d|(n/r)} \mu(d) }$

If we want this equal to $f(n)$ we need $\mu$ to satisfy

$\sum_{d|m}\mu(d) = \begin{cases} 0, & m \gt 1 \\ 1, & m = 1 \end{cases}$

A little thought leads to this unique solution, known as the Möbius function:

$\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & p^2 | n \textrm{ for some prime }p \\ (-1)^r & n = p_1...p_r \textrm{ for distinct primes }p_i \end{cases}$

Notice $\mu$ is multiplicative, which implies $f(n)$ is multiplicative if $F(n)$ is. In summary,

Theorem:

$F(n) = \sum_{d|n} f(d)$

if and only if

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

and $f(n)$ is multiplicative if and only if $F(n)$ is multiplicative.

Example: From before $n = \sum_{d|n} \phi(n)$. Write $n = p_1^{k_1}...p_m^{k_m}$. Then

$\array { \phi(n) &=& \sum_{d|n} \mu(d) \frac{n}{d} \\ &=& n \sum_{d|n} \mu(d) \frac{1}{d} \\ &=& n \left(1 - \sum_i \frac{1}{p_i} + \sum_{i\ne j} \frac{1}{p_i p_j} - ...\right) \\ &=& n \left(1 - \frac{1}{p_1}\right)...\left(1 - \frac{1}{p_m}\right) }$

which is another way to derive the formula for $\phi$.

Gauss encountered the Möbius function over 30 years before Möbius when he showed that the sum of the generators of $\mathbb{Z}_p^*$ is $\mu(p-1)$. More generally, if $\mathbb{Z}_n^*$ has a generator, then the sum of all the generators of $\mathbb{Z}_n^*$ is $\mu(\phi(n))$. This can be seen by considering the sums of the roots of polynomials of the form $x^d - 1$ where $d | \phi(n)$.