Exercise 4.3.18 ($\sigma(n) = \sum_{\delta \mid n} \phi(\delta) d(n/\delta)$)

Question

Show that for any positive integer $n$, $\sigma(n) = \sum_{d \mid n} \phi(d) d(n/d)$.

Richard Ganaye · Accepted Answer

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

\begin{proof} 
We define $f(n) = \sum\limits_{\delta \mid n} \phi(\delta) d(n/\delta)$. Then 
\begin{align*}
f(n) &=  \sum_{d_1 \mid n} \phi(d_1 ) d\left(\frac{n}{d_1}ight)\
&=\sum_{d_1 \mid n} \phi(d_1 ) \sum_{d_2 \mid \frac{n}{d_1}} 1\
&= \sum_{d_1 \mid n}\  \sum_{d_2 \mid \frac{n}{d_1}} \phi(d_1)\
&= \sum_{d_2 \mid n}\  \sum_{d_1\mid \frac{n}{d_2} }\phi(d_1)
\end{align*}
because 
$$\left(d_1 \mid n 	ext{ and } d_2 \mid \frac{n}{d_1}ight) \iff \left(d_2 \mid n 	ext{ and } d_1\mid \frac{n}{d_2}ight).$$
By theorem 4.6, 
$$ \sum_{d_1\mid \frac{n}{d_2} }\phi(d_1) = \frac{n}{d_2},$$
so
\begin{align*}
f(n) &=  \sum_{d_2 \mid n} \frac{n}{d_2}\
&= \sum_{\delta \mid n} \delta & (\delta = n/d_2)\
&= \sigma(n).
\end{align*}
For every positive integer $n$,
$$\sigma(n) = \sum\limits_{\delta \mid n} \phi(\delta) d\left(\frac{n}{\delta}ight).$$
\end{proof}

Note: For a more insightful proof, we show first the commutativity and associativity of the Dirichlet product $\star$. Let $f,g,h$ be arithmetic functions.

For all positive integer $n$, 
$$(f \star g)(n) = \sum_{d \mid n} f(d) g\left(\frac{n}{d} ight) = \sum_{(d_1,d_2) \in \N^* 	imes \N^* : d_1d_2 = n} f(d_1) g(d_2)$$
(for simplicity, we write this sum $\sum\limits_{d_1d_2 = n} f(d_1) g(d_2)$).

First, $(g \star h)(n) = \sum\limits_{d_2d_1 = n} g(d_2)f(d_1)  = \sum\limits_{d_1d_2 = n} f(d_1) g(d_2) = (f \star g)(n),$ so $f \star g = g \star f$.

Next
\begin{align*}
[(f \star g) \star h](n) &= \sum_{d d_3 = n} (f \star g)(d) h(d_3)\
&= \sum_{d d_3 = n} \left (\sum_{d_1 d_2 = d} f(d_1)g(d_2) ight) h(d_3)\
&= \sum_{d_1d_2d_3 = n} f(d_1) g(d_2) h(d_3).
\end{align*}
Using the commutativity of $\star$ and this result, where $(f,g,h)$ is replaced by $(h,f,g)$, we obtain 
\begin{align*}
[(f \star g) \star h] &= [h \star (f \star g)](n)\
&=  \sum_{d_3 d_1d_2= n} h(d_3)f(d_1) g(d_2) \
&= [(f \star g) \star h](n).
\end{align*}
Therefore $(f \star g) \star h = f \star (g \star h)$.

If we write ${\bf 1}$ the function defined by ${\bf 1}(n) = 1$ for all positive integer $n$, and $\mathrm{id}$ the function defined by $\mathrm{id}(n) = n$, then $d = {\bf 1} \star {\bf 1}$,  $\phi \star {\bf 1} =\mathrm{id}$ and $\mathrm{id} \star {\bf 1} = \sigma$, thus
\begin{align*}
\phi \star d &= \phi \star ({\bf 1} \star {\bf 1})\
&= (\phi \star {\bf 1}) \star {\bf 1}\
&= \mathrm{id} \star {\bf 1}\
&= \sigma.
\end{align*}
This shows that for all positive integer $n$,
$$\sigma(n) = \sum\limits_{\delta \mid n} \phi(\delta) d\left(\frac{n}{\delta}ight).$$

Exercise 4.3.18 ($\sigma(n) = \sum_{\delta \mid n} \phi(\delta) d(n/\delta)$)

Answers

Comments

Exercise 4.3.18 ($\sigma(n) = \sum_{\delta \mid n} \phi(\delta) d(n/\delta)$)

Answers

Comments

Add answer