3
$\begingroup$

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

$\endgroup$
6
  • 3
    $\begingroup$ $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).$$ $\endgroup$
    – AgentS
    Mar 1, 2015 at 11:37
  • 1
    $\begingroup$ @ganeshie8 so this basically means sum of all $φ(k)$, where k is divisible by gcd(a, b)? $\endgroup$
    – Salvador Dali
    Mar 1, 2015 at 11:42
  • 1
    $\begingroup$ $\ldots $ where $k$ is a divisor of $\gcd(a,b)$ $\endgroup$
    – AgentS
    Mar 1, 2015 at 11:43
  • 2
    $\begingroup$ More generally we have this for ANY positive integer $n$: $$n = \sum_{k|n} \varphi(k).$$ $\endgroup$
    – AgentS
    Mar 1, 2015 at 11:45
  • $\begingroup$ @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. $\endgroup$
    – Salvador Dali
    Mar 1, 2015 at 11:46

2 Answers 2

Reset to default
1
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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)? $\endgroup$
    – Salvador Dali
    Mar 1, 2015 at 11:58
  • $\begingroup$ You're looking for $\sum\limits_{i=1}^{k}\varphi(i)$ ? $\endgroup$
    – AgentS
    Mar 1, 2015 at 12:00
  • $\begingroup$ 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. $\endgroup$
    – Salvador Dali
    Mar 1, 2015 at 12:02
  • 1
    $\begingroup$ see this $\endgroup$
    – AgentS
    Mar 1, 2015 at 12:07
  • $\begingroup$ 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. $\endgroup$
    – Salvador Dali
    Mar 1, 2015 at 12:08
1
$\begingroup$

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

$\endgroup$

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.