Sum Over Divisors of Multiplicative Function
Theorem
Let $f: \Z_{>0} \to \Z_{>0}$ be a multiplicative function.
Let $n \in \Z_{>0}$.
Let $\ds \sum_{d \mathop \divides n} \map f d$ be the sum over the divisors of $n$.
Then $\ds \map F n = \sum_{d \mathop \divides n} \map f d$ is also a multiplicative function.
Proof
Let $\ds \map F n = \sum_{d \mathop \divides n} \map f d$.
Let $m, n \in \Z_{>0}: m \perp n$.
Then by definition:
- $\ds \map F {m n} = \sum_{d \mathop \divides m n} \map f d$
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.
It is noted that $r \perp s$, otherwise any common divisor of $r$ and $s$ would be a common divisor of $m$ and $n$.
Therefore:
- $\ds \map F {m n} = \sum_{r \mathop \divides m, \ s \mathop \divides n} \map f {r s}$
So, as $f$ is multiplicative:
- $\ds \map F {m n} = \sum_{r \mathop \divides m, \ s \mathop \divides n} \map f r \map f s$
But at the same time:
- $\ds \map F m \map F n = \paren {\sum_{r \mathop \divides m} \map f r} \paren {\sum_{s \mathop \divides n} \map f s}$
Multiplying out the product on the right hand side, $\map F {m n}$ and $\map F m \map F n$ are seen to be the same.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $31$