¿Cuál es la suma de totatives de n(números naturales $ \lt n$ coprime a $n$ )?

Question

Misma pregunta que en el título:

¿Cuál es la suma de los números naturales que son coprime a $n$ e se $ \lt n$ ?

Sé cómo contar el número de ellos a través de Euler de la función, pero cómo calcular la suma?

Answer 1

Vamos a llamar a esta función $f$. Entonces $$f(n) = \sum_{i = 1}^{n - 1} \delta_{1}^{\gcd(i, n)} i = \frac{n \phi(n)}{2},$$ where $\delta$ is the Kronecker delta function and $\phi$ is Euler's totient function. Clearly if $n$ is prime, then $f(n) = T_{n - 1}$, where $T_n$ is the $$n ésimo número triangular.

Trabajar un par de ejemplos. Voy a hacer dos: $f(6) = 1 + 5 = \frac{6 \times 2}{2} = 2$$f(8) = 1 + 3 + 5 + 7 = \frac{8 \times 4}{2} = 16$.

Ahora, yo no averiguarlo por mi cuenta. La respuesta viene de aquí: Sloane del OEIS A023896.

En cuanto a por qué me gusta la función delta de Kronecker, que porque soy un demonio.

Answer 2

Suponga $n>2$. Entonces, si $n/2$ es un número entero, entonces $n/2$ no es, ciertamente, un totative. Ahora es fácil ver que si $k$ es un totative, a continuación, $n-k$ es también un totative. Así que podemos dividir $\phi(n)$ totatives en $\phi(n)/2$ pares de $\{k,n-k\}$, cada uno contiene dos elementos distintos (porque $n/2$ no es un totative) que se suma a $n$. De modo que la suma de todos los totatives es $n\cdot\phi(n)/2=\frac{n\phi(n)}{2}$