Sum Over Divisors Equals Sum Over Quotients

Theorem

Let $n$ be a positive integer.

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

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

Then:

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

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 $\displaystyle \frac n {d_1}, \frac n {d_2}, \ldots, \frac n {d_r}$ except in a different order.

Hence:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \sum_{d \backslash n} f \left({\frac n d}\right)\)	\(=\)	\(\displaystyle f \left({\frac n {d_1} }\right) + f \left({\frac n {d_2} }\right) + \cdots + f \left({\frac n {d_r} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle f \left({d_1}\right) + f \left({d_2}\right) + \cdots + f \left({d_r}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{d \backslash n} f \left({d}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\blacksquare$