Summing the Euler $\varphi$-function $\varphi(n)$ The Euler $\varphi$-function $\varphi(n)$ counts the number of positive integers less than or equal to $n$,
which are relatively prime with $n$.
I would like to evaluate 
$$ \sum_{d\mid n}\varphi(d) $$and prove that the  answer is correct.

Define the sets $A_q = \{(n,k)=q \mid 1 \leq k \leq n\}$. As you can see, total number of elements of $A_1, \dots, A_n$ is equal to $n$ since for each $i \neq j $, $A_i \cap A_j = \emptyset $.
Now let us check how many elements does $A_d$ have:
If $x \in A_d$ then $(n,x)=d$ so that $(\frac{n}{d},\frac{x}{d})=1$. Then we can say that the number of such $x$'s is equal to $\varphi(\frac{n}{d})$.
$\implies |A_d|=\varphi(\frac{n}{d})$.
Going back to our sum:
$\sum_{d \mid n} \varphi(d) = \sum_{d\mid n}\varphi(\frac{n}{d})= \sum_{d \mid n}|A_d| =n$ as desired.
