Engineering / Mathematics — Integer Foundations
Arithmetic Functions and Mobius Inversion
Multiplicative arithmetic functions, Dirichlet convolution, the Mobius function and the inversion formula.
Executive summary
Arithmetic functions — maps from the positive integers to a ring — form an algebra under Dirichlet convolution, and the multiplicative ones behave particularly well under it.
The Mobius function is the convolution inverse of the constant function 1, and that single fact is what makes Mobius inversion work. The inversion formula is used throughout analytic number theory and in counting irreducible polynomials over finite fields.
Learning objectives
- Define multiplicative functions and Dirichlet convolution.
- State the Mobius function and its defining property.
- Apply Mobius inversion to recover a function from its divisor sums.
01Multiplicative functions
Multiplicative and completely multiplicative
An arithmetic function f is multiplicative if f(1) = 1 and f(mn) = f(m)f(n) whenever gcd(m, n) = 1.
It is completely multiplicative if the identity holds for all m, n without the coprimality condition.
A multiplicative function is determined by its values on prime powers, since any n factors into coprime prime powers. This reduces the study of such functions to a local question at each prime.
| Function | Definition | Type |
|---|---|---|
| φ(n) | Count of units mod n | Multiplicative |
| τ(n) | Number of divisors | Multiplicative |
| σ(n) | Sum of divisors | Multiplicative |
| μ(n) | Möbius function | Multiplicative |
| 1(n) = 1 | Constant one | Completely multiplicative |
| Id(n) = n | Identity | Completely multiplicative |
02Dirichlet convolution and the Mobius function
Dirichlet convolution
(f * g)(n) = Σ_{d | n} f(d) · g(n/d), summed over positive divisors of n.
This operation is commutative and associative, has identity the function that is 1 at n = 1 and 0 elsewhere, and preserves multiplicativity. The multiplicative functions form a group under it.
Möbius function
μ(n) = 1 if n is a product of an even number of distinct primes; −1 if an odd number; 0 if n has a squared prime factor.
So μ(1) = 1, μ(6) = 1, μ(30) = −1, μ(12) = 0.
Defining property
Σ_{d | n} μ(d) = 1 if n = 1, and 0 otherwise.
Equivalently, μ * 1 is the convolution identity, so μ is the inverse of the constant function 1.
03The inversion formula
Möbius inversion
If g(n) = Σ_{d | n} f(d) for all n, then
f(n) = Σ_{d | n} μ(d) · g(n/d).
In convolution notation this is trivial: g = f * 1 implies f = g * μ, because μ inverts 1. The apparent depth of the formula is entirely contained in the defining property of μ.
A standard application recovers Euler's phi from the identity Σ_{d|n} φ(d) = n, giving φ(n) = Σ_{d|n} μ(d) · n/d, which expands to the familiar product formula.
04Frequently asked questions
Why is μ(n) zero on non-squarefree numbers?
Because that is what makes μ the convolution inverse of 1. The defining property Σ_{d|n} μ(d) = 0 for n > 1 forces this value once the squarefree cases are fixed, so it is derived rather than chosen for convenience.
Is Dirichlet convolution related to ordinary convolution?
They are analogous. Ordinary convolution sums over additive decompositions n = i + j; Dirichlet convolution sums over multiplicative decompositions n = d · (n/d). Both correspond to multiplying generating functions, one ordinary and one a Dirichlet series.
Where does Mobius inversion matter computationally?
Most directly in counting irreducible polynomials over a finite field, which is needed to justify that random search for an irreducible polynomial of given degree succeeds quickly. It also appears in sieve methods for prime counting.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 28-32.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.