Dirichlet Convolution and Mobius Inversion

Pillar: Set — "Dirichlet convolution combines two arithmetic functions over the SET of divisors of $n$." Pillar: Fix — "Mobius inversion: if $g = f * \mathbf{1}$, then FIX $g$ and recover $f = g * \mu$."

The Setup

You know from Ch6 L4 that $\sum_{d \mid n} \mu(d) = [n = 1]$. You know that $\sum_{d \mid n} \phi(d) = n$. You've seen the Mobius function act as the "undo button" for inclusion-exclusion.

But these identities are not isolated coincidences. They are all instances of a single algebraic operation — Dirichlet convolution — and the fact that $\mu$ undoes summation over divisors is a theorem, not a trick.

Take a concrete question: how many ordered pairs $(a, b)$ with $1 \leq a, b \leq 10$ satisfy $\gcd(a, b) = 1$? You could loop over all $100$ pairs and check each GCD. Or you could compute the answer in one pass: $\sum_{d=1}^{10} \mu(d) \lfloor 10/d \rfloor^2$. The second formula runs in $O(n)$ time, drops to $O(\sqrt{n})$ with the floor staircase (Ch9 L4), and generalizes to GCD sums, totient sums, and a whole family of problems. The engine behind it is Mobius inversion.

Dirichlet Convolution

The Intuition

Consider two arithmetic functions $f$ and $g$ (functions from positive integers to real numbers). You want to "combine" them into a new function. One natural way: for each $n$, look at every way to split $n$ into a product of two factors $d$ and $n/d$, and sum up $f(d) \cdot g(n/d)$.

This is exactly the divisor structure. Every divisor $d$ of $n$ gives a complementary factor $n/d$, and you sum the product over all such pairs.

Formal Definition

The Dirichlet convolution of two arithmetic functions $f$ and $g$ is the function $f * g$ defined by:

\[(f * g)(n) = \sum_{d \mid n} f(d) \, g\!\left(\frac{n}{d}\right)\]

Equivalently, summing over all ordered pairs $(a, b)$ with $ab = n$:

\[(f * g)(n) = \sum_{\substack{a \cdot b = n \\ a, b \geq 1}} f(a) \, g(b)\]

The second form makes commutativity obvious: swapping $a$ and $b$ shows $f * g = g * f$.

Named Functions

Before listing identities, fix notation. These are the standard arithmetic functions:

Symbol	Name	Definition
$\varepsilon$	Dirichlet identity	$\varepsilon(1) = 1$, $\varepsilon(n) = 0$ for $n > 1$
$\mathbf{1}$	Constant $1$	$\mathbf{1}(n) = 1$ for all $n$
$\text{id}$	Identity	$\text{id}(n) = n$
$\mu$	Mobius function	$\mu(1) = 1$; $(-1)^k$ if $n$ is squarefree with $k$ primes; $0$ otherwise
$\phi$	Euler's totient	$\phi(n) = $ count of integers in $[1, n]$ coprime to $n$
$\tau$	Divisor count	$\tau(n) = \sum_{d \mid n} 1 =$ number of divisors of $n$
$\sigma$	Divisor sum	$\sigma(n) = \sum_{d \mid n} d =$ sum of divisors of $n$

Key Identities

1. $\mu * \mathbf{1} = \varepsilon$

Expand: $(\mu * \mathbf{1})(n) = \sum_{d \mid n} \mu(d) \cdot 1 = \sum_{d \mid n} \mu(d)$.

You proved in Ch6 L4 that this sum equals $[n = 1]$, which is exactly $\varepsilon(n)$. So $\mu$ is the Dirichlet inverse of $\mathbf{1}$.

Trace it for $n = 6$. Divisors: $1, 2, 3, 6$. Values of $\mu$: $1, -1, -1, 1$. Sum: $0 = \varepsilon(6)$. Correct.

2. $\phi * \mathbf{1} = \text{id}$

Expand: $(\phi * \mathbf{1})(n) = \sum_{d \mid n} \phi(d)$.

The identity $\sum_{d \mid n} \phi(d) = n$ was shown in Ch4 L5. The partition argument: every integer $k$ in $[1, n]$ satisfies $\gcd(k, n) = d$ for exactly one divisor $d$ of $n$, and exactly $\phi(n/d)$ values of $k$ give $\gcd(k, n) = d$.

