$$ \sum_{m =1}^n {m\over\gcd(m,n)}$$
Por ejemplo, para 1 es
$${1\over\gcd(1,1)} =1;$$
para 5 es $${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$$
Si define $S(n)$ como su suma:
$$S(n)=\sum_{m=1}^n \frac{m}{(m,n)}$$
entonces demostraremos que $2S(n)-1$ es multiplicativo .
Puedes reescribir la suma como:
$$S(n)=\sum_{d\mid n} \sum_{m=1}_{(m,n)=d}^n \frac{m}{d}$$
Configuración $k=m/d$ , obtenemos:
$$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$$
Así que $$f(d) = \sum_{k=1}_{(k,d)=1}^d k$$
No es difícil demostrar que este $f(1)=1$ y $f(d)=\frac{1}{2}\phi(d)d$ cuando $d>1$ .
Así que tenemos:
$$S(n)=\frac{1}{2}+\frac{1}{2}\sum_{d\mid n} \phi(d)d$$
Ahora $g(n)=\sum_{d|n} d\phi(d)$ es multiplicativa, ya que $n\phi(n)$ es, así que $g(n)$ viene determinada por $$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}$$
Y en general, si $n=\prod p_i^{a_i}$ entonces $$g(n)=\prod \frac{p_i^{2a_i+1}+1}{p_i+1}$$
Y tu suma original es:
$$S(n)=\frac{1+g(n)}2$$
Así, por ejemplo, $$g(12)=g(2^2)g(3^1)= \frac{2^5+1}{2+1}\frac{3^3+1}{3} = 11\cdot 7 = 77$$ Así que cuando $n=12$ su suma es $S(12)=\frac{77+1}{2}=39$ .
Para $n=143$ , $$g(143)=g(11)g(13)=\frac{11^3+1}{11+1}\frac{13^3+1}{13+1} = 111\cdot 157 = 17427$$ y su suma es $S(143)=\frac{17427+1}{2}=8714$ .
Si $\ n=p\ $ es primo, podemos decir
$$\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$$
Pero en general, a pesar de que el número $\,22\,$ aparece varias veces en los primeros números no primos, no parece haber una salida fácil. Por ejemplo:
$$\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$$
Sabemos que $(m,n)=(n-m,n)$ donde $1\le m \le n-1$
y $\frac n {(n,n)}=1$
Así que.., $$\frac m {(m,n)}+\frac{n-m}{(n-m,n)}=\frac m {(m,n)}+\frac{n-m}{(m,n)}=\frac{n}{(n,m)}$$
Si $n$ es impar, $m$ será de hasta $\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)}$
Si $n$ es par, $m$ será de hasta $\frac{n}2$ . Aquí para $$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)}$
Para cada divisor $d|n$ habrá algunos $m$ tal que $\gcd(m,n)=d$ es decir, precisamente las de la forma $m=kd$ con $\gcd(k,\frac nd)=1$ y $1\le k\le \frac nd$ . Tenga en cuenta que con $$\tag1f(n):=\sum_{1\le k\le n\atop \gcd(k,n)=1}k$$ tenemos $$F(n)=\sum_{d|n}f(d)$$ como su función en cuestión. Como $\gcd(k,n)=\gcd(n-k,n)$ los sumandos en $(1)$ pueden emparejarse en $\frac{\phi(n)}2$ sumandos $k+(n-k)=n$ . Se comprueban los casos especiales $n=1$ y $n=2$ por separado para ver que $$f(n)=\begin{cases}\frac{n\phi(n)}2&n>1\\1&n=1\end{cases}$$ retenciones. La función $\tilde f(n)=n\phi(n)$ sería una función multiplicativa, por lo que también lo sería $\tilde F(n)=\sum_{d|n}d\phi(d)$ . Así, para calcular $\tilde F(n)$ basta con conocer los valores a potencias primos. Tenemos para $p$ primo y $k\ge 1$ $$p^k\phi(p^k)=\left(1-\frac1p\right)p^{2k},$$ de ahí $$\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}.$$ Así, finalmente tenemos $$\tag2F(n)=\frac12 (\tilde F(n)+1) = \frac12+\frac12\prod_{p|n}\left(1+p\cdot \frac{p^{2k}-1}{p+1}\right).$$
Observación: A partir de la expresión $p\cdot \frac{p^{2k}-1}{p+1}$ no es sorprendente que los polinomios ciclotómicos desempeñen un papel para $F(p^k)$ .
Continuando con la respuesta de DonAntonio examinemos el caso en el que $n=pq $ con $p>q$ primos.
En este caso tenemos (utilizando la inclusión $-$ exclusión): $$ \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} \ . $$
Por ejemplo, para $n=22$ tenemos que $\displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=167 \ }$ y para $n=13\cdot 29=377$ tenemos que $\displaystyle{\sum_{m=1}^{n}\frac{m}{\gcd(m,n)}=63821 \ .}$
Para ir un poco más lejos tenemos con el mismo método lo siguiente:
$$ \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} $$
donde $p>2$ y $\phi_n$ es el $n^{th}$ polinomio ciclotómico.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
