# How can I compute the sum of ${m\over\gcd(m,n)}$?

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

-
@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:

$$S(n)=\frac{1+g(n)}2$$

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

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

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:

$$\sum_{m=1}^{12}\frac{m}{gcd(m,n)}=1+\frac{2}{2}+\frac{3}{3}+\frac{4}{4}+\frac{5}{1}+\frac{6}{6}+\frac{7}{1}+\frac{8}{4}+\frac{9}{3}+\frac{10}{2}+\frac{11}{1}+\frac{12}{12}=39$$

-

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

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

-

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.

-
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