The Mobius Function

How many integers in a range are free of a given prime factor, exactly? How does one count integers with no square factors? Or invert a divisor sum to recover an original sequence? These questions share a hidden mechanism. It is a small function that assigns to each positive integer a value in {−1,0,1}\{-1, 0, 1\}. This value encodes the parity and squarefreeness of its prime factorization. This function was discovered by August Ferdinand Möbius in 1832. It looks almost too simple to matter. Yet it is the engine behind sieve arguments. It also drives the inversion of divisor sums, and deep statements about the distribution of primes. The Möbius function matters because it is the arithmetic shadow of inclusion–exclusion. Sometimes one wants to count objects satisfying "none of these divisibility conditions." In that case, a sum weighted by μ\mu appears naturally. It systematically cancels overcounts. It converts sums over all divisors into sums over squarefree divisors only. It also provides the precise "inverse" operation to summing a function over divisors. This duality becomes indispensable once one has Multiplicative Functions in hand. The big picture: the set of arithmetic functions f:Z+→Cf:\mathbb{Z}^{+}\to\mathbb{C} forms a commutative ring. This ring arises under pointwise addition and Dirichlet convolution. Within this ring, the Möbius function μ\mu is the convolution inverse of the constant function 1\mathbf{1}. This single algebraic fact is proved rigorously below. It is the seed from which Mobius Inversion grows. It also grows the general theory of Dirichlet Convolution. This article gives the precise definition of μ\mu. It proves that μ\mu is multiplicative. It establishes the central summatory identity ∑d∣nμ(d)=[n=1]\sum_{d\mid n}\mu(d) = [n=1]. It also works through two nontrivial numerical examples. It isolates exactly which hypothesis makes the identity true, via a counterexample. Finally, it surveys where μ\mu appears in mathematics beyond pure number theory.

Key takeaways
  • μ(n)\mu(n) encodes whether nn is squarefree, and if so, the parity of its number of prime factors.
  • μ\mu is a multiplicative function: μ(mn)=μ(m)μ(n)\mu(mn)=\mu(m)\mu(n) whenever gcd⁡(m,n)=1\gcd(m,n)=1.
  • The central identity ∑d∣nμ(d)=[n=1]\sum_{d\mid n}\mu(d)=[n=1] makes μ\mu the Dirichlet-convolution inverse of the constant function 1\mathbf 1.
  • The proof is a direct binomial-coefficient computation on the squarefree divisors built from nn's distinct prime factors.
  • Dropping multiplicativity or the "sum over all divisors" hypothesis breaks the identity, as a concrete counterexample shows.
  • Key idea: μ\mu is inclusion–exclusion packaged as a number, and summing it over divisors performs exact cancellation except at n=1n=1.

Where this lives today

The Möbius function is the combinatorial heart of Möbius inversion, which recovers a function from its divisor-sum transform — a technique used to extract Euler's totient function, count squarefree integers, and invert generating relationships throughout combinatorics, as formalized generally by Gian-Carlo Rota's Möbius function on partially ordered sets (of which the divisor lattice is a special case). In analytic number theory, the Dirichlet series identity

∑n=1∞μ(n)ns=1ζ(s)\sum_{n=1}^{\infty} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}

links the growth of partial sums of μ\mu directly to the Riemann Hypothesis: the statement ∑n≤xμ(n)=O(x1/2+ϵ)\sum_{n\le x}\mu(n) = O(x^{1/2+\epsilon}) for every ϵ>0\epsilon>0 is equivalent to the Riemann Hypothesis. In cryptography and computational number theory, Möbius-weighted sums appear in fast algorithms for computing Euler's totient over ranges and in sieve-based primality and factorization routines. In combinatorics and computer science, the generalized Möbius function on posets underlies inclusion–exclusion algorithms, subset-sum sieves in competitive programming, and the zeta-function formalism of incidence algebras. In statistical physics, the Möbius function appears in counting problems for necklaces and in the combinatorics of the cycle index of symmetric groups relevant to partition functions.

