2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Would the downvoter care to comment? $\endgroup$ – Bijesh K.S Jun 1 '16 at 3:56
  • 1
    $\begingroup$ 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. $\endgroup$ – user296602 Jun 1 '16 at 3:57
  • $\begingroup$ Ohk Thanks! I'll look to it@T.Bongers $\endgroup$ – Bijesh K.S Jun 1 '16 at 4:01
  • 1
    $\begingroup$ I have edited, thanks @MartinSleziak $\endgroup$ – Bijesh K.S Jun 1 '16 at 7:48
  • 1
    $\begingroup$ You really described your motivation for asking this very nicely, so it is not that surprising that the post was indeed reopened. $\endgroup$ – Martin Sleziak Jun 1 '16 at 9:18
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But I don't understand how $n=\sum_{k|n}\varphi(k)$ comes in? $\endgroup$ – Bijesh K.S Jun 1 '16 at 4:07
  • 1
    $\begingroup$ I will write down a proof. $\endgroup$ – marwalix Jun 1 '16 at 4:09
  • 1
    $\begingroup$ @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. $\endgroup$ – Martin Sleziak Jun 1 '16 at 7:52
  • $\begingroup$ Thanks for the links!, I should have researched properly @MartinSleziak $\endgroup$ – Bijesh K.S Jun 1 '16 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.