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