Trace for $n = 6$: $\phi(1) + \phi(2) + \phi(3) + \phi(6) = 1 + 1 + 2 + 2 = 6$. Correct.

3. $\mathbf{1} * \mathbf{1} = \tau$

Expand: $(\mathbf{1} * \mathbf{1})(n) = \sum_{d \mid n} 1 \cdot 1 = \sum_{d \mid n} 1 = \tau(n)$.

Convolving $\mathbf{1}$ with itself just counts divisors. For $n = 12$: divisors are $1, 2, 3, 4, 6, 12$, so $\tau(12) = 6$.

4. $\text{id} * \mathbf{1} = \sigma$

Expand: $(\text{id} * \mathbf{1})(n) = \sum_{d \mid n} d = \sigma(n)$.

For $n = 6$: $1 + 2 + 3 + 6 = 12 = \sigma(6)$.

The Algebra

Dirichlet convolution is:

Commutative: $f * g = g * f$
Associative: $(f * g) * h = f * (g * h)$
Identity element: $\varepsilon$ (since $f * \varepsilon = f$ for any $f$)

This means arithmetic functions under $*$ form a commutative monoid with identity $\varepsilon$. The identity $\mu * \mathbf{1} = \varepsilon$ says $\mu$ is the multiplicative inverse of $\mathbf{1}$ in this monoid. And that inverse is what powers Mobius inversion.

The Mobius Inversion Theorem

Statement

Suppose $f$ and $g$ are arithmetic functions related by:

\[g(n) = \sum_{d \mid n} f(d)\]

In convolution notation: $g = f * \mathbf{1}$.

Then you can recover $f$ from $g$:

\[f(n) = \sum_{d \mid n} \mu(d) \, g\!\left(\frac{n}{d}\right)\]

In convolution notation: $f = g * \mu$.

Proof

Convolve both sides of $g = f * \mathbf{1}$ with $\mu$:

\[g * \mu = (f * \mathbf{1}) * \mu = f * (\mathbf{1} * \mu) = f * \varepsilon = f\]

Associativity lets you regroup. The key step is $\mathbf{1} * \mu = \varepsilon$, which you already proved. Done.

The proof is three lines because the algebraic framework does all the work. Once you know $\mu$ is the inverse of $\mathbf{1}$, inversion is just "multiply both sides by $\mu$."

Example: Recovering $\phi$ from $\text{id}$

You know $\text{id} = \phi * \mathbf{1}$ (identity 2). Apply Mobius inversion:

\[\phi(n) = \sum_{d \mid n} \mu(d) \cdot \frac{n}{d} = n \sum_{d \mid n} \frac{\mu(d)}{d}\]

Trace for $n = 12$. Divisors: $1, 2, 3, 4, 6, 12$. Compute $\mu(d) \cdot (12/d)$:

$d$	$\mu(d)$	$12/d$	$\mu(d) \cdot (12/d)$
$1$	$1$	$12$	$12$
$2$	$-1$	$6$	$-6$
$3$	$-1$	$4$	$-4$
$4$	$0$	$3$	$0$
$6$	$1$	$2$	$2$
$12$	$0$	$1$	$0$

Sum: $12 - 6 - 4 + 0 + 2 + 0 = 4 = \phi(12)$. Matches $12 \cdot (1 - 1/2)(1 - 1/3) = 4$.

Applications

Coprime Pair Counting

Problem. Count the number of ordered pairs $(a, b)$ with $1 \leq a, b \leq n$ and $\gcd(a, b) = 1$.

Define $f(d)$ as the number of pairs where $\gcd(a, b) = d$, and $g(d)$ as the number of pairs where $d \mid \gcd(a, b)$. If $d$ divides both $a$ and $b$, then $a$ and $b$ are multiples of $d$ in $[1, n]$, so:

\[g(d) = \left\lfloor \frac{n}{d} \right\rfloor^2\]

The relationship between $f$ and $g$ is:

\[g(d) = \sum_{\substack{k \geq 1 \\ dk \leq n}} f(dk) = \sum_{d \mid m} f(m)\]

