Hay una directa, en la escuela primaria prueba de $n = \sum_{k|n} \phi(k)$?

Question

Si $k$ es un número natural positivo, a continuación, $\phi(k)$ indica el número de números naturales a menos de $k$, que es el primer a $k$. He visto pruebas de que $n = \sum_{k|n} \phi(k)$ que básicamente particiones $\mathbb{Z}/n\mathbb{Z}$ en subconjuntos de elementos de orden $k$ (de los cuales hay $\phi(k)$-muchos) como $k$ rangos de divisores de a $n$.

Pero todo lo que sabemos acerca de la $\mathbb{Z}/n\mathbb{Z}$ viene de la escuela elemental a la teoría de números (división con resto, bezout relaciones de divisibilidad), por lo que esta relación debe ser comprobable, sin invocar la estructura del grupo $\mathbb{Z}/n\mathbb{Z}$. ¿Alguien tiene un agradable, claro, la prueba de que se evita la $\mathbb{Z}/n\mathbb{Z}$?

Answer 1

Escribir las fracciones $1/n,2/n,3/n \dots ,n/n$ en la forma más simple y se puede observar que cada fracción es de la forma $s/t$ donde $t$ divide $n$$(s,t)=1$. Por lo que el número de las fracciones es el mismo que $\sum_{k|n}{\phi(k)}$ que es igual a $n$.

Answer 2

Claramente $n$ cuenta el número de elementos en el conjunto $ \{1,\ldots,n\}$. Esto sugiere que para obtener una combinatoria prueba debemos contar el número de elementos de este conjunto en una manera diferente y obtener $\sum_{k \mid n} \varphi(k)$.

Para $k \mid n$, vamos a $S(k)$ el conjunto de $m \in \{1,\ldots,n\}$ tal que $\gcd(m,n) = k$. Ya que para todos $m \in \{1,\ldots,n\}$, $\gcd(m,n)$ es un divisor de a$n$,$\sum_{k \mid n} \# S(k) = n$.

Ahora me reclama que para todos los $k \mid n$, $\# S(k) = \varphi(\frac{n}{k})$. Esto implica el resultado porque como $k$ corre a través de todos los divisores positivos de $n$ lo hace $\frac{n}{k}$. Se puede ver cómo establecer esta igualdad?

Answer 3

Considerar todas las fracciones propias de la forma $a/n$. Hay $n$ de las personas. Cuando se considere la posibilidad de su reducción de las formas de obtener las fracciones de la forma$b/d$$d|n$$(b,d)=1$. Hay $\phi(d)$ de las personas. El resultado de la siguiente manera.