Suma de $\gcd$

Question

Me pidieron que evaluara la suma $\sum_{k = 1}^n \frac{n}{\gcd(n,k)}$ en términos de la factorización en primos de $n$ . Sé que hay $\phi(n)$ números enteros $k < n$ tal que $\gcd(n,k) = 1$ así que intenté escribir $\sum_{k = 1}^n \frac{n}{\gcd(n,k)} = \phi(n)n + 1 + S$ donde $S$ es la contribución de los términos donde $k < n$ y $\gcd(n,k) > 1$ .

También he intentado evaluar $\sum_{k = 1}^n \frac{\text{lcm}(n,k)}{k}$ pero fue en vano.

Preferiría una pista antes que una solución completa. Se agradece cualquier ayuda.

Answer 1

Si $G$ es el grupo cíclico de orden $n$ y $G=\langle g\rangle $ , entonces $ord(g^k)=\dfrac{n}{\gcd(n,k)}$ .

Por lo tanto, $$ \sum_{k = 1}^n \frac{n}{\gcd(n,k)} = \sum_{k = 1}^n ord(g^k) = \sum_{d\mid n} \sum_{x \in G, ord(x)=d} d = \sum_{d\mid n} d \phi(d) $$

Para la última suma, véase esta pregunta .