= Möbius inversion formula
{c}
{title2=$g=f*\mathbf1\iff f=\mu*g$}
{wiki}
= Möbius inversion
{c}
{synonym}
<Möbius inversion> recovers an <arithmetic function> from its <divisor sum>. For <arithmetic functions> $f,g$, the following statements are equivalent, with each equality required for every <positive integer> $n$:
$$
g(n)=\sum_{d\mid n}f(d)
\quad\Longleftrightarrow\quad
f(n)=\sum_{d\mid n}\mu(d)g(n/d).
$$
Here $d$ ranges over positive <integer divisors> of $n$ and $\mu$ is the <Möbius function>. No <multiplicativity> assumption is needed, and both sums are finite. The right side can also be written $\sum_{d\mid n}\mu(n/d)g(d)$ by exchanging complementary <integer divisors>. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781 lecture notes, Theorem 2.5.1 and Proposition 2.5.2]{ref}
The <divisor sum> $g(n)$ bundles $f(n)$ together with values at smaller <integer divisors>. <Möbius inversion> subtracts aggregates indexed by one distinct <prime factor>, adds those indexed by two, and continues with the alternating signs of <inclusion-exclusion>. A <divisor> containing a squared <prime factor> receives weight zero. The <Möbius divisor-sum identity> ensures that every unwanted contribution cancels exactly.
In <Dirichlet convolution> notation, $g=f*\mathbf1$ and $\mu*\mathbf1=\varepsilon$, where $\mathbf1$ is the <constant-one arithmetic function> and $\varepsilon$ is the <Identity for Dirichlet convolution>. <Associativity> and <commutativity> give the short proof:
$$
\mu*g=\mu*(\mathbf1*f)=(\mu*\mathbf1)*f=\varepsilon*f=f.
$$
Convolving $f=\mu*g$ with $\mathbf1$ proves the reverse implication. At $n=1$, the formula reduces to $f(1)=g(1)$ because $\mu(1)=1$.
For a worked example, take $f(n)=\varphi(n)$, <Euler's totient function>. The <totient divisor-sum identity> says that $g(n)=n$, the <identity arithmetic function>:
$$
g(12)=\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)
=1+1+2+2+2+4=12.
$$
This identity comes from classifying the <integers> $1,\ldots,n$ by their <greatest common divisor> with $n$: the group with $\gcd(j,n)=h$ has $\varphi(n/h)$ members, since $j/h$ and $n/h$ are <coprime integers>. Summing the group sizes gives $n$, as detailed under <totient divisor-sum identity>.
Now undo this aggregation with the <Möbius function>:
$$
\begin{aligned}
\varphi(12)&=\mu(1)12+\mu(2)6+\mu(3)4+\mu(4)3+\mu(6)2+\mu(12)1\\
&=12-6-4+0+2+0=4.
\end{aligned}
$$
The nonzero terms use $d=1,2,3,6$; $d=4,12$ vanish because they contain the square of the <prime number> $2$. The four surviving <integers> <coprime> to $12$ are $1,5,7,11$.
\Image[/mobius-inversion-totient.png]
{title=A <divisor sum> aggregates <Euler's totient function> values to 12, while <Möbius inversion> recovers the four <integers> <coprime> to 12}
This example also reveals why <Möbius inversion> is useful: it turns an easy count of all objects into a count satisfying a <coprimality> restriction. Expanding over <subsets> of distinct <prime factors> gives
$$
\varphi(n)=\sum_{d\mid n}\mu(d)\frac nd
=n\prod_{p\mid n}\left(1-\frac1p\right).
$$
The product is <inclusion-exclusion> over multiples of the <prime factors>. For $12$, it gives $12(1-1/2)(1-1/3)=4$. More generally, whenever a counting problem produces a <divisor sum>, <Möbius inversion> lets that aggregate be reversed without solving a new system of <equations>.
Back to article page
