---
tag: 0SAR26CKPS
kind: statement
role: proposition
name: Dirichlet convolution formula
msc: [11A25]
uses: [0KH1N66QWW]
sources:
  - url: https://en.wikipedia.org/wiki/Dirichlet_convolution
    locator: Definition
---

## Statement

Let $f$ and $g$ be arithmetic functions, and let $n$ be a positive integer.
Then
$$(f * g)(n) = \sum_{\substack{a, b \ge 1 \\ ab = n}} f(a) \, g(b),$$
where the sum runs over the ordered pairs of positive integers $(a, b)$ with $ab = n$, and $*$ is the [[Dirichlet convolution|0KH1N66QWW]].

## Remarks

The map $d \mapsto (d, n/d)$ is a bijection from the divisors of $n$ to these pairs. This gives the formula.
The symmetric form shows at once that $f * g = g * f$.
For example, $(f * g)(6) = f(1)g(6) + f(2)g(3) + f(3)g(2) + f(6)g(1)$.

## Explanations

### L1 human

Each divisor $d$ of $n$ comes with its partner $n/d$.
So a sum over divisors is the same as a sum over the ways to write $n$ as an ordered product of two factors.