Mobius Inversion

Suppose you know, for every positive integer $n$ , the sum of a mystery function $f$ over all divisors of $n$ . Can you recover $f$ itself? This is not idle curiosity. Euler's totient function $\varphi$ , the divisor-counting function $d$ , and the sum-of-divisors function $\sigma$ are all easiest to define through such divisor sums. Yet number theorists constantly need to invert the relationship. They need to strip away the summation and isolate the original function. Möbius inversion answers this question completely and explicitly. It uses nothing more than the arithmetic properties of the Mobius Function $\mu$ . The idea matters because it converts a huge class of "summed" identities into "unsummed" identities and back. It does this essentially for free. Once you know that $g(n) = \sum_{d\mid n} f(d)$ , Möbius inversion hands you $f(n) = \sum_{d \mid n} \mu(n/d) g(d)$ with no further work. This single formula unifies dozens of classical identities in elementary number theory. These include the totient sum, the identity $\sum_{d\mid n}\mu(d)=[n=1]$ , and formulas for counting irreducible polynomials over finite fields. It also includes formulas in combinatorics (inclusion–exclusion on the divisor lattice). All of these fall under one algebraic umbrella. The big picture is that Möbius inversion is really a statement about invertibility. This invertibility lives in the Ring of Arithmetic Functions under Dirichlet Convolution. The divisor sum $g = f * \mathbf{1}$ is a convolution with the constant function $\mathbf{1}(n) = 1$ . And $\mu$ is precisely the Dirichlet inverse of $\mathbf{1}$ . Once this is understood, Möbius inversion is not a clever trick. It is an immediate consequence of associativity in a ring. This is the same mechanism that lets you cancel a nonzero real number by multiplying by its reciprocal. This article gives the precise formal statement. It includes a fully rigorous proof from first principles. A second proof via the convolution ring is also given, to show both viewpoints. There are two worked examples with genuinely different flavors. A counterexample shows why the divisor-sum hypothesis cannot be weakened. Finally, there is a survey of where this circle of ideas resurfaces. It resurfaces from cryptography to combinatorics to the analytic study of average orders.

Key takeaways

Möbius inversion recovers $f$ from $g(n) = \sum_{d\mid n} f(d)$ via $f(n) = \sum_{d\mid n} \mu(n/d)g(d)$ .
It rests on one identity: $\sum_{d \mid n} \mu(d) = [n=1]$ (the Iverson bracket).
Equivalently, $\mu$ is the Dirichlet convolution inverse of the constant function $\mathbf{1}$ .
Classical payoffs: $\varphi(n) = \sum_{d\mid n} \mu(d)\, n/d$ , and inversion of $d(n)$ , $\sigma(n)$ identities.
The formula is a two-way street: it converts unsummed formulas into summed ones just as easily.
Key idea: inversion is convolution by an inverse element, so it works whenever $\mathbf{1}$ has an inverse — which it always does.

Where this lives today

