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