5
$\begingroup$

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.

2 Answers 2

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$.

  • 1
    Wow! 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
  • 0
    OK. 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.

  • 0
    I prefer this answer, since it's the most elementary.2015-08-15