Exercise 4.2.6 ($\sum_{d\mid n} f(d) = \sum_{d \mid n} f(n/d)$)

Question

Prove that $\sum_{d \mid n} d = \sum_{d \mid n} n/d$, and more generally that $\sum_{d\mid n} f(d) = \sum_{d \mid n} f(n/d)$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

\begin{proof} 
Let $f : \N^* 	o \C$  be a function, and let $D_n$ denote the set of divisors of $n$, so that $\sum_{d \mid n} f(d)  = \sum_{d \in D_n} f(d)$.
Then the map
$$
\varphi
\left\{
\begin{array}{ccl}
D_n & 	o & D_n\
d & \mapsto & n/d
\end{array}
ight.
$$
is a bijection, because $\varphi \circ \varphi = 1_{D_n}$, so that $\varphi$ is an involution of $D_n$. Therefore
$$\sum_{d \in D_n} f(d) = \sum_{\delta \in D_n} f(\varphi(\delta)) =  \sum_{\delta \in D_n} f(n/\delta) = \sum_{d \in D_n} f(n/d).$$
This shows that
$$\sum_{d\mid n} f(d) = \sum_{d \mid n} f(n/d).$$
In the particular case  $f(n) = n$ for all $n \in \N^*$, we obtain
$$\sum_{d\mid n} d = \sum_{d \mid n} n/d.$$
\end{proof}

Exercise 4.2.6 ($\sum_{d\mid n} f(d) = \sum_{d \mid n} f(n/d)$)

Answers

Comments

Exercise 4.2.6 ($\sum_{d\mid n} f(d) = \sum_{d \mid n} f(n/d)$)

Answers

Comments

Add answer