[Math] Connection between GCD and totient function

divisibilityelementary-number-theorysummationtotient-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).

Best Answer

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

Related Question