How can you prove the number-theoretic equation $\sum_{d|n} \phi(d) = n$?

[Euge]

Here is this week's POTW:

-----
Give a proof of the number-theoretic equation $$\sum_{d|n} \phi(d) = n$$ where $\phi(d)$ is the number of positive integers $\le d$ and relatively prime to $d$.-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[Euge]

Congratulations to Olinguito and castor28 for their correct solutions.

1. Olinguito's solution.

Spoiler

Let $N=\{1,\ldots,n\}$. For each $d\in N$ such that $d\mid n$, consider the set $N_d=\{r\in N:\gcd(r,n)=d\}$. Now if $s\in N$ and $sd\in N_d$, then $\gcd(sd,n)=d$ and so $\gcd\left(s,\frac nd\right)=1$. Conversely, if $s,sd\in N$ and $\gcd\left(s,\frac nd\right)=1$, then $\gcd(sd,n)=d$ and so $sd\in N_d$. Hence there is a bijection between $N_d$ and the set of all $s\in N$ such that $s\le \frac nd$ and $\gcd\left(s,\frac nd\right)=1$. It follows that $\left|N_d\right|=\phi\left(\frac nd\right)$.

Now if $r\in N_{d_1}$ and $r\in N_{d_2}$, then $d_1=\gcd(r,n)=d_2$. Hence the $N_d$ are pairwise disjoint. Moreover, if $r\in N$ then $r\in N_{\gcd(r,n)}$. Hence $\displaystyle\bigcup_{d\mid n}N_d=N$. It follows that
$$n=\sum_{d\mid n}\left|N_d\right|=\sum_{d\mid n}\phi\left(\frac nd\right)=\sum_{d\mid n}\phi(d)$$(since as $d$ ranges over all the divisors of $n$, so does $\frac nd$).

2. castor28's solution.

Spoiler

In a cyclic group of order $n$, each element generates a cyclic subgroup of order $d$ for some $d\mid n$.

The number of generators of that subgroup (the number of elements of order $d$) is $\phi(d)$. As these elements (for all $d\mid n$) account for all the $n$ elements of the group, we have :
$$
\sum_{d|n} \phi(d) = n
$$