Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@MJD: thanks a lot for the excellent editing and formatting – user43255 Oct 9 '12 at 18:44
I didn't get exactly the question, could you be a bit more explicit please? – Giovanni De Gaetano Oct 9 '12 at 18:47
@GiovanniDeGaetano That was my fault. I have tried to make the question more explicit: OP wants to compute the indicated sum. – MJD Oct 9 '12 at 18:48
@GiovanniDeGaetano:sir if you need any clarifications for the question ,please comment. Also,I think answer could involve use of the totient function. – user43255 Oct 9 '12 at 18:49
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. – 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$.

share|cite|improve this answer

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:


share|cite|improve this answer

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

share|cite|improve this answer
:i see a recursion here – user43255 Oct 9 '12 at 19:03
@user43255, could you please elaborate a bit more? – lab bhattacharjee Oct 9 '12 at 19:07
: 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 – user43255 Oct 9 '12 at 19:09
Nice use of symmetry. – André Nicolas Oct 9 '12 at 20:36
@AndréNicolas, thanks. But unfortunately, it didn't lead me much further. – 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)$.

share|cite|improve this answer

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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