The Möbius Function
The Möbius function \mu(n) looks strange at first — it
spits out +1, -1 or 0
according to a number's prime structure. But it is the secret machinery of "inclusion–exclusion"
in number theory, and it will let us invert sums in a way nothing else can.
Definition
\mu(n) = \begin{cases} +1 & n = 1,\\ (-1)^{k} & n \text{ is a product of } k \text{ distinct primes (squarefree)},\\ \ \ 0 & n \text{ has a squared prime factor.} \end{cases}
So \mu(1) = 1, \mu(6) = \mu(2\cdot 3) = +1,
\mu(30) = \mu(2\cdot 3\cdot 5) = -1, and
\mu(12) = 0 (because 4 = 2^2 divides it). The
function vanishes on anything that isn't squarefree. It is
multiplicative.
The defining miracle
What makes \mu useful is how it sums over divisors. Add it up over all
divisors of n and almost everything cancels:
\sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1,\\ 0 & n > 1. \end{cases}
For n = 6:
\mu(1) + \mu(2) + \mu(3) + \mu(6) = 1 - 1 - 1 + 1 = 0. This perfect
cancellation is exactly the signed counting of inclusion–exclusion — and it acts as a kind
of arithmetic "delta function" that picks out n = 1.
Why we built it
That cancellation is precisely the tool needed to undo a sum-over-divisors relationship —
recovering a function from its accumulated totals. That inversion is so important it gets its own
page: Möbius inversion.