$$ \sum_{m =1}^n {m\over\gcd(m,n)}$$

For example, for 1 it is

$${1\over\gcd(1,1)} =1;$$

for 5 it is $${1\over \gcd(1,5)}+{2\over \gcd(2,5)}+{3\over \gcd(3,5)}+{4\over \gcd(4,5)}+{5\over \gcd(5,5)}=\\ \frac11+\frac21+\frac31+\frac41+1 = \\ 1+2+3+4+1= \\ 11$$

  • $\begingroup$ @MJD: thanks a lot for the excellent editing and formatting $\endgroup$ – user43255 Oct 9 '12 at 18:44
  • $\begingroup$ I didn't get exactly the question, could you be a bit more explicit please? $\endgroup$ – Giovanni De Gaetano Oct 9 '12 at 18:47
  • $\begingroup$ @GiovanniDeGaetano That was my fault. I have tried to make the question more explicit: OP wants to compute the indicated sum. $\endgroup$ – MJD Oct 9 '12 at 18:48
  • $\begingroup$ @GiovanniDeGaetano:sir if you need any clarifications for the question ,please comment. Also,I think answer could involve use of the totient function. $\endgroup$ – user43255 Oct 9 '12 at 18:49
  • $\begingroup$ OEIS does not give any simple closed form, which it surely would if one were known. It does point out that the sum is equal to $1 + \frac12\sum_{d\vert n} d\cdot\varphi(d)$, where $\varphi$ is the Euler totient function. $\endgroup$ – MJD Oct 9 '12 at 19:06

If you define $S(n)$ as your sum:

$$S(n)=\sum_{m=1}^n \frac{m}{(m,n)}$$

then we will show that $2S(n)-1$ is multiplicative.

You can rewrite the sum as:

$$S(n)=\sum_{d\mid n} \sum_{m=1}_{(m,n)=d}^n \frac{m}{d}$$

Setting $k=m/d$, we get:

$$S(n)=\sum_{d\mid n} \sum_{k=1}_{(k,n/d)=1}^{n/d} k = \sum_{d\mid n}\sum_{k=1}_{(k,d)=1}^d k$$

So let $$f(d) = \sum_{k=1}_{(k,d)=1}^d k$$

It is not hard to show that this $f(1)=1$ and $f(d)=\frac{1}{2}\phi(d)d$ when $d>1$.

So we get:

$$S(n)=\frac{1}{2}+\frac{1}{2}\sum_{d\mid n} \phi(d)d$$

Now $g(n)=\sum_{d|n} d\phi(d)$ is multiplicative, since $n\phi(n)$ is, so $g(n)$ is determined by $$g(p^a) = 1+\sum_{i=1}^a p^i\phi(p^i) = \\1+\sum_{i=1}^a p^{2i-1}(p-1) = \\1 + p(p-1)\sum_{i=1}^a p^{2i-2} = \\1+p(p-1)\frac{p^{2a}-1}{p^2-1}=\\ \frac{p^{2a+1}+1}{p+1}$$

And in general, if $n=\prod p_i^{a_i}$ then $$g(n)=\prod \frac{p_i^{2a_i+1}+1}{p_i+1}$$

And your original sum is:


So, for example, $$g(12)=g(2^2)g(3^1)= \frac{2^5+1}{2+1}\frac{3^3+1}{3} = 11\cdot 7 = 77$$ So when $n=12$, your sum is $S(12)=\frac{77+1}{2}=39$.

For $n=143$, $$g(143)=g(11)g(13)=\frac{11^3+1}{11+1}\frac{13^3+1}{13+1} = 111\cdot 157 = 17427$$ and your sum is $S(143)=\frac{17427+1}{2}=8714$.


If $\ n=p\ $ is prime, we can say


But in general, in spite of the fact that the number $\,22\,$ appears several times in the first few non-prime numbers, there doesn't seem to be an easy way out. For example:



We know $(m,n)=(n-m,n)$ where $1\le m \le n-1$

and $\frac n {(n,n)}=1$

So, $$\frac m {(m,n)}+\frac{n-m}{(n-m,n)}=\frac m {(m,n)}+\frac{n-m}{(m,n)}=\frac{n}{(n,m)}$$

If $n$ is odd, $m$ will be upto $\frac{n-1}2$

$ \sum_{m =1}^n {m\over\gcd(m,n)}=n \sum_{m =1}^{\frac{n-1}2}\frac 1{(m,n)}$

If $n$ is even, $m$ will be upto $\frac{n}2$. Here for $$m=\frac n 2, \frac{\frac n 2}{(\frac n 2, n)}=1$$

