Sum Over Divisors Equals Sum Over Quotients

Theorem

Let $n$ be a positive integer.

Let $f: \Z_{>0} \to \Z_{>0}$ be a mapping on the positive integers.

Let $\ds \sum_{d \mathop \divides n} \map f d$ be the sum of $\map f d$ over the divisors of $n$.

Then:

$\ds \sum_{d \mathop \divides n} \map f d = \sum_{d \mathop \divides n} \map f {\frac n d}$.

Proof

If $d$ is a divisor of $n$ then $d \times \dfrac n d = n$ and so $\dfrac n d$ is also a divisor of $n$.

Therefore if $d_1, d_2, \ldots, d_r$ are all the divisors of $n$, then so are $\dfrac n {d_1}, \dfrac n {d_2}, \ldots, \dfrac n {d_r}$, except in a different order.

Hence:

\(\ds \sum_{d \mathop \divides n} \map f {\frac n d}\)

\(=\)

\(\ds \map f {\frac n {d_1} } \map f {\frac n {d_2} } \cdots \map f {\frac n {d_r} }\)

\(\ds \)

\(=\)

\(\ds \map f {d_1} \map f {d_2} \cdots \map f {d_r}\)

\(\ds \)

\(=\)

\(\ds \sum_{d \mathop \divides n} \map f d\)

$\blacksquare$