I am a graduate student of Mathematics.I am now studying analytic number theory from Apostol's book.In the exercise $3$ there is a question which is as follows:
If $x\geq1$,Show that $\sum\limits_{n\leq x} \varphi(n)=\frac{1}{2}\sum\limits_{n\leq x}\mu(n)[\frac{x}{n}]^2+\frac{1}{2}$,where $\varphi$ and $\mu$ are respectively the Euler's totient function and Mobius function and $[.]$ denotes the greatest integer function.
I have no idea how to start with.Can someone help me to solve this?
Best Answer
For every integer $n$, you have the classical relation $$\varphi(n)= \sum_{d|n} \mu(d)\frac{n}{d}$$
Hence \begin{align*} \sum_{n \leq x} \varphi(n) &= \sum_{n \leq x}\sum_{d|n} \mu(d)\frac{n}{d}\\ & = \sum_{d \leq x} \mu(d)\sum_{n \leq \frac{x}{d}} n \end{align*}
by interverting the two sums. So $$\sum_{n \leq x} \varphi(n) = \sum_{d \leq x}\mu(d) \frac{\left\lfloor \frac{x}{d}\right\rfloor \left(\left\lfloor \frac{x}{d}\right\rfloor +1\right)}{2}$$
and because $\sum_{d \leq x} \mu(d)\left\lfloor \frac{x}{d}\right\rfloor = 1$, you get directly that
$$\boxed{\sum_{n \leq x} \varphi(n) = \frac{1}{2 }+ \frac{1}{2}\sum_{d \leq x}\mu(d) \left\lfloor \frac{x}{d}\right\rfloor^2}$$