18.14 Möbius Function and Möbius Inversion

Many counting problems involve inclusion-exclusion. We count objects satisfying one condition, subtract those satisfying another, add back intersections, and continue alternating signs. The Möbius function packages this process into a powerful algebraic tool.

At first glance, the Möbius function appears obscure. In practice, it provides elegant solutions to divisor-sum problems, coprime counting, multiplicative-function analysis, and inversion of arithmetic relationships. Once understood, it becomes one of the most useful tools in advanced number theory.

This section introduces the Möbius function, develops its properties, and shows how Möbius inversion recovers hidden information from divisor-based sums.

Problem

Suppose we know:

F(n) = Σ f(d)
       d|n

for every positive integer n.

Can we recover:

f(n)

from the values of:

F(n)

This is precisely what Möbius inversion solves.

Definition of the Möbius Function

The Möbius function is written:

μ(n)

and defined as follows.

Case 1: n = 1

μ(1) = 1

Case 2: Repeated Prime Factor

If:

p² | n

for some prime p, then:

μ(n) = 0

Example:

μ(4) = 0
μ(12) = 0
μ(18) = 0
μ(72) = 0

because each contains a squared prime factor.

Case 3: Square-Free Number

If:

n = p₁p₂...pₖ

contains exactly k distinct prime factors and no repeated factors:

μ(n) = (-1)^k

Examples:

μ(2) = -1
μ(3) = -1
μ(5) = -1

because each contains one prime factor.

μ(6) = 1
μ(10) = 1
μ(15) = 1

because each contains two distinct prime factors.

μ(30) = -1

because:

30 = 2 × 3 × 5

contains three distinct primes.

First Values

The beginning of the sequence looks like:

n	μ(n)
1	1
2	-1
3	-1
4	0
5	-1
6	1
7	-1
8	0
9	0
10	1
11	-1
12	0
13	-1
14	1
15	1
16	0

Notice the frequent zeros caused by squared prime factors.

Computing μ(n) from Factorization

A direct implementation uses prime factorization.

def mobius(n):
    if n == 1:
        return 1

    distinct_primes = 0
    p = 2

    while p * p <= n:
        count = 0

        while n % p == 0:
            n //= p
            count += 1

        if count > 1:
            return 0

        if count == 1:
            distinct_primes += 1

        p += 1

    if n > 1:
        distinct_primes += 1

    return -1 if distinct_primes % 2 else 1

Examples:

print(mobius(6))
print(mobius(12))
print(mobius(30))

Output:

1
0
-1

Multiplicativity

The Möbius function is multiplicative.

If:

gcd(a,b)=1

then:

μ(ab)=μ(a)μ(b)

Example:

μ(2) = -1
μ(3) = -1

Therefore:

μ(6)
=
μ(2)μ(3)
=
1

This property allows efficient sieve-based computation.

Fundamental Identity

One of the most important identities in number theory is:

Σ μ(d)
d|n
=
1    if n=1
0    otherwise

Examples:

For:

n=1

we obtain:

μ(1)=1

For:

n=6

divisors are:

1,2,3,6

Thus:

μ(1)+μ(2)+μ(3)+μ(6)
=
1-1-1+1
=
0

This cancellation property drives Möbius inversion.

Counting Square-Free Numbers

A number is square-free if no prime square divides it.

Examples:

1
2
3
5
6
10
15

Non-examples:

4
8
9
12
18

A simple test uses the Möbius function:

μ(n) ≠ 0

if and only if:

n

is square-free.

Thus Möbius values naturally encode square-free structure.

Möbius Inversion Formula

Suppose:

F(n)
=
Σ f(d)
d|n

Then:

f(n)
=
Σ μ(d)F(n/d)
d|n

This is the Möbius inversion formula.

It transforms divisor sums into their original functions.

Conceptually:

Summation over divisors

and

Möbius inversion

are inverse operations.

Example

Suppose:

F(n)=number of divisors of n

Recall:

τ(n)
=
Σ 1
d|n

Thus:

F(n)
=
Σ f(d)

with:

f(d)=1

Applying Möbius inversion recovers:

f(n)

exactly.

The inversion cancels all unwanted divisor contributions.

Recovering Euler's Phi Function

A famous example starts from:

Σ φ(d)
d|n
=
n

For every positive integer n.

Applying Möbius inversion:

φ(n)
=
Σ μ(d)(n/d)
d|n

or:

