Möbius Inversion
Often in number theory you know a function only through its running totals over divisors, and you
want the original back. Möbius inversion is the formula that recovers it — the
arithmetic analogue of the fundamental theorem of calculus, undoing a "sum over divisors" the way
differentiation undoes integration.
The setup
Suppose g is the divisor-sum of some function f:
g(n) = \sum_{d \mid n} f(d).
Knowing all the totals g, can we recover f? The
Möbius function
says yes — and gives an exact formula.
The inversion formula
If g(n) = \sum_{d \mid n} f(d) for all n, then
f(n) = \sum_{d \mid n} \mu(d)\, g\!\left(\frac{n}{d}\right).
The weights \mu(d) are exactly the signs that make the over-counting
cancel, thanks to the identity \sum_{d\mid n}\mu(d) = 0 for
n > 1. It is signed inclusion–exclusion, written once and for all.
A beautiful payoff
A classic application recovers
Euler's totient.
Because every number from 1 to n has a unique
gcd with n, one can show
\sum_{d \mid n} \varphi(d) = n. Möbius inversion turns this around into a
formula for \varphi itself:
\varphi(n) = \sum_{d \mid n} \mu(d)\,\frac{n}{d} = n \prod_{p \mid n}\left(1 - \frac1p\right).
The same machine appears throughout mathematics — counting necklaces, irreducible polynomials over
finite fields, and in the
Euler products
that open analytic number theory.