Question 95
For all positive integers $n$, prove that
$$
\sum_{k=1}^{n} \phi(k)\left\lfloor\frac{n}{k}\right\rfloor=\frac{n(n+1)}{2}
$$
(For a positive integer $n$, $\phi(n)$ denotes the number of positive integers less than or equal to $n$ and relatively prime to $n$. For a real number $x$, $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$.)
$$
\sum_{k=1}^{n} \phi(k)\left\lfloor\frac{n}{k}\right\rfloor=\frac{n(n+1)}{2}
$$
(For a positive integer $n$, $\phi(n)$ denotes the number of positive integers less than or equal to $n$ and relatively prime to $n$. For a real number $x$, $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$.)