TAOCP 1.2.4 Exercise 31

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 31. [M22] Prove that if $f(n)$ is multiplicative, so is

$$g(n)=\sum_{d \mid n} f(d).$$

Verified: yes
Solve time: 33s

Solution

Let $f(n)$ be a multiplicative function, and define

$g(n) = \sum_{d \mid n} f(d).$

We want to show that $g$ is multiplicative, that is, for any integers $r \perp s$,

$g(rs) = g(r) g(s).$

Since $r \perp s$, every divisor $d$ of $rs$ can be written uniquely as $d = d_1 d_2$, where $d_1 \mid r$ and $d_2 \mid s$. This follows from the fundamental theorem of arithmetic: any prime factor of $d$ must divide either $r$ or $s$, but not both, because $r$ and $s$ have no common prime factors. Conversely, for every pair of divisors $d_1 \mid r$ and $d_2 \mid s$, the product $d_1 d_2$ is a divisor of $rs$. Therefore we can write

$\sum_{d \mid rs} f(d) = \sum_{d_1 \mid r} \sum_{d_2 \mid s} f(d_1 d_2).$

By multiplicativity of $f$, since $d_1 \perp d_2$, we have $f(d_1 d_2) = f(d_1) f(d_2)$. Hence

$\sum_{d \mid rs} f(d) = \sum_{d_1 \mid r} \sum_{d_2 \mid s} f(d_1) f(d_2) = \left( \sum_{d_1 \mid r} f(d_1) \right) \left( \sum_{d_2 \mid s} f(d_2) \right) = g(r) g(s).$

This establishes that $g$ is multiplicative. This completes the proof.

∎