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

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.

• Would the downvoter care to comment? – Bijesh K.S Jun 1 '16 at 3:56
• Can you share what you've tried, and what you're having trouble with? You've just copy-pasted a problem here without any thoughts or efforts shown, hence my downvote and vote for closure. – user296602 Jun 1 '16 at 3:57
• Ohk Thanks! I'll look to it@T.Bongers – Bijesh K.S Jun 1 '16 at 4:01
• I have edited, thanks @MartinSleziak – Bijesh K.S Jun 1 '16 at 7:48
• You really described your motivation for asking this very nicely, so it is not that surprising that the post was indeed reopened. – Martin Sleziak Jun 1 '16 at 9:18

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

• But I don't understand how $n=\sum_{k|n}\varphi(k)$ comes in? – Bijesh K.S Jun 1 '16 at 4:07
• I will write down a proof. – marwalix Jun 1 '16 at 4:09
• @BijeshK.S You can also have a look at this post to see some proofs of this equality. And some of the posts linked there might be worth looking at, too. – Martin Sleziak Jun 1 '16 at 7:52
• Thanks for the links!, I should have researched properly @MartinSleziak – Bijesh K.S Jun 1 '16 at 7:54