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

$$F(n)=\sum _{d\mid 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\mid n}\mu (n/d)F(d)=\sum _{d\mid n}\mu (d)F(n/d).$$

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

$$\begin{array}{ccc}\sum _{d\mid n}\mu (d)F(n/d)& =& \sum _{d\mid n}\mu (d)\sum _{r\mid \frac{n}{d}}f(r)\\ & =& \sum _{dr\mid n}\mu (d)f(r)\\ & =& \sum _{r\mid n}f(r)\sum _{d\mid (n/r)}\mu (d)\end{array}$$

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

$$\sum _{d\mid m}\mu (d)=\{\begin{array}{ll}0,& m>1\\ 1,& m=1\end{array}$$

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

$$\mu (n)=\{\begin{array}{ll}1& n=1\\ 0& p^2\mid n\text{ for some prime }p\\ (-1{)}^r& n=p_1...p_r\text{ for distinct primes }{p}_i\end{array}$$

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

Theorem:

$$F(n)=\sum _{d\mid n}f(d)$$

if and only if

$$f(n)=\sum _{d\mid 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\mid n}\varphi (n)$. Write $n=p_1^{k_1}...p_m^{k_m}$. Then

$$\begin{array}{ccc}\varphi (n)& =& \sum _{d\mid n}\mu (d)\frac{n}{d}\\ & =& n\sum _{d\mid n}\mu (d)\frac{1}{d}\\ & =& n(1-\sum _i\frac{1}{p_i}+\sum _{i\ne j}\frac{1}{p_i{p}_j}-...)\\ & =& n(1-\frac{1}{p_1})...(1-\frac{1}{p_m})\end{array}$$

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

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 (\varphi (n))$. This can be seen by considering the sums of the roots of polynomials of the form $x^d-1$ where $d\mid \varphi (n)$.