How to prove $$\sum\limits_{d\mid n} {\sigma (d)\varphi (n/d) = n\tau (n)}$$ and $$\sum\limits_{d\mid n} {\tau (d)\varphi (n/d) = \sigma (n)}$$ where ${\sigma (N)}$ is the divisor function, ${\tau (N)}$ is the number of positive divisors of $N$, and $\varphi (N)$ is Euler's totient? I am looking for a short proof.
Relation between $\sigma (N)$, $\tau (N)$, and $\varphi (N)$
5
$\begingroup$
elementary-number-theory
2 Answers
8
Use Dirichlet convolution: $$ \sum\limits_{d\mid n} \sigma (d)\varphi (n/d) = (\sigma * \varphi) (n) = (u * N * \mu * N)(n) = (N * N)(n) = n \tau(n) $$ where $u(n)=1$ and $N(n)=n$. By definition, $\sigma = u*N$. It's a famous (but easy) theorem that $N=u*\varphi$, from which follows that $\varphi = \mu * N$, since $u$ and $\mu$ are Dirichlet inverses (that's essentially Moebius inversion formula).
The second one follows in the same way: $$ \sum\limits_{d\mid n} \tau (d)\varphi (n/d) = (\tau*\phi)(n) = (u*u*\mu*N)(n) = (u*N)(n)=\sigma (n) $$ since $\tau = u*u$.
-
1Wow! Not only did you answer my question you actually taught me something I did not know. You see, the book we are using does not use the convolution notation $f*g$, nor does it use the identity map $N$ or the unit function $u$, which are extremely convenient as your answer shows. I wish I could upvote your answer more than once. Thanks! – 2012-11-13
-
1@glebovg, see for instance Chapter 2 of Apostol's *Introduction to Analytic Number Theory*. An excellent book. Which book are you using? – 2012-11-13
-
0OK. We are using *Elementary Number Theory* by Burton (undergrad number theory). We covered Mobius inversion, but the author does not mention Drichlet convolution, $N$, $u$, etc. – 2012-11-13
4
Hint: In all cases, the left side and the right side are multiplicative. So it is enough to verify things for prime powers, where computation is easy.
-
0I prefer this answer, since it's the most elementary. – 2015-08-15