Euler phi divisor sum property. How to show that the sets in a proof are disjoint and their cardinalities sum up to $n$.

Solution 1:

Consider the elements of $[n]=\{1,2,\ldots,n\}$. Each element $k\in [n]$, will have exactly one value of $\gcd(k,n)$. Moreover, from the definition of $\gcd$, this value will be a divisor of $n$. Hence, each element $k\in [n]$ belongs in exactly one of $A(d)$, where $d$ is a divisor of $n$. Hence the family of sets $A(d)$ where $d|n$ are all pairwise disjoint and $\bigcup_{d|n} A(d)=[n]$. Therefore, from the addition principle, it follows that $\sum_{d|n} \left|A(d)\right|=\left|[n]\right|=n$.

We can also use this result to prove a well known identity: $\sum_{d|n} \phi(d)=n$. We want the value of the sum $\sum_{d|n} |A(d)|$, where $A(d)=\{k\in [n]\mid\gcd(k,n)=d\}$. Note that if $k\in A(d)$, then $d|k$. Moreover, we require that $\gcd\left(\frac{k}{d},\frac{n}{d}\right)=1$. Since $k\leq n$, this means that there are $\phi\left(\frac{n}{d}\right)$ elements in $A(d)$.

Hence, $\sum_{d|n} \left| A(d)\right|=\sum_{d|n} \phi\left(\frac{n}{d}\right)=\sum_{d|n} \phi(d)$. In the beginning, we showed that $\sum_{d|n} \left| A(d)\right|=n$, hence our proof is complete.