Relation between $\gcd$ and Euler's totient function .

Question

How to show that $$\gcd(a,b)=\sum_{k\mid a\text{ and }k\mid b}\varphi(k).$$

$\varphi$ is the Euler's totient function.

I was trying to prove the number of homomorphisms from a cyclic group of order $m$ and $n$ is $\gcd(n,m)$.
Every cyclic group of order $n$ is isomorphic to $Z_n$. Hence a homomorphism from $Z_n$ to $Z_m$ is completely determined by the image of $1 \in Z_n$. If $1$ maps to $a$, I know that $|a|$ should divide both $n$ and $m$. So $|a|$ are common divisors of $n$ and $m$. Let $d$ be any positive common divisor of $n$ and $m$, then the number of elements of order $d$ in a cyclic group of order $n$ is $\phi(d)$. Then the number of candidates for $a$ is $\sum_{d|n\,and\,d|m}\varphi(d)$. If I am able to show the above relation, I'm done.

Answer 1

It is an immediate consequence of

$$n=\sum_{k|n}\varphi(k)$$

Because $k|a \text{ and } k|b\iff k|\gcd(a,b)$

Consider the set

$$D=\left\lbrace{1\over n},\ldots,{n\over n}\right\rbrace$$

$|D|=n$. Now consider the family of sets

$$D_d=\left\lbrace{k\over d}|\gcd(k,d)=1\text{ and }1\leq k\leq d\right\rbrace$$

The existence and unicity of the representation of a rational by an irreducible fraction allows to say that the sets $D_d$ for $d|n$ form a partition of $D$. And this gives

$$n=|D|=\sum_{d|n}|D_d|=\sum_{d|n}\varphi(d)$$