Wait — this sums $f$ over multiples of $d$, not divisors of $d$. But Mobius inversion works for multiples too. The "multiples" version:

If $g(d) = \sum_{d \mid m} f(m)$, then $f(d) = \sum_{d \mid m} \mu(m/d) \, g(m)$.

Apply this to get $f(1)$ — the coprime pair count:

\[f(1) = \sum_{m=1}^{n} \mu(m) \, g(m) = \sum_{d=1}^{n} \mu(d) \left\lfloor \frac{n}{d} \right\rfloor^2\]

This is the key formula. Sieve $\mu$ in $O(n)$, then evaluate the sum in $O(n)$.

GCD Sum

Problem. Compute $\sum_{a=1}^{n} \sum_{b=1}^{n} \gcd(a, b)$.

Write $\gcd(a, b) = \sum_{d \mid \gcd(a,b)} \phi(d)$, using the identity $\sum_{d \mid n} \phi(d) = n$. Swap the order of summation:

\[\sum_{a=1}^{n} \sum_{b=1}^{n} \gcd(a, b) = \sum_{d=1}^{n} \phi(d) \sum_{\substack{1 \leq a, b \leq n \\ d \mid a, \, d \mid b}} 1 = \sum_{d=1}^{n} \phi(d) \left\lfloor \frac{n}{d} \right\rfloor^2\]

Sieve $\phi$ in $O(n)$, evaluate the sum in $O(n)$.

Squarefree Counting

Problem. Count squarefree integers in $[1, n]$.

A number $k$ is squarefree if and only if $\sum_{d^2 \mid k} \mu(d) = 1$ (and $0$ otherwise — this is a standard identity). Sum over $k$:

\[Q(n) = \sum_{k=1}^{n} \sum_{d^2 \mid k} \mu(d) = \sum_{d=1}^{\lfloor \sqrt{n} \rfloor} \mu(d) \left\lfloor \frac{n}{d^2} \right\rfloor\]

The inner swap counts, for each $d$, how many multiples of $d^2$ lie in $[1, n]$. This runs in $O(\sqrt{n})$ time — just iterate $d$ up to $\sqrt{n}$.

Worked Example: Coprime Pairs in $[1, 10]$

Compute $\sum_{d=1}^{10} \mu(d) \lfloor 10/d \rfloor^2$ step by step.

First, recall $\mu$ values:

$d$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$\mu(d)$	$1$	$-1$	$-1$	$0$	$-1$	$1$	$-1$	$0$	$0$	$1$

Now compute each term:

$d$	$\mu(d)$	$\lfloor 10/d \rfloor$	$\lfloor 10/d \rfloor^2$	Contribution
$1$	$1$	$10$	$100$	$+100$
$2$	$-1$	$5$	$25$	$-25$
$3$	$-1$	$3$	$9$	$-9$
$4$	$0$	$2$	$4$	$0$
$5$	$-1$	$2$	$4$	$-4$
$6$	$1$	$1$	$1$	$+1$
$7$	$-1$	$1$	$1$	$-1$
$8$	$0$	$1$	$1$	$0$
$9$	$0$	$1$	$1$	$0$
$10$	$1$	$1$	$1$	$+1$

Total: $100 - 25 - 9 + 0 - 4 + 1 - 1 + 0 + 0 + 1 = 63$.

So there are $63$ ordered pairs $(a, b)$ in $[1, 10]^2$ with $\gcd(a, b) = 1$.

Sanity check: the probability that two random integers are coprime is $6/\pi^2 \approx 0.6079$. For $n = 10$: $100 \times 0.6079 \approx 60.8$. The answer $63$ is close. The small deviation is expected for small $n$.

The Code

Coprime Pair Counting

Uses the sieveMu function from Ch6 L4.

