Another Totient sum

Posts: 791
Joined: Aug 4, 2011

by hemangsarkar, Nov 8, 2015, 12:07 PM

Q) $\sum_{k=1}^n gcd(k,n) = \sum_{d|n}d* \phi\left(\frac{n}{d}\right)$ where $\phi(n)$ is the Euler Totient function of $n$ .

Solution:
$gcd(k,n)$ for $1 \le k \le n$ will always be a value from the set of divisors of $n$ .

If we pick any divisor $d$ then we need to find out how many times does $d$ occur when $1 \le k \le n$ .

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

So the number of times $d$ occurs in $\sum_{k=1}^n gcd(k,n)$ is $\phi\left(\frac{n}{d}\right)$ .

$\sum_{k=1}^n gcd(k,n) = \sum_{d|n}f(d) = \sum_{d|n}d* \phi\left(\frac{n}{d}\right)$

It can be thus shown that

$\sum_{k=1}^n \frac{n}{gcd(k,n)} = \sum_{d|n}\left(\frac{n}{d}\right)\phi\left(\frac{n}{d}\right) = \sum_{d|n} d*\phi(d)$

This post has been edited 3 times. Last edited by hemangsarkar, Nov 8, 2015, 12:20 PM

Comment

hemangsarkar's blog

Another Totient sum

by hemangsarkar, Nov 8, 2015, 12:07 PM

0 Comments