Question

$\phi \left(1\right)\lfloor \frac{n}{1}\rfloor +\phi \left(2\right)\lfloor \frac{n}{2}\rfloor +...+\phi \left(n\right)\lfloor \frac{n}{n}\rfloor =\frac{n(n+1)}{n},$ where $\phi$ denotes Euler's totient function.

Answer 1

Observe that the right-hand side can be written as $=\frac{n(n+1)}{2}=1+\mathrm{2...}+n$ Using the result of problem 3.21of Sect. 3.3,we obtain $\frac{n(n+1)}{2}=\sum _{d/1}\phi \left(d\right)+...+\sum _{d/n}\phi \left(d\right).Now,forsomek,$\displaystyle 1\leq k\leq n,$letuscounthowmanytimes$\displaystyle \varphi \left ( k \right )$isatermofthesum$\displaystyle \sum_{d/m}\varphi \left ( d \right )$ifandonlyifkisadivisorofm,or,equivalently,misamultipleofk.So,$\displaystyle \varphi \left ( k \right ) $appearsasmanytimesasthenumberofmultiplesofkintheset1,2,...,nthatis,$\displaystyle \left \lfloor \frac{n}{k} \right \rfloor.$weconcludethatthesumcanbewrittenas$\displaystyle \varphi \left ( 1 \right )\left \lfloor \frac{n}{1} \right \rfloor+\varphi \left ( 2 \right )\left \lfloor \frac{n}{2} \right \rfloor+...+\varphi \left ( n \right )\left \lfloor \frac{n}{n} \right \rfloor, giving the required result. Alternatively, we cound count in two ways the number of fractions $\frac{a}{b}$ with $1\le a\le b\le n$ where we do not insist that our fraction be in lowest terms, so for example $\frac{1}{2}$ and $\frac{2}{4}$would count as different fractions. First, this number is clearly $\sum _{b=1}^n=\frac{n(n+1)}{2}$since this is the number of such pairs (a,b).Second, we count fractions based on their reduced forms. We saw in problem 3.21 that the number of reduced fractions with denominator d is $\varphi \left(d\right).$ The number of multiples of such a fraction with de-nominator at most n is $\lfloor n/d\rfloor$ so the number is also $\sum _{d=1}^n\varphi \left(d\right)\lfloor \frac{n}{d}\rfloor .$