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

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.

Answer 4

Let’s construct the same set $S_d=\{x: 1\leq x\leq n$ and $gcd(x,n)=d\}$ in a different way and find out. This way, I believe, one can feel all the details. Although one might argue that some of these facts needn't be proved as they are already clear in their definition. But as I've seen, most people can't agree, at first, how these are so obvious.

Take $A_d=\{x: 1\leq x\leq \frac{n}{d}$ and $ gcd(x,\frac{n}{d})=1\}$. Then of course, $\mid A_d\mid =\varphi(\frac{n}{d})$ as this is indeed the definition of $\varphi$. Now consider the set $B_d=\{x: x=d.y$ where $ y\in A_d\}$. Then again, of course, $\mid B_d\mid =\varphi(\frac{n}{d})$. For any $x \in B_d$, both $gcd(x,n)=d$ and $1\leq x\leq n$ are true. So, $B_d \subseteq S_d$. If there was an $m \in S_d$ but $m \notin B_d$, then that would mean, $\frac{m}{d}∉A_d$. But that can’t be possible as $\frac {m}{d}(=x)$ satisfies $1\leq x\leq \frac {n}{d}$ and $gcd(x,\frac {n}{d})=1$, both the conditions to be in $A_d$. Hence, $B_d=S_d \Longrightarrow\mid S_d\mid =\mid B_d\mid =\varphi(\frac {n}{d})$. Now consider the set $S= \bigcup{S_d}$ . This set must include all integers from $1$ to $n$. For if it didn’t, then there would exist an $x$ such that $1\leq x\leq n$ but $gcd(x,n)=k$ which is not one of the $d$s we considered. But that is not possible. So it follows that, $\mid S\mid =\sum{\mid S_d \mid } =\sum{\varphi(\frac{n}{d})}= \sum{\varphi(d)}=n$.

Answer 5

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