The Möbius Function

Meet a function that looks almost deliberately unfriendly. Feed it a whole number n, and it hands back exactly one of three values: +1, -1, or 0. No smooth curve, no obvious pattern at a glance — just a strict little rule about how n breaks into primes. This is the Möbius function, written \mu(n).

Why would anyone invent something so fussy? Because it turns out to be exactly the right tool for a problem that shows up all over number theory: given a running total built by adding a function up over all the divisors of n, how do you get the original function back? That "un-summing" trick — Möbius inversion — needs \mu as its key ingredient, and nothing else quite does the job. First, let's see what the rule actually says.

The definition, case by case

To compute \mu(n), factor n into primes and look at the shape of that factorisation. There are exactly three outcomes:

In symbols, that's often written all at once:

\mu(n) = \begin{cases} +1 & n = 1,\\ (-1)^{k} & n = p_1 p_2 \cdots p_k \text{, distinct primes},\\ \ \ 0 & p^2 \mid n \text{ for some prime } p. \end{cases}

Notice that \mu only ever looks at which primes divide n and how many of them there are — never at how big n itself is, and (as long as it's squarefree) never at the primes' actual sizes either. Two utterly different squarefree numbers with the same number of prime factors get the same \mu value. It is multiplicative: for coprime a, b, \mu(ab) = \mu(a)\mu(b).

Worked examples: all three cases in action

The best way to get comfortable with \mu is to grind through a few values by hand, deliberately picking one of each kind.

Example 1 — squarefree, even count (so +1). Take n = 30. Factoring: 30 = 2 \cdot 3 \cdot 5. That's three distinct primes, none repeated, so n is squarefree. Wait — three is odd, so actually \mu(30) = (-1)^3 = -1. Let's instead check n = 6: 6 = 2 \cdot 3, two distinct primes, an even count, so \mu(6) = (-1)^2 = +1.

Example 2 — squarefree, odd count (so -1). Take n = 30 = 2 \cdot 3 \cdot 5 again: three distinct primes, an odd count, so \mu(30) = (-1)^3 = -1. A single prime is the simplest case of all — for any prime p, k = 1 is odd, so \mu(p) = -1 always. For instance \mu(7) = -1 and \mu(13) = -1.

Example 3 — a repeated prime factor (so 0). Take n = 12. Factoring: 12 = 2^2 \cdot 3. The prime 2 appears twice, so 4 = 2^2 divides 12. That single repeated factor is enough: \mu(12) = 0, full stop — it doesn't matter that 3 only appears once. The same happens for n = 18 = 2 \cdot 3^2 (the 3 repeats) and for any perfect square bigger than 1, like n = 9 = 3^2, giving \mu(9) = 0.

Lining up the first dozen values makes the "randomness" visible at a glance:

\mu(1),\dots,\mu(12) = 1,\ -1,\ -1,\ 0,\ -1,\ 1,\ -1,\ 0,\ 0,\ 1,\ -1,\ 0

There is no periodic pattern here — \mu genuinely depends on the fine detail of each number's prime factorisation, which is precisely why it can encode such delicate information about divisors.

A quick shortcut worth internalising: \mu(p) = -1 for every prime p (one prime factor is always an odd count), and \mu(p^2) = \mu(p^3) = \cdots = 0 for every higher power of a prime, since those all have a repeated factor. Those two facts alone let you sanity-check most small computations in your head before reaching for a full factorisation.

The defining miracle: a perfect cancellation

What makes \mu more than a curiosity is what happens when you sum it over all the divisors of a number. Almost everything cancels out:

\sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1,\\ 0 & n > 1. \end{cases}

Check it for n = 6, whose divisors are 1, 2, 3, 6:

\mu(1) + \mu(2) + \mu(3) + \mu(6) = 1 + (-1) + (-1) + 1 = 0.

And for n = 12, whose divisors are 1, 2, 3, 4, 6, 12:

\mu(1)+\mu(2)+\mu(3)+\mu(4)+\mu(6)+\mu(12) = 1 - 1 - 1 + 0 + 1 + 0 = 0.

Every time, for every n > 1, the pluses and minuses balance out to 0 exactly. This is the signed counting of inclusion–exclusion at work, and it makes \mu behave like an arithmetic "delta function" — a spike of size 1 at n=1 and silence everywhere else, once you sum over divisors. Use the explorer below to pick your own n: each bar is \mu(d) for a divisor d of n, and the total underneath always settles to 0 or 1.

The single most common mistake with \mu(n) is skipping the squarefree check and jumping straight to counting prime factors. If n has any repeated prime factor — even just one, buried among several distinct primes — the answer is immediately \mu(n) = 0, and it makes no difference how many other distinct primes are floating around.

For example, take n = 2 \cdot 3 \cdot 5 \cdot 5 = 150. A hurried student might see "three distinct primes, 2, 3, 5" and guess \mu(150) = (-1)^3 = -1. But 5 actually appears twice in the factorisation 150 = 2 \cdot 3 \cdot 5^2, so 25 \mid 150 and the correct answer is \mu(150) = 0.

The fix: always factor n completely first and check every exponent. Only once you've confirmed every prime appears to the power 1 — that n is genuinely squarefree — should you move on to counting how many distinct primes there are and applying the (-1)^k rule.

Here's a genuinely strange fact. Add up \mu(1) + \mu(2) + \cdots + \mu(N) for some large N — this running total is called M(N), the Mertens function. Since \mu(n) jumps unpredictably between +1, -1 and 0, you might expect M(N) to wander off wildly as N grows.

It doesn't. Remarkably, M(N) grows far more slowly than N itself — the pluses and minuses very nearly balance, on average, over long ranges. Proving exactly how slowly M(N) can grow turns out to be equivalent to one of the biggest open problems in all of mathematics: the Riemann hypothesis. A function defined by nothing more than counting prime factors modulo repeats connects, through this one sum, to the deepest unsolved question about the distribution of primes — and it is still being actively researched today.

Why we built it this way

It's worth pausing on why the definition has exactly this shape. The 0 on non-squarefree numbers isn't an accident or an afterthought — it's what makes the divisor-sum identity above come out so cleanly. And the alternating (-1)^k on squarefree numbers is exactly the sign pattern that inclusion–exclusion needs: add the primes' contributions, subtract the pairs' overlaps, add back the triples, and so on. Put those two pieces together and you get a function precisely engineered to cancel a sum over divisors down to almost nothing.

That cancellation is exactly the tool needed to undo a sum-over-divisors relationship — recovering a function from its accumulated totals. That inversion trick is powerful enough to get its own page: Möbius inversion.