Möbius Inversion Formula

Number Theory · Axiom Academy

LESSON The Mobius Inversion Formula A powerful technique for inverting sums over divisors in number theory Before we can understand inversion, we need to define the Mobius function, denoted by the Greek letter mu. This function encodes information about the prime factorization of integers. where p 1 , p 2 , ..., p k are distinct primes. In other words: if n has a squared prime factor, then mu(n) = 0. Otherwise, mu(n) = (-1)^k where k is the number of distinct prime factors. The Mobius function satisfies a remarkable property that makes inversion possible. When we sum mu(d) over all divisors of n, something special happens. This property is fundamental because it acts like a "delta function" in number theory - it picks out n=1 and annihilates everything else. This is precisely what allows us to perform inversion. The divisors of 6 are 1, 2, 3, 6 . 3. The Mobius Inversion Formula Now we arrive at the main result. The Mobius inversion formula establishes a bidirectional relationship between pairs of arithmetic functions. If g(n) is defined in terms of f(n) by: Then we can recover f(n) from g(n) using: This says that if g is the "divisor sum" of f, then f can be recovered by taking a weighted divisor sum of g, where the weights are given by the Mobius function. The proof is a beautiful application of the key property of the Mobius function. Let's see why the inversion formula is true. Starting with the proposed inverse formula, we substitute the definition of g:

This is the written version of the interactive lesson above. See the full Number Theory course.