Sum Over Divisors of Multiplicative Function

Theorem

Let $f: \Z_{>0} \to \Z_{>0}$ be a multiplicative function.

Let $n \in \Z_{>0}$.

Let $\displaystyle \sum_{d \backslash n} f \left({d}\right)$ be the sum over the divisors of $n$.

Then $\displaystyle F \left({n}\right) = \sum_{d \backslash n} f \left({d}\right)$ is also a multiplicative function.

Proof

Let $\displaystyle F \left({n}\right) = \sum_{d \backslash n} f \left({d}\right)$.

Let $m, n \in \Z_{>0}: m \perp n$.

Then by definition:

$\displaystyle F \left({m n}\right) = \sum_{d \backslash m n} f \left({d}\right)$

The divisors of $m n$ are of the form $d = r s$ where $r$ and $s$ are divisors of $m$ and $n$ respectively, from Divisors of Product of Coprime Integers.

Therefore:

$\displaystyle F \left({m n}\right) = \sum_{r \backslash m, s \backslash n} f \left({r s}\right)$

(Note of course that $r \perp s$ otherwise any common divisor of $r$ and $s$ would be a common divisor of $m$ and $n$.)

So, as $f$ is multiplicative:

$\displaystyle F \left({m n}\right) = \sum_{r \backslash m, s \backslash n} f \left({r}\right) f \left({s}\right)$

But at the same time:

$\displaystyle F \left({m}\right) F \left({n}\right) = \left({\sum_{r \backslash m} f \left({r}\right)}\right) \left({\sum_{s \backslash n} f \left({s}\right)}\right)$

Multiplying out the product on the right, $F \left({m n}\right)$ and $F \left({m}\right) F \left({n}\right)$ are seen to be the same.

$\blacksquare$

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.4$: Exercises $31$