Mathematics.

elementary number theory

The Möbius Function

Number Theory30 minDifficulty5 out of 10

You should know: fundamental theorem of arithmetic

Overview

The Möbius function μ(n), introduced by August Ferdinand Möbius in 1832, is a multiplicative function that detects square-free structure: μ(n) = 0 if n has a repeated prime factor, and otherwise μ(n) = (−1)^k where k is the number of distinct prime factors of n. It is the key ingredient of Möbius inversion, a technique that reverses sums over divisors — if g(n) = Σ_{d|n} f(d), then f(n) = Σ_{d|n} μ(d) g(n/d), letting you recover f from a divisor sum of it. This machinery appears throughout multiplicative number theory: it gives a formula for Euler's totient function φ(n) = Σ_{d|n} μ(d)·n/d, and the identity Σ_{d|n} μ(d) = [n = 1] (equal to 1 only when n = 1, else 0) is the discrete engine behind sieve methods and the analytic study of the prime-counting function via the Möbius function's connection to 1/ζ(s).

Intuition

Think of μ(n) as a sign-and-kill filter over the divisors of n used in inclusion–exclusion. When you sum μ(d) over all divisors d of n, the +1s and −1s from square-free divisors cancel out in pairs — additively including then excluding overlapping cases — leaving 0 unless n = 1 has no structure to cancel. This is exactly the inclusion–exclusion principle in disguise: μ(d) records whether a divisor d corresponds to an even or odd number of 'excluded' prime factors, and any repeated prime factor makes the corresponding term vanish entirely (0), since such a divisor double-counts in the inclusion–exclusion argument.

Formal Definition

Definition

For a positive integer n with prime factorization n = p₁^{a₁}⋯pₖ^{aₖ}, the Möbius function is defined as:

μ(n)={1if n=1(−1)kif n is square-free with k distinct prime factors0if n has a squared prime factor\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^{k} & \text{if } n \text{ is square-free with } k \text{ distinct prime factors} \\ 0 & \text{if } n \text{ has a squared prime factor} \end{cases}
Definition of μ(n)
∑d∣nμ(d)={1n=10n>1\sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1 \\ 0 & n > 1 \end{cases}
Fundamental summation identity
g(n)=∑d∣nf(d) ⟹ f(n)=∑d∣nμ(d) g ⁣(nd)g(n) = \sum_{d \mid n} f(d) \ \Longrightarrow\ f(n) = \sum_{d \mid n} \mu(d)\, g\!\left(\frac{n}{d}\right)
Möbius inversion formula

Worked Examples

  1. 30 = 2·3·5, square-free with 3 distinct primes, so μ(30) = (−1)^3.

    μ(30)=−1\mu(30) = -1

  2. 12 = 2^2·3 has a squared prime factor (2^2), so μ(12) = 0.

    μ(12)=0\mu(12) = 0

  3. By definition μ(1) = 1 (the empty product, 0 distinct primes, (−1)^0 = 1).

    μ(1)=1\mu(1) = 1

Answer: μ(30) = −1, μ(12) = 0, μ(1) = 1.

Practice Problems

Difficulty 3/10

Compute μ(6), μ(7), and μ(8).

Difficulty 6/10

Verify the identity Σ_{d|n} μ(d) = 0 for n = 12 by summing μ(d) over all divisors d of 12.

Difficulty 7/10

Use φ(n) = Σ_{d|n} μ(d)·n/d to compute φ(12), and check it against the direct count of integers in {1,…,12} coprime to 12.

Quiz

μ(n) = 0 exactly when:
For a square-free n with k distinct prime factors, μ(n) equals:
Möbius inversion recovers f(n) from g(n) = Σ_{d|n} f(d) via:

Summary

  • μ(n) = 0 if n has a repeated prime factor; otherwise μ(n) = (−1)^k for k distinct prime factors (μ(1)=1).
  • The identity Σ_{d|n} μ(d) equals 1 if n=1 and 0 otherwise — the discrete inclusion–exclusion behind Möbius inversion.
  • Möbius inversion reverses divisor sums (g(n)=Σf(d) ⟹ f(n)=Σμ(d)g(n/d)), giving formulas like φ(n) = Σ_{d|n} μ(d)·n/d.

References

  1. WebsiteWikipedia — Möbius function