:::faq[Does the identity ∑d∣nμ(d)=[n=1]\sum_{d\mid n}\mu(d) = [n=1] require nn to be squarefree?] No — the identity holds for every positive integer nn, squarefree or not. The proof shows that non-squarefree divisors of nn contribute exactly 00 to the sum automatically, since μ\mu vanishes there, so only the squarefree divisors (which always exist, since 1∣n1 \mid n and 11 is squarefree) contribute, and the binomial-theorem cancellation among those is what forces the total to 00 whenever n>1n>1.

Ask the tutor: How does the Möbius summatory identity get used to derive the Möbius inversion formula in full generality?

DefinitionThe Möbius function

The Möbius function μ:Z+→{−1,0,1}\mu:\mathbb{Z}^{+}\to\{-1,0,1\} is defined by

μ(n)={1if n=1,(−1)kif n=p1p2⋯pk for distinct primes p1,…,pk,0if p2∣n for some prime p.\mu(n) = \begin{cases} 1 & \text{if } n = 1,\\[2pt] (-1)^{k} & \text{if } n = p_1 p_2 \cdots p_k \text{ for distinct primes } p_1,\dots,p_k,\\[2pt] 0 & \text{if } p^2 \mid n \text{ for some prime } p. \end{cases}

Equivalently: μ(n)=0\mu(n)=0 unless nn is squarefree (i.e., not divisible by any perfect square greater than 11), in which case μ(n)=(−1)ω(n)\mu(n)=(-1)^{\omega(n)}, where ω(n)\omega(n) denotes the number of distinct prime factors of nn. By convention ω(1)=0\omega(1)=0, consistent with μ(1)=1\mu(1)=1.

Intuition

Think of μ(n)\mu(n) as a signed indicator that "activates" only on squarefree integers, and whose sign tracks how many independent prime "tags" nn carries. A prime pp has μ(p)=−1\mu(p) = -1; a product of two distinct primes like 6=2⋅36 = 2\cdot 3 has μ(6)=1\mu(6) = 1; but 4=224 = 2^2 is contaminated by a repeated prime and gets μ(4)=0\mu(4) = 0. The function is silent — literally zero — on any number with a squared prime factor, and alternates sign on squarefree numbers according to parity of prime count. The deeper reason μ\mu deserves attention is the identity it satisfies when summed over the divisors of nn. Picture the divisors of nn arranged as a lattice built from the prime-power "coordinates" in nn's factorization. Summing μ(d)\mu(d) over this lattice performs an alternating overcount/undercount cancellation — precisely the mechanism of inclusion–exclusion — and it collapses to 00 whenever there is more than one prime involved, surviving only at n=1n=1.

Figure
Divisor lattice of n=30=2⋅3⋅5n=30=2\cdot3\cdot5, with μ(d)\mu(d) labeled on each node; the eight values sum to 00
1 μ=1 2 μ=-1 3 μ=-1 5 μ=-1 6 μ=1 10 μ=1 15 μ=1 30 μ=-1

Multiplicativity of μ\mu

Before proving the summatory identity, we establish that μ\mu is multiplicative, since the proof of the main theorem uses this structural fact.

LemmaMultiplicativity

For all coprime positive integers m,nm,n (i.e., gcd⁡(m,n)=1\gcd(m,n)=1),

μ(mn)=μ(m) μ(n).\mu(mn) = \mu(m)\,\mu(n).
Proof

We argue by cases based on squarefreeness, using the Multiplicative Functions framework where a function respects coprime factorization. Case 1: mm or nn is not squarefree. Suppose p2∣mp^2 \mid m for some prime pp. Then p2∣mnp^2 \mid mn as well, so μ(mn)=0\mu(mn) = 0 by definition. Also μ(m)=0\mu(m) = 0, so μ(m)μ(n)=0=μ(mn)\mu(m)\mu(n) = 0 = \mu(mn). The symmetric case where p2∣np^2\mid n is identical. Case 2: both mm and nn are squarefree. Write m=p1⋯pjm = p_1\cdots p_j and n=q1⋯qkn = q_1 \cdots q_k as products of distinct primes (with j=ω(m)j = \omega(m), k=ω(n)k=\omega(n), and j=0j=0 or k=0k=0 allowed if m=1m=1 or n=1n=1). Since gcd⁡(m,n)=1\gcd(m,n)=1, no prime among p1,…,pjp_1,\dots,p_j equals any prime among q1,…,qkq_1,\dots,q_k; combined with distinctness within each list, all j+kj+k primes p1,…,pj,q1,…,qkp_1,\dots,p_j,q_1,\dots,q_k are pairwise distinct. Hence mnmn is squarefree with exactly j+kj+k distinct prime factors, so

μ(mn)=(−1)j+k=(−1)j(−1)k=μ(m)μ(n).\mu(mn) = (-1)^{j+k} = (-1)^j (-1)^k = \mu(m)\mu(n).

This exhausts all cases, proving the lemma. ■\blacksquare

∎

We now turn to the central result.

TheoremSummatory identity for the Möbius function

Let nn be a positive integer. Then

∑d∣nμ(d)={1if n=1,0if n>1,\sum_{d \mid n} \mu(d) = \begin{cases} 1 & \text{if } n = 1,\\ 0 & \text{if } n > 1, \end{cases}

where the sum runs over all positive divisors dd of nn.

Proof

We prove this by direct combinatorial computation, using the multiplicativity of μ\mu established above. Denote the sum by F(n):=∑d∣nμ(d)F(n) := \sum_{d\mid n}\mu(d).

Base case n=1n=1. The only divisor of 11 is 11 itself, so F(1)=μ(1)=1F(1) = \mu(1) = 1, matching the claim.

Case n>1n>1. Write the prime factorization of nn as

n=p1a1p2a2⋯prar,r≥1, ai≥1,n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad r \ge 1,\ a_i \ge 1,

with p1,…,prp_1,\dots,p_r distinct primes. Every divisor dd of nn has the form d=p1b1⋯prbrd = p_1^{b_1}\cdots p_r^{b_r} with 0≤bi≤ai0 \le b_i \le a_i. By definition, μ(d)=0\mu(d) = 0 whenever some exponent bi≥2b_i \ge 2, since then pi2∣dp_i^2 \mid d. So only divisors with each bi∈{0,1}b_i \in \{0,1\} contribute — precisely the squarefree divisors of nn, which correspond exactly to subsets S⊆{1,…,r}S \subseteq \{1,\dots,r\} via d=∏i∈Spid = \prod_{i \in S} p_i. There are 2r2^r such divisors, one for each subset. For a subset SS of size k=∣S∣k = |S|, the corresponding squarefree divisor d=∏i∈Spid=\prod_{i\in S} p_i has ω(d)=k\omega(d) = k distinct prime factors, so μ(d)=(−1)k\mu(d) = (-1)^k. Grouping the sum by subset size kk (there are (rk)\binom{r}{k} subsets of size kk), we get

F(n)=∑d∣nμ(d)=∑k=0r(rk)(−1)k.F(n) = \sum_{d \mid n} \mu(d) = \sum_{k=0}^{r} \binom{r}{k} (-1)^k.

By the binomial theorem applied to (1+x)r(1 + x)^r at x=−1x = -1,

∑k=0r(rk)(−1)k=(1+(−1))r=0r.\sum_{k=0}^{r} \binom{r}{k} (-1)^k = (1 + (-1))^r = 0^r.

Since r≥1r \ge 1 (as n>1n>1 forces at least one prime factor), 0r=00^r = 0. Hence F(n)=0F(n) = 0 for every n>1n>1. Combining the two cases proves the theorem. ■\blacksquare

∎
CorollaryConvolution-inverse characterization

Define the Dirichlet convolution of arithmetic functions f,gf,g by

(f∗g)(n)=∑d∣nf(d) g(n/d).(f * g)(n) = \sum_{d \mid n} f(d)\, g(n/d).

Let 1\mathbf{1} denote the constant function 1(n)=1\mathbf{1}(n) = 1 for all nn, and let ε\varepsilon denote the identity element of convolution, ε(n)=[n=1]\varepsilon(n) = [n=1] (equal to 11 if n=1n=1 and 00 otherwise). Then

μ∗1=ε.\mu * \mathbf{1} = \varepsilon.
Proof

By definition of Dirichlet convolution,

(μ∗1)(n)=∑d∣nμ(d) 1(n/d)=∑d∣nμ(d),(\mu * \mathbf{1})(n) = \sum_{d\mid n} \mu(d)\,\mathbf{1}(n/d) = \sum_{d \mid n} \mu(d),

since 1(n/d)=1\mathbf 1(n/d) = 1 for every divisor dd. By the theorem just proved, this sum equals ε(n)\varepsilon(n) for every n≥1n \ge 1. Hence μ∗1=ε\mu * \mathbf{1} = \varepsilon as functions on Z+\mathbb{Z}^+. ■\blacksquare

∎

This corollary is exactly the algebraic statement that μ\mu is the two-sided inverse of 1\mathbf{1} in the Dirichlet convolution ring (the ring is commutative, so μ∗1=1∗μ\mu * \mathbf 1 = \mathbf 1 * \mu), and it is the fact that powers Mobius Inversion.

Worked examples

Example 1: n=60n = 60. Factor 60=22⋅3⋅560 = 2^2 \cdot 3 \cdot 5. Its divisors are

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

We compute μ(d)\mu(d) for each, using squarefreeness and ω(d)\omega(d):

ddfactorizationsquarefree?ω(d)\omega(d)μ(d)\mu(d)
1—yes011
222yes1−1-1
333yes1−1-1
4222^2no—00
555yes1−1-1
62⋅32\cdot3yes211
102⋅52\cdot5yes211
1222⋅32^2\cdot3no—00
153⋅53\cdot5yes211
2022⋅52^2\cdot5no—00
302⋅3⋅52\cdot3\cdot5yes3−1-1
6022⋅3⋅52^2\cdot3\cdot5no—00

Summing: 1+(−1)+(−1)+0+(−1)+1+1+0+1+0+(−1)+01 + (-1) + (-1) + 0 + (-1) + 1 + 1 + 0 + 1 + 0 + (-1) + 0. Group the nonzero terms: 1−1−1−1+1+1+1−1=01 -1 -1 -1 +1+1+1 -1 = 0. Indeed this matches the theorem's prediction, since 60=22⋅3⋅560 = 2^2\cdot 3\cdot 5 has r=3r=3 distinct primes, and only the 23=82^3 = 8 squarefree divisors (1,2,3,5,6,10,15,301,2,3,5,6,10,15,30) contribute, summing via ∑k=03(3k)(−1)k=(1−1)3=0\sum_{k=0}^3 \binom{3}{k}(-1)^k = (1-1)^3 = 0. ✓.

Example 2: Using the identity to isolate squarefree divisor counting for n=23⋅7=56n = 2^3 \cdot 7 = 56. Suppose we want ∑d∣56μ(d)\sum_{d\mid 56}\mu(d) computed independently to double-check the theorem, and additionally illustrate a typical application: counting integers up to NN coprime to 5656 using μ\mu. First the divisor sum. 56=23⋅756 = 2^3\cdot 7, so r=2r=2 distinct primes (22 and 77). The squarefree divisors of 5656 are exactly the divisors of the squarefree "radical" 2⋅7=142\cdot 7 = 14: these are 1,2,7,141, 2, 7, 14. Their Möbius values: μ(1)=1\mu(1)=1, μ(2)=−1\mu(2)=-1, μ(7)=−1\mu(7)=-1, μ(14)=μ(2⋅7)=(−1)2=1\mu(14)=\mu(2\cdot7)=(-1)^2=1. Sum: 1−1−1+1=01 - 1 - 1 + 1 = 0, consistent with (20)−(21)+(22)=1−2+1=0\binom{2}{0}-\binom{2}{1}+\binom{2}{2} = 1-2+1=0. All other divisors of 5656 (namely 4,8,28,564, 8, 28, 56) carry a squared prime factor and contribute μ=0\mu=0. Now the application: count integers in {1,…,100}\{1,\dots, 100\} coprime to 5656, i.e., not divisible by 22 or 77 (the distinct prime factors of 5656). By inclusion–exclusion, this count is

∑d∣14μ(d)⌊100d⌋=μ(1)⌊100⌋+μ(2)⌊50⌋+μ(7)⌊100/7⌋+μ(14)⌊100/14⌋.\sum_{d \mid 14} \mu(d)\left\lfloor \frac{100}{d} \right\rfloor = \mu(1)\lfloor 100\rfloor + \mu(2)\lfloor 50 \rfloor + \mu(7)\lfloor 100/7\rfloor + \mu(14)\lfloor 100/14 \rfloor.

Numerically: ⌊100/1⌋=100\lfloor 100/1\rfloor = 100, ⌊100/2⌋=50\lfloor 100/2\rfloor = 50, ⌊100/7⌋=14\lfloor 100/7\rfloor = 14, ⌊100/14⌋=7\lfloor 100/14 \rfloor = 7. So the count is

100−50−14+7=43.100 - 50 - 14 + 7 = 43.

One can sanity-check this by direct reasoning: numbers coprime to 56=23⋅756=2^3\cdot7 up to 100100 are those coprime to 1414. By Euler's totient-style density, roughly 100⋅12⋅67≈42.86100 \cdot \frac{1}{2}\cdot\frac{6}{7} \approx 42.86, and the exact inclusion–exclusion count 4343 matches this estimate closely, confirming the computation is sound. This is precisely the mechanism by which μ\mu underlies sieve methods.

CounterexampleWhy "sum over all divisors" cannot be weakened to "sum over proper divisors"

The theorem requires summing μ(d)\mu(d) over every divisor dd of nn, including d=nd=n itself and d=1d=1. If we instead sum only over the proper divisors of nn (all divisors dd with 1≤d<n1 \le d < n), the identity fails. Take n=6n = 6. The full divisor sum is μ(1)+μ(2)+μ(3)+μ(6)=1+(−1)+(−1)+1=0\mu(1)+\mu(2)+\mu(3)+\mu(6) = 1 + (-1) + (-1) + 1 = 0, as the theorem predicts. But the proper-divisor sum omits d=6d=6:

μ(1)+μ(2)+μ(3)=1−1−1=−1≠0.\mu(1) + \mu(2) + \mu(3) = 1 - 1 - 1 = -1 \ne 0.

So restricting the range of summation — dropping the hypothesis that all divisors, including nn itself, are included — breaks the conclusion. This shows the hypothesis "dd ranges over all of nn's divisors" is not a superfluous technicality: the term μ(n)\mu(n) itself is load-bearing in the cancellation, since it is exactly the top-subset term (S={1,…,r}S = \{1,\dots,r\}, k=rk=r) needed for the binomial sum ∑k(rk)(−1)k\sum_k \binom{r}{k}(-1)^k to vanish completely.

Scope, edge cases & common traps

SituationWhat happensCommon mistake
n=1n=1∑d∣1μ(d)=μ(1)=1\sum_{d\mid 1}\mu(d) = \mu(1) = 1Forgetting n=1n=1 is the sole exception
n=pn=p primeμ(1)+μ(p)=1−1=0\mu(1)+\mu(p) = 1-1=0None typically, but good sanity check
n=p2n = p^2Divisors 1,p,p21,p,p^2: 1+(−1)+0=01 + (-1) + 0 = 0Assuming μ(p2)=(−1)2=1\mu(p^2)=(-1)^2=1 — wrong, it is 00 by definition, not by parity of exponent
nn squarefree with many factorsSum vanishes via binomial theoremTrying to verify by brute force for large rr instead of using the binomial argument
Summing over proper divisors onlyIdentity can fail (see counterexample)Misremembering the identity's summation range
μ\mu evaluated at non-squarefree inputAlways 00, regardless of exponent parityConfusing μ(n)\mu(n) with (−1)Ω(n)(-1)^{\Omega(n)} (using total prime count with multiplicity instead of ω\omega)

The mathematician behind it

Origins · 1 minAugust Ferdinand Möbius and how this was discovered
AF
August Ferdinand Möbius
1790–1868 · German mathematician and astronomer, University of Leipzig

Möbius is best known outside number theory for the Möbius strip in topology, but his 1832 paper Über eine besondere Art von Umkehrung der Reihen ("On a special kind of series inversion") introduced the function and inversion formula bearing his name. He worked at the Leipzig observatory for most of his career, straddling astronomy, projective geometry, and number theory, and his interest in inverting series directly motivated the arithmetic function studied here.

History
- 1790: August Ferdinand Möbius born in Schulpforta, Saxony.
- 1815: Möbius becomes an observer at the Leipzig Observatory.
- 1832: Möbius publishes the function and the inversion formula in Crelle's Journal.
- 1858: Möbius (independently with Johann Listing) describes the Möbius strip.
- 1868: Möbius dies in Leipzig; his function becomes foundational to 20th-century analytic number theory.
Is μ(0)\mu(0) defined?

No. The Möbius function is defined only on the positive integers Z+={1,2,3,… }\mathbb{Z}^{+} = \{1,2,3,\dots\}, since it is built from prime factorization, and 00 has no meaningful prime factorization (every positive integer divides 00, making "distinct prime factors of 00" an ill-posed notion). Standard treatments, including this one, restrict the domain to positive integers throughout, consistent with the broader convention for Multiplicative Functions, all of which are conventionally defined on Z+\mathbb{Z}^+ only.

Why is μ(1)=1\mu(1) = 1 rather than 00 or undefined?

Setting μ(1)=1\mu(1)=1 is what makes the Dirichlet convolution identity μ∗1=ε\mu * \mathbf{1} = \varepsilon hold, where ε(1)=1\varepsilon(1)=1. Combinatorially, 11 has zero distinct prime factors (ω(1)=0\omega(1)=0), so μ(1)=(−1)0=1\mu(1) = (-1)^0 = 1 is consistent with the general formula μ(n)=(−1)ω(n)\mu(n)=(-1)^{\omega(n)} for squarefree nn, of which 11 is a (vacuous) special case, being squarefree with an empty set of prime factors.

How does this identity relate to Mobius Inversion?

The identity μ∗1=ε\mu * \mathbf{1} = \varepsilon is exactly the algebraic fact needed to invert any relation of the form g(n)=∑d∣nf(d)g(n) = \sum_{d\mid n} f(d). Convolving both sides by μ\mu and using associativity of Dirichlet convolution recovers f(n)=∑d∣nμ(d) g(n/d)f(n) = \sum_{d\mid n}\mu(d)\, g(n/d). This inversion formula, whose full proof and applications are developed separately, is the direct practical payoff of the summatory identity proved here.

Is μ\mu completely multiplicative, like n↦nsn \mapsto n^s?

No. μ\mu is multiplicative (meaning μ(mn)=μ(m)μ(n)\mu(mn)=\mu(m)\mu(n) only when gcd⁡(m,n)=1\gcd(m,n)=1), but not completely multiplicative, which would require the identity to hold for all m,nm,n without the coprimality restriction. A quick check: μ(2)⋅μ(2)=(−1)(−1)=1\mu(2)\cdot\mu(2) = (-1)(-1) = 1, but μ(4)=0\mu(4) = 0 since 4=224=2^2 is not squarefree. Since gcd⁡(2,2)=2≠1\gcd(2,2)=2\ne 1, this is not a counterexample to multiplicativity as defined, but it does show completeness fails.

How fast can μ(n)\mu(n) be computed for large nn?

Computing μ(n)\mu(n) requires knowing whether nn is squarefree and, if so, the parity of its number of distinct prime factors — both derivable from the full prime factorization of nn. For a single nn, trial division up to n\sqrt n suffices in O(n)O(\sqrt n) time. For computing μ(k)\mu(k) for all k≤Nk \le N simultaneously, a linear or near-linear sieve (a variant of the Sieve of Eratosthenes) computes all values in O(Nlog⁡log⁡N)O(N \log\log N) time, which is the standard approach in computational number theory software.

Why does the value 00 matter — isn't it "no information"?

Far from being wasted, μ(n)=0\mu(n)=0 for non-squarefree nn is essential to the summatory identity's proof: it is precisely what lets the divisor sum reduce to a sum over squarefree divisors only, which then telescopes via the binomial theorem. Without this vanishing, the clean cancellation into ε(n)\varepsilon(n) would not occur, and μ\mu would not serve as the convolution inverse of 1\mathbf 1.

Before this

Where this leads