Euler totient function sum of divisors. Theorem 2.2 Apostol

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

Here is another approach to solve this problem if you are familiar with cyclic groups although it is equivalent to approaches given in other answers. But knowing the interdependency of mathematical disciplines is always beneficial.

Let $G(a)$ be the cyclic group generated by the element $a$ of order $n$. By fundamental theorem of cyclic groups we know that for each divisor $k$ of $n$ , $G(a)$ has excatly one subgroup of order $k$ - namely $G(a^{\frac{n}{k}})$. Also we know that $G(a^k) = G(a)$ if and if only $gcd(n,k) = 1$.

Now if $d$ divides $n$ then there is exactly one subgroup of order $d$ and let it be $G(b)$. Then every element of order $d$ generates $G(b)$. But $G(b^k) = G(b)$ only if $gcd(k,d)=1$. So number of elements having order $d$ is $\phi(d)$.

Now if the total number of elements in given cyclic group is $n$, then by fundamental theorem of cyclic groups, $$ \sum_{d|n} \phi(d) = n $$