$ \sum_{m =1}^n {m\over\gcd(m,n)}=1+n \sum_{m =1}^{\frac{n-2}2}\frac 1{(m,n)}$

  • $\begingroup$ :i see a recursion here $\endgroup$ – user43255 Oct 9 '12 at 19:03
  • $\begingroup$ @user43255, could you please elaborate a bit more? $\endgroup$ – lab bhattacharjee Oct 9 '12 at 19:07
  • $\begingroup$ : I mean,it is quite similar if we can express the simplified summation which you derived in a format similar to original expression,I think than the problem is solved $\endgroup$ – user43255 Oct 9 '12 at 19:09
  • $\begingroup$ Nice use of symmetry. $\endgroup$ – André Nicolas Oct 9 '12 at 20:36
  • $\begingroup$ @AndréNicolas, thanks. But unfortunately, it didn't lead me much further. $\endgroup$ – lab bhattacharjee Oct 10 '12 at 16:18

For every divisor $d|n$ there will be some $m$ such that $\gcd(m,n)=d$, namely precisely those of the form $m=kd$ with $\gcd(k,\frac nd)=1$ and $1\le k\le \frac nd$. Note that with $$\tag1f(n):=\sum_{1\le k\le n\atop \gcd(k,n)=1}k$$ we have $$F(n)=\sum_{d|n}f(d)$$ as your function in question. As $\gcd(k,n)=\gcd(n-k,n)$, the summands in $(1)$ can be paired off into $\frac{\phi(n)}2$ summands $k+(n-k)=n$. One checks the special cases $n=1$ and $n=2$ separately to see that $$f(n)=\begin{cases}\frac{n\phi(n)}2&n>1\\1&n=1\end{cases}$$ holds. The function $\tilde f(n)=n\phi(n)$ would be a multiplicative function, hence so would $\tilde F(n)=\sum_{d|n}d\phi(d)$. Thus to compute $\tilde F(n)$ it is sufficient to know the values at prime powers. We have for $p$ prime and $k\ge 1$ $$p^k\phi(p^k)=\left(1-\frac1p\right)p^{2k},$$ hence $$\tilde F(p^k)=1+\left(1-\frac1p\right)\sum_{r=1}^kp^{2r}=1+\left(1-\frac1p\right)\cdot\frac{p^{2k+2}-p^2}{p^2-1}=1+p\cdot \frac{p^{2k}-1}{p+1}.$$ Thus finally we have $$\tag2F(n)=\frac12 (\tilde F(n)+1) = \frac12+\frac12\prod_{p|n}\left(1+p\cdot \frac{p^{2k}-1}{p+1}\right).$$

Remark: From the expression $p\cdot \frac{p^{2k}-1}{p+1}$ it is not surprising that cyclotomic polynomials play a role for $F(p^k)$.


Continuing DonAntonio's answer let's examine the case where $n=pq $ whith $p>q$ primes.

In this case we have (using inclusion $-$ exclusion): $$ \displaystyle{\sum_{m=1}^{pq}\frac{m}{\gcd(m,pq)}= \sum_{i=1}^{pq}i-(q\sum_{i=1}^{p}i+ p\sum_{i=1}^{q}i-pq)+\sum_{i=1}^{p-1}i+\sum_{i=1}^{q-1}i+1=\\ \frac{pq(pq-1)}{2}-\frac{(p+q)(p-1)(q-1)}{2}+1} \ . $$

For example, for $n=22$ we have that $\displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=167 \ }$ and for $n=13\cdot 29=377$ we have that $\displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=63821 \ .}$

To go little further we have with the same method the following:

$$ \text{for} \ n=p \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p(p-1)}{2}+1=\frac{p\phi_1(p)}{2}+1} ,\\ \text{for} \ n=p^2 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p(p-1)(p^2+1)}{2}+1=\frac{p\phi_1(p)\phi_4(p)}{2}+1} ,\\ \text{for} \ n=p^3 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p(p-1)(p^2+p+1)(p^2-p+1)}{2}+1=\frac{p\phi_1(p)\phi_3(p)\phi_6(p)}{2}+1} ,\\ \text{for} \ n=p^4 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p(p-1)(p^2+1)(p^4+1)}{2}+1=\frac{p\phi_1(p)\phi_4(p)\phi_8(p)}{2}+1} ,\\ \text{for} \ n=p^5 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p\phi_1(p)\phi_5(p)\phi_{10}(p)}{2}+1} ,\\ \text{for} \ n=p^6 \ , \displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=\frac{p\phi_1(p)\phi_3(p)\phi_4(p)\phi_6(p)\phi_{12}(p)}{2}+1} $$

where $p>2$ and $\phi_n$ is the $n^{th}$ cyclotomic polynomial.

  • $\begingroup$ I get 8714 (both with my formula and explicitly) for $n=143$. $\endgroup$ – Hagen von Eitzen Oct 9 '12 at 21:36
  • $\begingroup$ @Hagen von Eitzen: Of course you are right. I get the same with my formula. I corrected my mistake. Thanks. $\endgroup$ – P.. Oct 9 '12 at 21:42

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.