long long countCoprimePairs(int limit) {
    vector<int> mu(limit + 1, 0);
    vector<int> smallestPrimeFactor(limit + 1, 0);
    vector<int> primes;
    mu[1] = 1;
    for (int current = 2; current <= limit; current++) {
        if (smallestPrimeFactor[current] == 0) {
            smallestPrimeFactor[current] = current;
            primes.push_back(current);
            mu[current] = -1;
        }
        for (int primeIndex = 0; primeIndex < (int)primes.size(); primeIndex++) {
            long long composite = (long long)current * primes[primeIndex];
            if (composite > limit) break;
            smallestPrimeFactor[composite] = primes[primeIndex];
            if (current % primes[primeIndex] == 0) {
                mu[composite] = 0;
                break;
            }
            mu[composite] = -mu[current];
        }
    }
    long long totalPairs = 0;
    for (int divisor = 1; divisor <= limit; divisor++) {
        if (mu[divisor] == 0) continue;
        long long multiplesCount = limit / divisor;
        totalPairs += mu[divisor] * multiplesCount * multiplesCount;
    }
    return totalPairs;
}

$O(n)$ time, $O(n)$ space.

GCD Sum

long long gcdSum(int limit) {
    vector<long long> phi(limit + 1, 0);
    vector<int> smallestPrimeFactor(limit + 1, 0);
    vector<int> primes;
    phi[1] = 1;
    for (int current = 2; current <= limit; current++) {
        if (smallestPrimeFactor[current] == 0) {
            smallestPrimeFactor[current] = current;
            primes.push_back(current);
            phi[current] = current - 1;
        }
        for (int primeIndex = 0; primeIndex < (int)primes.size(); primeIndex++) {
            long long composite = (long long)current * primes[primeIndex];
            if (composite > limit) break;
            smallestPrimeFactor[composite] = primes[primeIndex];
            if (current % primes[primeIndex] == 0) {
                phi[composite] = phi[current] * primes[primeIndex];
                break;
            }
            phi[composite] = phi[current] * (primes[primeIndex] - 1);
        }
    }
    long long totalGCDSum = 0;
    for (int divisor = 1; divisor <= limit; divisor++) {
        long long multiplesCount = limit / divisor;
        totalGCDSum += phi[divisor] * multiplesCount * multiplesCount;
    }
    return totalGCDSum;
}

$O(n)$ time, $O(n)$ space.

Common Mistakes

Confusing divisor-sum inversion with multiple-sum inversion. If $g(n) = \sum_{d \mid n} f(d)$, inversion gives $f(n) = \sum_{d \mid n} \mu(d) g(n/d)$. But the coprime counting setup has $g(d) = \sum_{d \mid m} f(m)$ — summation over multiples of $d$, not divisors. The inversion formula changes accordingly: $f(d) = \sum_{d \mid m} \mu(m/d) g(m)$. Mixing these up flips the $\mu$ argument and gives wrong answers.
Overflow in the squared floor term. $\lfloor n/d \rfloor^2$ can reach $n^2$. For $n = 10^6$, that's $10^{12}$, which fits in long long. But if you accumulate a sum of $n$ such terms, the total can approach $n^3$ — for $n = 10^6$, that's $10^{18}$, right at the long long boundary. Use long long everywhere in the accumulation, and be aware that $n > 10^6$ may need the floor staircase from Ch9 L4.
Forgetting to skip $\mu(d) = 0$ terms. Not a correctness issue — zero times anything is zero — but a performance habit. In the coprime pair formula, roughly $60\%$ of values have $\mu(d) = 0$. Skipping them is a constant-factor speedup.

Quick Recap

Dirichlet convolution $(f * g)(n) = \sum_{d \mid n} f(d) g(n/d)$ combines arithmetic functions over the divisor set. It is commutative, associative, with identity $\varepsilon$.
The key identity is $\mu * \mathbf{1} = \varepsilon$: the Mobius function is the Dirichlet inverse of the constant function $\mathbf{1}$.
Mobius Inversion Theorem: if $g = f * \mathbf{1}$, then $f = g * \mu$. In sums: if $g(n) = \sum_{d \mid n} f(d)$, then $f(n) = \sum_{d \mid n} \mu(d) \, g(n/d)$.
Coprime pair count in $[1, n]$: $\sum_{d=1}^{n} \mu(d) \lfloor n/d \rfloor^2$. GCD sum: $\sum_{d=1}^{n} \phi(d) \lfloor n/d \rfloor^2$. Both run in $O(n)$ after sieving.
These $O(n)$ formulas drop to $O(\sqrt{n})$ using the floor staircase — the subject of Ch9 L4.

