Totient function sum of divisors

Posts: 791
Joined: Aug 4, 2011

by hemangsarkar, Nov 8, 2015, 11:36 AM

Q) Let $n \geq 1$ then $\sum_{d|n}\phi(d) = n$ where $\phi(n)$ denotes the Euler Totient function of $n$ .

Solution:
Let $S$ denote the set $\{1,2,\cdots,n\}$ . We distribute the integers of $S$ into disjoint sets as follows. For each divisor $d$ of $n$ , let
$A(d)=\{k:(k,n)=d,1 \le k \le n\}$

That is, $A(d)$ contains the elements of $S$ which have the gcd $d$ with $n$ . The sets $A(d)$ form a disjoint collection whose union is $S$ .

Let $m$ be one element in $A(d)$ , then $gcd(m,n) = d$ .

hence $m = dl, n = dk$ where $gcd(l,k) = 1$ .

Also since $l \leq k$ and they are relatively prime we have $\phi(k) = \phi\left(\frac{n}{d}\right)$ choices for such $l$ .

Therefore if $f(d)$ denotes the number of integers in $A(d)$ we have

$f(d) = \phi\left(\frac{n}{d}\right)$

hence,

$\sum_{d|n}f(d) = \sum_{d|n}\phi\left(\frac{n}{d}\right) = \sum_{d|n}\phi(d) = n$ .

This post has been edited 4 times. Last edited by hemangsarkar, Nov 8, 2015, 11:56 AM

hemangsarkar's blog

Totient function sum of divisors

by hemangsarkar, Nov 8, 2015, 11:36 AM

1 Comment