Summation involving totient function: $\sum_{d\mid n} \varphi(d)=n$

Question

Prove that:$$\sum_{d\mid n} \varphi(d)=n$$

Where $\varphi(n)$ denotes the number of positive integers $m$ less than or equal to $n$ such that $\gcd(m,n)=1$

I am lost here, any help would be appreciated.

Answer 1

Here is my proof, based on counting arguments.

Consider the fractions $$\frac1{n},\frac{2}{n},\frac{3}{n},\cdots,\frac{n}{n}$$

Obviously there are $n$ such fractions.

Now consider these fractions, simplified to their lowest terms.

In each of these fractions, the denominator has to be a divisor of $n$. The number of fractions, in which the denominator is still equal to $n$, is the number of fractions whose numerator was originally relatively prime to $n$, i.e, $\varphi(n)$.

Similarly, for any given $d$, where $d$ is a divisor of $n$, there will be $\varphi(d)$ such fractions where the denominator is equal to $d$. Adding all these $\varphi(d)$ thus returns the total number of fractions, $n$.

So we arrive at the equality,

$$\sum_{d\mid n}\varphi(d)=n$$

Answer 2

Consider the cyclic group $C_n$. Then, for every $g\in C_n$, $o(g)$ divides $|C_n|=n$. Moreover, for any $d|C_n$, $\exists g\in C_n:o(g)=d$. Thereofore, if $A_k$ is the set of all the elements of $C_n$ with order $k$, $A_k \neq \emptyset \Longleftrightarrow k | n$. Therefore, $\{A_k : k | n\}$ is a partition of $C_n$. So:

$$|C_n|= n = \displaystyle{\sum _{g \in C_n}} 1 = \displaystyle{\sum _{d|n} |A_d|} = \displaystyle{\sum _{d|n} \varphi(d)}$$

Since the number of elements of order $d$ in $C_n$ is $\varphi(d)$.