Problems

Problem	Link	Difficulty	Focus
CSES — Counting Coprime Pairs	cses.fi/problemset/task/2417	Medium	Mobius sieve + $\sum \mu(d) \lfloor n/d \rfloor^2$
CF 1009F — Dominant Indices	codeforces.com/problemset/problem/1009/F	Medium	Divisor-sum manipulation
SPOJ LCMSUM — LCM Sum	spoj.com/problems/LCMSUM	Medium	Mobius inversion to convert LCM sum to GCD sum
CF 548E — Mike and Frog	codeforces.com/problemset/problem/547/C	Medium-Hard	GCD constraints + divisor enumeration
CF 839D — Winter is here	codeforces.com/problemset/problem/839/D	Hard	$\mu$-based inversion on array GCDs
CF 1139D — Steps to One	codeforces.com/problemset/problem/1139/D	Hard	Expected value + Mobius inversion
PE 351 — Hexagonal Orchards	projecteuler.net/problem=351	Hard	Coprime pair counting in hexagonal geometry

Symbol	Name	Definition
\(\varepsilon\)	Dirichlet identity	\(\varepsilon(1) = 1\), \(\varepsilon(n) = 0\) for \(n > 1\)
\(\mathbf{1}\)	Constant \(1\)	\(\mathbf{1}(n) = 1\) for all \(n\)
\(\text{id}\)	Identity	\(\text{id}(n) = n\)
\(\mu\)	Mobius function	\(\mu(1) = 1\); \((-1)^k\) if \(n\) is squarefree with \(k\) primes; \(0\) otherwise
\(\phi\)	Euler's totient	$\phi(n) = $ count of integers in \([1, n]\) coprime to \(n\)
\(\tau\)	Divisor count	\(\tau(n) = \sum_{d \mid n} 1 =\) number of divisors of \(n\)
\(\sigma\)	Divisor sum	\(\sigma(n) = \sum_{d \mid n} d =\) sum of divisors of \(n\)

\(d\)	\(\mu(d)\)	\(12/d\)	\(\mu(d) \cdot (12/d)\)
\(1\)	\(1\)	\(12\)	\(12\)
\(2\)	\(-1\)	\(6\)	\(-6\)
\(3\)	\(-1\)	\(4\)	\(-4\)
\(4\)	\(0\)	\(3\)	\(0\)
\(6\)	\(1\)	\(2\)	\(2\)
\(12\)	\(0\)	\(1\)	\(0\)

\(d\)	\(\mu(d)\)	\(\lfloor 10/d \rfloor\)	\(\lfloor 10/d \rfloor^2\)	Contribution
\(1\)	\(1\)	\(10\)	\(100\)	\(+100\)
\(2\)	\(-1\)	\(5\)	\(25\)	\(-25\)
\(3\)	\(-1\)	\(3\)	\(9\)	\(-9\)
\(4\)	\(0\)	\(2\)	\(4\)	\(0\)
\(5\)	\(-1\)	\(2\)	\(4\)	\(-4\)
\(6\)	\(1\)	\(1\)	\(1\)	\(+1\)
\(7\)	\(-1\)	\(1\)	\(1\)	\(-1\)
\(8\)	\(0\)	\(1\)	\(1\)	\(0\)
\(9\)	\(0\)	\(1\)	\(1\)	\(0\)
\(10\)	\(1\)	\(1\)	\(1\)	\(+1\)

Dirichlet Convolution and Mobius Inversion

The Setup

Dirichlet Convolution

The Intuition

Formal Definition

Named Functions

Key Identities

1. \(\mu * \mathbf{1} = \varepsilon\)

2. \(\phi * \mathbf{1} = \text{id}\)

3. \(\mathbf{1} * \mathbf{1} = \tau\)

4. \(\text{id} * \mathbf{1} = \sigma\)

The Algebra

The Mobius Inversion Theorem

Statement

Proof

Example: Recovering \(\phi\) from \(\text{id}\)

Applications

Coprime Pair Counting

GCD Sum

Squarefree Counting

Worked Example: Coprime Pairs in \([1, 10]\)

The Code

Coprime Pair Counting

GCD Sum

Common Mistakes

Quick Recap

Problems