9
$\begingroup$

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

  • 0
    See my answer. It depends on the prime factorization of $n$. For $n=10000000=2^7\cdot 5^7$ the value is $$\frac{1+\frac{2^{15}+1}{3}\frac{7^{15}+1}{8}}{2}$$2012-10-10

5 Answers 5

4

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

2

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$

1

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

  • 0
    Well, it gives easy way to compute at powers of $p$, and elsewhere. (I have not written down anything, just thought about it while driving.)2012-10-10
1

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

0

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.

  • 0
    @Hagen von Eitzen: Of course you are right. I get the same with my formula. I corrected my mistake. Thanks.2012-10-09