Möbius inversion is a load-bearing tool well beyond its origin. In analytic number theory it underlies the study of average orders of arithmetic functions such as $\varphi$ , $d$ , and $\sigma$ , since inverting a divisor-sum relation is often the first step in extracting asymptotics — a theme picked up directly in the study of Average Order of Arithmetic Functions. In algebra and combinatorics, the same cancellation phenomenon generalizes to the Möbius function of an arbitrary locally finite partially ordered set (Rota's theory of Möbius functions on posets), with the divisor lattice as the motivating special case; this recovers inclusion–exclusion on finite sets as another instance of the same abstract machinery. In finite fields and coding theory, as in the worked example above, Möbius inversion gives exact formulas for the number of irreducible polynomials of each degree, which feeds directly into constructions of finite fields used in error-correcting codes and in cryptographic primitives built over $\mathbb{F}_{2^n}$ . In cryptography more broadly, cyclotomic polynomials — defined via a Möbius-inverted product formula over divisors of $n$ — appear in the design of discrete-log-based systems and in analyzing the structure of multiplicative groups modulo primes. In combinatorics on necklaces and dynamical systems, Möbius inversion counts the number of aperiodic binary necklaces of a given length, connecting directly to counting periodic points of the shift map and to de Bruijn sequences. Even in statistical mechanics, cluster-expansion techniques for computing free energies use Möbius-type inversions on lattices of subsets, echoing the same alternating-sign cancellation seen in the Lemma above.

Ask the tutor: How does Möbius inversion generalize to the Möbius function of an arbitrary partially ordered set, and how does that recover ordinary inclusion–exclusion as a special case?

\mu : \mathbb{Z}_{>0} \to \{-1,0,1\}

Intuition

Think of the divisors of $n$ as forming a small partially ordered set under divisibility — a lattice. The equation $g(n) = \sum_{d\mid n} f(d)$ says that $g$ at $n$ "collects" all the values of $f$ sitting below $n$ in this lattice. This is exactly the same shape as inclusion–exclusion: if $g$ counts something cumulative over a family of nested sets, $f$ is the "new content added at level $d$ ," and recovering $f$ from $g$ should involve alternating sums, since inclusion–exclusion always does. The Möbius function is engineered to be the correct alternating-sign machine for the divisor lattice. Its defining property, $\sum_{d\mid n}\mu(d) = [n=1]$ , says that if you sum $\mu$ over the divisors of $n>1$ , the positive and negative contributions from square-free divisors with even versus odd numbers of prime factors cancel exactly. This is inclusion–exclusion over the set of prime divisors of $n$ : squarefree divisors correspond to subsets of primes, and $\mu$ assigns $(-1)^{|S|}$ to the subset $S$ . The picture below shows the divisor lattice of $n = 12$ with $\mu$ -values labeled on each divisor, illustrating both facts used in the proof: which divisors are squarefree (nonzero $\mu$ ) and how the alternating signs cancel.

Figure

Divisor lattice of 12 with Möbius values, illustrating cancellation

The two-way bridge

The intuition to keep is that Möbius inversion is a change of coordinates: it re-expresses the same information (the function $f$ ) using a different, more convenient generating rule (partial sums over divisors instead of raw values). Once you see $\mu$ as the multiplicative inverse of the all-ones function under Dirichlet convolution, the inversion formula stops looking like magic and starts looking like solving $g = f\cdot 1$ for $f$ by multiplying both sides by $1^{-1}$ .

f, g : \mathbb{Z}_{>0} \to \mathbb{C}

\mu

n=1

\Rightarrow

\mathbf{1}

(f*g)(n) = \sum_{d\mid n} f(d)\,g(n/d)

Worked examples

Example 1: Recovering $\varphi$ from the identity $\sum_{d\mid n} \varphi(d) = n$ . It is a standard fact (provable directly by partitioning $\{1,\dots,n\}$ according to $\gcd$ with $n$ ) that Euler's totient function satisfies

n = \sum_{d \mid n} \varphi(d) \qquad \text{for every } n \ge 1.

This says $g(n) = n$ is the divisor sum of $f = \varphi$ . By Möbius inversion,

\varphi(n) = \sum_{d \mid n} \mu\!\left(\frac{n}{d}\right) d.

Let us verify this concretely for the asymmetric case $n = 60 = 2^2\cdot 3\cdot 5$ , whose divisors are

1,2,3,4,5,6,10,12,15,20,30,60.

We need $\mu(60/d)$ for each divisor $d$ :

$d$	$60/d$	$\mu(60/d)$	contribution $\mu(60/d)\cdot d$
1	60	$\mu(60)=0$ ( $4\mid 60$ )	0
2	30	$\mu(30)=\mu(2\cdot3\cdot5)=-1$	$-2$
3	20	$\mu(20)=0$ ( $4\mid 20$ )	0
4	15	$\mu(15)=\mu(3\cdot5)=1$	$4$
5	12	$\mu(12)=0$ ( $4\mid 12$ )	0
6	10	$\mu(10)=\mu(2\cdot5)=1$	$6$
10	6	$\mu(6)=\mu(2\cdot3)=1$	$10$
12	5	$\mu(5)=-1$	$-12$
15	4	$\mu(4)=0$	0
20	3	$\mu(3)=-1$	$-20$
30	2	$\mu(2)=-1$	$-30$
60	1	$\mu(1)=1$	$60$

Summing the contributions:

0 -2+0+4+0+6+10-12+0-20-30+60 = 16.

Independently, the standard formula $\varphi(n) = n\prod_{p\mid n}(1 - 1/p)$ gives

\varphi(60) = 60 \cdot \left(1-\tfrac12\right)\left(1-\tfrac13\right)\left(1-\tfrac15\right) = 60\cdot\frac12\cdot\frac23\cdot\frac45 = 16.

The two computations agree, confirming both the inversion formula and the arithmetic.

Example 2: Counting monic irreducible polynomials over $\mathbb{F}_2$ . Over the finite field $\mathbb{F}_2$ , every monic polynomial of degree $n$ factors uniquely into monic irreducibles, and comparing degrees on both sides of $X^{2^n} - X = \prod (\text{irreducibles of degree } d,\ d\mid n)$ yields the identity (a standard fact from finite field theory, taken here as given)

2^n = \sum_{d \mid n} d \cdot I(d),

where $I(d)$ denotes the number of monic irreducible polynomials of degree $d$ over $\mathbb{F}_2$ . Setting $f(d) = d\cdot I(d)$ and $g(n) = 2^n$ , this is exactly a divisor-sum relation $g(n) = \sum_{d\mid n} f(d)$ , so Möbius inversion gives

n \cdot I(n) = \sum_{d \mid n} \mu\!\left(\frac{n}{d}\right) 2^{d}, \qquad I(n) = \frac{1}{n}\sum_{d\mid n} \mu\!\left(\frac{n}{d}\right) 2^d.

Let us compute $I(6)$ , an asymmetric case with two distinct prime factors in the exponent. Divisors of $6$ are $1,2,3,6$ .

$d$	$6/d$	$\mu(6/d)$	$2^d$	product
1	6	$\mu(6)=1$	2	2
2	3	$\mu(3)=-1$	4	$-4$
3	2	$\mu(2)=-1$	8	$-8$
6	1	$\mu(1)=1$	64	64

Sum: $2 - 4 - 8 + 64 = 54$ . Then

I(6) = \frac{54}{6} = 9.

So there are exactly $9$ monic irreducible polynomials of degree $6$ over $\mathbb{F}_2$ . As a sanity check via the recursive structure: $I(1)=2$ (namely $X, X+1$ ), $I(2) = (2^2-2)/2 = 1$ , $I(3) = (2^3-2)/3=2$ , and the degree-6 count should satisfy $6\cdot 9 + 3\cdot 2 + 2\cdot1 + 1\cdot 2 = 54 + 6 + 2 + 2 = 64 = 2^6$ , which checks out exactly against the original (non-inverted) identity for $n=6$ .

n

Scope, edge cases & common traps

Situation	What happens
$g(n) = \sum_{d\mid n} f(d)$ known for all $n$	Inversion recovers $f$ exactly and uniquely, by the Theorem.
Relation known only for finitely many $n$ , or only $n$ in a proper sub-semigroup	Inversion formula does not apply; $f$ is underdetermined, as the counterexample shows.
$f,g$ complex-valued, not just real or integer	No change — the proof never uses positivity, integrality, or any ordering; only finite-sum algebra.
Multiplicativity of $f$	Not required for inversion to hold, but if $g$ is multiplicative and $f$ 's divisor sum equals $g$ , then $f$ is automatically multiplicative too (a separate, provable fact about Dirichlet convolution of multiplicative functions).
Using $\sum_{d\mid n}$ vs. $\sum_{d\le n}$	These are different operations entirely; Möbius inversion as stated concerns only the divisor sum, not partial sums over an interval (a related but distinct "Möbius summation" exists via $\sum_{d\le x}\mu(d)\lfloor x/d\rfloor$ type identities, not covered by this theorem).

The mathematician behind it

Origins · 1 minAugust Ferdinand Möbius and how this was discovered

August Ferdinand Möbius

1790–1868 · German mathematician and astronomer, University of Leipzig

Möbius worked across geometry, astronomy, and number theory, and is best remembered publicly for the one-sided surface that bears his name. In number theory, he introduced the function $\mu$ and the inversion formula in an 1832 paper, motivated by problems in combinatorial counting that he had encountered while studying the structure of finite groups of permutations of divisors — an early instance of the inclusion–exclusion idea being made fully algebraic.

History

- 1790 — August Ferdinand Möbius born in Schulpforta, Saxony.

- 1815 — Becomes an astronomer and later professor at Leipzig, working under Gauss's influence in Göttingen.

- 1832 — Publishes "Über eine besondere Art von Umkehrung der Reihen," introducing

\mu

and the inversion formula.

- 1858 — Discovers the one-sided surface later named the Möbius strip (independently of Listing).

- 1868 — Dies in Leipzig; his number-theoretic function becomes foundational to 20th-century analytic number theory.

f

and

g

need to be multiplicative for Möbius inversion to apply?

No. The Theorem as proved makes no assumption of multiplicativity, complete multiplicativity, or even non-negativity of $f$ or $g$ ; the argument is a purely combinatorial rearrangement of finite sums over divisors, valid for arbitrary complex-valued arithmetic functions. Multiplicativity becomes relevant only as a bonus: if $g$ happens to be multiplicative, one can show separately (using properties of Dirichlet convolution of multiplicative functions) that the resulting $f$ is automatically multiplicative as well, which is often a useful sanity check but never a hypothesis of the inversion theorem itself.

Is there a version of Möbius inversion for sums over an interval

1,\dots,n

instead of divisors of

n

Yes, and it is a genuinely different (though related) tool sometimes called "Möbius summation" or used in proving $\sum_{n\le x}\mu(n)/n \to 0$ -type results; it involves double sums of the form $\sum_{d\le x}\mu(d)h(x/d)$ and connects to the Average Order of Arithmetic Functions. It is not the same statement as the divisor-sum inversion proved here, and applying the divisor-sum formula to an interval sum is a common source of error — the index sets ("divisors of $n$ " versus "integers up to $x$ ") are structurally different.

Why does

\mu(n)=0

whenever

n

has a squared prime factor?

This is a definitional choice, but it is exactly the choice needed to make the fundamental Lemma true. If $\mu$ were instead defined only on squarefree numbers by $(-1)^{(\text{number of prime factors})}$ and left undefined (or nonzero) on non-squarefree numbers, the identity $\sum_{d\mid n}\mu(d) = [n=1]$ would fail for numbers like $n=4$ , since $4$ 's divisors $1,2,4$ would then contribute $\mu(1)+\mu(2)+\mu(4)$ with $\mu(4)$ not forced to vanish, breaking the binomial-theorem cancellation used in the proof.

Can Möbius inversion be used to define

\mu

rather than the other way around?

In a sense, yes — one common approach is to define $\mu$ as the unique Dirichlet inverse of $\mathbf{1}$ (i.e., the unique function with $\mu * \mathbf{1} = \varepsilon$ ), and then derive its explicit prime-factorization formula as a theorem. This article took the historical order (explicit formula first, inversion second), but the two developments are logically equivalent, and the convolution-ring proof given above makes the equivalence completely transparent.

Does the formula still work if

n

is replaced by an arbitrary positive real, or must

n

be a positive integer?

The formula as stated is only meaningful for positive integers $n$ , since "divisors of $n$ " and the prime factorization used to define $\mu$ both require $n \in \mathbb{Z}_{>0}$ . There is no direct extension to non-integer or negative arguments within this framework; generalizations instead go through Dirichlet series (where $\mu(n)$ appears as coefficients of $1/\zeta(s)$ ) or through Möbius functions of more general partially ordered sets, which is a different — though philosophically related — construction.

What is the fastest way to remember the formula without re-deriving it?

Think of $g = f * \mathbf{1}$ , read as " $g$ equals $f$ convolved with the all-ones function," and recall that $\mu$ is the Dirichlet inverse of $\mathbf{1}$ . Then inversion is just "divide by $\mathbf 1$ ," i.e. convolve by $\mu$ : $f = \mu * g$ . Writing this out termwise gives exactly $f(n) = \sum_{d\mid n}\mu(n/d)g(d)$ , and the mnemonic " $\mu$ undoes $\mathbf 1$ " is enough to reconstruct the whole formula on demand.

Does the sign pattern of

\mu(n/d)

have any interpretation, or is it just "whatever makes the algebra work"?

It has a clean interpretation: $\mu(n/d)$ is nonzero only when $n/d$ is squarefree, and its sign is $(-1)^{(\text{number of distinct primes dividing } n/d)}$ . This is exactly the inclusion–exclusion sign for "correcting" overcounts introduced by summing $f$ over all divisors: each additional prime factor in $n/d$ represents one more layer of overcounting to be alternately added and subtracted, mirroring inclusion–exclusion over the set of primes dividing $n$ .