φ(n)
=
n Σ μ(d)/d
    d|n

This formula provides an alternative way to compute phi values.

Example: Computing φ(12)

Divisors:

1,2,3,4,6,12

Corresponding Möbius values:

1,-1,-1,0,1,0

Apply:

φ(12)
=
12[
1
-
1/2
-
1/3
+
1/6
]

Simplify:

=
12 × 1/3
=
4

Wait, we made an arithmetic error.

Correct computation:

1
-
1/2
-
1/3
+
1/6
=
1/3

Multiplying:

12 × 1/3
=
4

This reveals that we accidentally computed only one divisor layer.

Using the full phi formula:

φ(12)=4

which matches the known result.

The example demonstrates the inversion mechanism rather than the most efficient computational route.

Möbius Transform

Given an array:

f(1)...f(n)

define:

F(x)
=
Σ f(d)
d|x

This operation is called the divisor transform.

Möbius inversion computes:

f

from:

F

Many advanced algorithms perform these transforms directly.

Sieve Computation

The Möbius function can be computed for all values up to n using a linear sieve.

def mobius_sieve(n):
    mu = [0] * (n + 1)
    mu[1] = 1

    primes = []
    is_composite = [False] * (n + 1)

    for x in range(2, n + 1):
        if not is_composite[x]:
            primes.append(x)
            mu[x] = -1

        for p in primes:
            if x * p > n:
                break

            is_composite[x * p] = True

            if x % p == 0:
                mu[x * p] = 0
                break

            mu[x * p] = -mu[x]

    return mu

Complexity:

O(n)

This is the standard approach when many Möbius values are required.

Coprime Pair Counting

A classic application counts pairs:

(a,b)

with:

1 ≤ a,b ≤ n

and:

gcd(a,b)=1

Using inclusion-exclusion directly becomes complicated.

Möbius inversion yields:

Σ μ(d)⌊n/d⌋²
d≤n

This formula appears frequently in computational number theory.

Dirichlet Convolution

Möbius inversion is naturally expressed through Dirichlet convolution.

Given arithmetic functions:

f
g

define:

(f * g)(n)
=
Σ f(d)g(n/d)
d|n

The Möbius function is the inverse of the constant function:

1(n)=1

under this operation.

Symbolically:

μ * 1 = ε

where:

ε(1)=1
ε(n)=0 for n>1

This viewpoint unifies many number-theoretic identities.

Applications

Inclusion-Exclusion

Möbius inversion is a generalized inclusion-exclusion principle.

Euler Phi Computation

Alternative formulas arise directly from inversion.

Coprime Counting

Many GCD-based counting problems simplify dramatically.

Multiplicative Functions

Dirichlet convolution relies heavily on Möbius theory.

Prime Number Research

The Möbius function appears throughout analytic number theory.

Competitive Programming

Many advanced divisor-sum problems require Möbius inversion.

Common Mistakes

Confusing μ(n)=0 with Composite Numbers

Many composite numbers have nonzero Möbius values.

Example:

μ(6)=1
μ(10)=1
μ(15)=1

Only repeated prime factors produce zero.

Forgetting Square-Free Requirement

The sign:

(-1)^k

applies only to square-free numbers.

Using Naive Factorization Repeatedly

When many values are needed, use a sieve.

Mixing Divisor and Multiple Loops

Möbius inversion formulas are sensitive to indexing.

Always verify whether the summation is over:

d|n

or:

n|d

Testing

def test_mobius():
    assert mobius(1) == 1
    assert mobius(2) == -1
    assert mobius(3) == -1
    assert mobius(4) == 0
    assert mobius(6) == 1
    assert mobius(30) == -1

Verify the fundamental identity:

def divisor_sum_mu(n):
    total = 0

    for d in range(1, n + 1):
        if n % d == 0:
            total += mobius(d)

    return total

Expected:

n=1 → 1
n>1 → 0

This is one of the most useful correctness checks.

Takeaway

The Möbius function encodes prime-factor structure through a simple rule: square-free numbers receive alternating signs based on the number of distinct prime factors, while numbers containing repeated prime factors receive zero. Its remarkable cancellation property leads to the Möbius inversion formula, which reconstructs arithmetic functions from divisor sums. Together, the Möbius function and Möbius inversion provide a powerful framework for inclusion-exclusion, coprime counting, multiplicative functions, divisor transforms, and advanced number-theoretic algorithms.