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

  • 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