Section 6.6 Möbius Inversion
Theorem 6.6.1. Möbius Inversion.
Let \(f\) and \(F\) be arithmetic functions such that
\begin{equation*}
F(n) = \sum_{d\vert n}f(d).
\end{equation*}
Then
\begin{equation*}
f(n)=\sum_{d\vert n}\mu(d)F\left(\frac{n}{d}\right)=\sum_{d\vert n}\mu\left(\frac{n}{d}\right)F(d).
\end{equation*}
Proof.
This is proof by computation. We see that
\begin{equation*}
\sum_{d\vert n}\mu(d)F\left(\frac{n}{d}\right)=\sum_{d\vert n}\left(\mu(d)\sum_{c\vert (n/d)}f(c)\right)=\sum_{d\vert n}\left(\sum_{c\vert (n/d)}\mu(d) f(c)\right).
\end{equation*}
Now \(d\vert n\) and \(c\vert (n/d)\) provided there exist \(k, l\in\mathbb{N}\) such that \(n = kd\) and \((n/d) = cl.\) But the \((n/d) = cl\) if and only if \(n = d(cl)\) so that \(c\vert n\) and \(d\vert (n/c).\) Now our equality continues to give
\begin{equation*}
\sum_{d\vert n}\left(\sum_{c\vert (n/d)}\mu(d) f(c)\right)=\sum_{c\vert n}\left(\sum_{d\vert (n/c)} f(c)\mu(d)\right)=\sum_{c\vert n}\left(f(c)\sum_{d\vert (n/c)} \mu(d)\right).
\end{equation*}
Due to the previous theorem, we know that \(\sum_{d\vert (n/c)}\mu(d)=0\) except when \(n/c = 1;\) that is, when \(n = c,\) so again continuing, we have
\begin{equation*}
\sum_{c\vert n}\left(f(c)\sum_{d\vert (n/c)} \mu(d)\right)=\sum_{c= n}f(c)\cdot 1=f(n),
\end{equation*}
so that \(f(n) = \sum_{d\vert n}\mu(d)F\left(\frac{n}{d}\right).\)
Example 6.6.2.
Recall that
\begin{equation*}
d(n) =\sum_{d\vert n} 1 \hspace{5mm} \mathrm{and} \hspace{5mm} \sigma(n)=\sum_{d\vert n} d.
\end{equation*}
Using the Möbius Inversion formula we have that
\begin{equation*}
1 =\sum_{c\vert n} \mu\left(\frac{n}{c}\right)d(c) \hspace{5mm} \mathrm{and} \hspace{5mm} n=\sum_{d\vert n} \mu\left(\frac{n}{d}\right)\sigma(d).
\end{equation*}
Section 6.6.1 Application of Möbius Inversion
Theorem 6.6.1.
If \(F\) is a multiplicative function and
\begin{equation*}
F(n) =\sum_{d\vert n}f(d),
\end{equation*}
then \(f\) is multiplicative.
Proof.
(We use the same lemma as for the converse.) Let \(m, n \in\mathbb{N}\) with \(\gcd(m, n) = 1.\) Using Möbius inversion, we have
\begin{align*}
f(mn) \amp =\sum_{d\vert mn} \mu(d)F\left(\frac{mn}{d}\right)\\
\amp =\sum_{\substack{d_1\vert m \\ d_2\vert n}} \mu(d_1d_2)F\left(\frac{mn}{d_1d_2}\right) \hspace{5mm} (\gcd(d_1,d_2)=1)\\
\amp =\sum_{\substack{d_1\vert m \\ d_2\vert n}} \mu(d_1)\mu(d_2)F\left(\frac{m}{d_1}\right)F\left(\frac{n}{d_2}\right)\\
\amp =\sum_{d_1\vert m} \mu(d_1)\mu(d_2)F\left(\frac{m}{d_1}\right)\sum_{d_2\vert n}F\left(\frac{n}{d_2}\right)\\
\amp =f(m)f(n),
\end{align*}
which is the desired result.