Prove that :
If $ n\ge 1 $,
then
$ \sum_{d|n}\phi(d)=n $.
Let $S$ denote the set $\{1,2,…,n\}$. We distribute the integers of $S$ into disjoint sets as follows. For each divisor $d$ of $n$, let
$A(d) = \{k \in S :(k,n) = d\}$
That is, $A(d)$ contains the elements of S which have the gcd d with n. The sets $A(d)$ for a disjoint collection whose union is S. Therefore if $f(d)$ denotes the number of integers in $A(d)$ we have
$\sum_{d|n}f(d)=n$
I don't understand why the sum of $f(d)$ equals $n$. Can someone explain this?
Best Answer
The elements of $A(d)$ are the numbers $k$ in the interval $[1,n]$ (that is, the set $S$) such that $\gcd(k,n)=d$. If $k$ is such a number, then $k=d\ell$ for some $\ell \in [1,n/d]$ relatively prime to $n/d$. There are $\varphi(n/d)$ such $\ell$ in the interval $[1,n/d]$. Thus the number of elements in $A(d)$ is $\varphi(n/d)$.
The $A(d)$ are pairwise disjoint, and their union is the set $S=\{1,2,3,\dots,n\}$. It follows that $$\sum_{d|n} \varphi(n/d)=n.\tag{1}$$ But as $d$ ranges over the divisors of $n$, so does $n/d$. It follows that $$\sum_{d|n}\varphi(n/d)=\sum_{d|n}\varphi(d).\tag{2}$$ By (1), the sum on the left-hand side of (2) is equal to $n$. It follows that the sum on the right-hand side is also $n$.