Mobius Inversion

We can generalize our earlier Theorem 8 as follows.

Definition 9   Let $f$ and $g$ be functions defined on the positive integers. Define $F=g*f$ by the formula

$$F(n)=\sum_{d\vert n} f(d)g(n/d)$$

Theorem 10   Suppose that $f$ and $g$ are multiplicative functions. Then the function $F=g*f$ is also multiplicative.

Remark 1   The * operation is associative (F*(G*H)=(F*G)*H) and commutative (F*G=G*F).

Define the Mobius function to be the unique multiplicative function such that $\mu(p^{k})=1$ if $k=0$, $-1$ if $k=1$, and $0$ if $k>1$.

Theorem 11 (Mobius Inversion)   Let $e$ be the function that is one on every number. Then for any functions $F$ and $G$ defined on the positive integers, $F*e=G$ if and only if $G*\mu=F$.

Notice that $F$ and $G$ don't have to be multiplicative for this to be true.

For example:

$$\sum_{d\vert n}\mu(d)=1.$$

$$\sum_{d\vert n} d\mu(n/d)=\phi(n).$$

An example of the latter formula: n=12.

$d$	$12/d$	$\mu(12/d)$	$d\mu(12/d)$
1	12	0	0
2	6	1	2
3	4	0	0
4	3	-1	-4
6	2	-1	-6
12	1	1	12

Adding up the last column we get 12-10+2=4 as we should