Euler totient function sum of divisors. Theorem 2.2 Apostol

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?

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$.

We consider rational numbers

• 1/n,2/n,…,n/n

• Clearly there are n numbers in the list, we obtain a new list by reducing each number in the above list to the lowest terms ; that is, express the above list as a quotient of relatively prime integers. The denominator of the numbers in the new list will be divisor of n. If d divides n, exactly phi(d) of the numbers will have d as their denominator(this is the meaning of lowest term). Hence, there are (summation of phi(d)) in the new list . Because the two list have same number of terms, we obtain the desired result.

I like Gauß's proof: for each $d\mid n$, we have $\phi (d)$ generators for $C_d$, where $C_d$ is the cyclic group of order $d$. This is because, if $\langle g\rangle =C_d$, then $\langle g^k\rangle=C_d$ iff$(k,d)=1$.

Since every element of $C_n$ generates a cyclic subgroup, and every $C_d\le C_n$ is generated by some element of $C_n$, the claim follows.