# Connection between GCD and totient function

I found the following formula which connects Euler's totient function with gcd at wikipedia.

$$\gcd(a,b) = \sum_{k|a \; \hbox{and} \; k|b} \varphi(k).$$

The problem is that I can not figure out what exactly I am suppose to sum up (basically what $k|a$ and $k|b$ mean in this context).

It would be nice if someone can provide an explanation (may be with some examples).

• $k|a$ and $k|b$ is equivalent to saying $k|\gcd(a,b)$. so the given equation is same as below : $$\gcd(a,b) = \sum_{k|\gcd(a,b)} \varphi(k).$$ Mar 1, 2015 at 11:37
• @ganeshie8 so this basically means sum of all $φ(k)$, where k is divisible by gcd(a, b)? Mar 1, 2015 at 11:42
• $\ldots$ where $k$ is a divisor of $\gcd(a,b)$ Mar 1, 2015 at 11:43
• More generally we have this for ANY positive integer $n$: $$n = \sum_{k|n} \varphi(k).$$ Mar 1, 2015 at 11:45
• @ganeshie8 thank you. Can you please post this (may be with a few examples as an answer), because you basically answered my question in the comments. Mar 1, 2015 at 11:46

$(\ldots \text{continued from comments})$ Consider an example when $\color{blue}{n=10}$.

Divisors of $\color{blue}{10}$ are $\{1,2,5,10\}$

$\varphi(1)=1$
$\varphi(2)=1$
$\varphi(5)=4$
$\varphi(10)=4$
Therefore \begin{align}\sum_{k|10} \varphi(k) &= \varphi(1)+ \varphi(2)+ \varphi(5)+ \varphi(10) \\~\\&=1+1+4+4\\~\\&=\color{blue}{10}\end{align}

as desired.

• thank you for the explanation. Do you know (by any chance) whether there is a way to find the sum from 1 to k of φ(i)? Mar 1, 2015 at 11:58
• You're looking for $\sum\limits_{i=1}^{k}\varphi(i)$ ? Mar 1, 2015 at 12:00
• Yes (my question was not about it), but when I looked at your explanation I started to wonder whether such thing exist and somehow connected to the formula, I asked. Mar 1, 2015 at 12:02
• see this Mar 1, 2015 at 12:07
• Thank you, just found it a couple of minutes before this. I thought that may be there is something less complicated. Anyway thank you for the excellent answer. Mar 1, 2015 at 12:08

$k|a$ means that $k$ divides $a$ or

$a = 0 \text{ } mod\text{ } k$ or

there is a $n\in N$ so that $k*n=a$

The same goes for $k|b$