Prueba alternativa de:$n = \sum_{d|n} \phi(d)$ que es la suma de la función de Phi de Euler sobre los divisores

Question

Ejercicio :

Utilizando el hecho de que el número de los generadores de $\mathbb Z_d$$\phi(d)$, muestran que : $$n = \sum_{d|n} \phi(d)$$ donde $\phi$ es de Euler de la función que se define para cada entero positivo $n$ a partir de la fórmula $\phi(n)=s$ donde $s$ es el número de enteros positivos menores o iguales de $n$, que es el primer a $n$.

PREGUNTA : me han demostrado la relación dada de la siguiente manera, mientras que el estudio pero no estoy seguro de si podría ser menor o alternado, con el hecho dado en el ejercicio acerca de $\mathbb Z_d$. Agradecería cualquier aclaración o sugerencia.

Deje $S_d = \left\{{m \in \mathbb Z: 1 \le m \le n, \gcd \left\{{m, n}\right\} = d}\right\}$. Es decir, $S_d$ es todos los números menores o iguales a $n$ cuyas $\text{gcd}$$n$$d$.

Ahora, a partir de la división por $\text{gcd}$ para Coprime Enteros tenemos:

$$\gcd \left\{{m, n}\right\} = d \iff \dfrac m d, \dfrac n d \in \mathbb Z: \dfrac m d \perp \dfrac n d$$

Por lo que el número de enteros en $S_d$ es igual al número de enteros positivos no mayores de $n/d$, que es el primer a $n/d$.

Por definición de la función de Euler declaró en el ejercicio, esto es :

$$|S_d| = \phi\bigg(\frac{n}{d}\bigg)$$

A partir de la definición de la $S_d$, se deduce que para todos los $1≤m≤n$ :

$$\exists d | n: m \in S_d$$

lo que conduce a :

$$\displaystyle \left\{{1, \ldots, n}\right\} = \bigcup_{d |n} S_d$$

De la forma en que me definen $S_d$ a pesar de que, se desprende también que son pares distintos.

Ahora, a partir de Corolario a la Cardinalidad del Conjunto de la Unión, se sigue que :

$$n=\sum_{d|n} |S_d| = \sum_{d|n} \phi \left({\dfrac n d}\right)$$

Pero con el hecho de que la suma de los divisores es igual a la suma de los cocientes, que se derivan de la fórmula quería :

$$\sum_{d | n} \phi \left({\dfrac n d}\right) = \sum_{d |n} \phi \left({d}\right)$$

Answer 1

La idea es que desee contar los elementos en$\mathbb{Z}_{n}$ de dos maneras. Primero, notamos que$|\mathbb{Z}_{n}| = n$. Ahora contamos de una segunda manera. Recuerde que por cada$1\leq d|n$, existe un subgrupo único de orden$d$ en$\mathbb{Z}_{n}$, que es precisamente$\mathbb{Z}_{d}$. Además, estos son los únicos subgrupos de$\mathbb{Z}_{n}$. Ahora cuente los generadores de$\mathbb{Z}_{d}$; hay$\phi(d)$ tales generadores. Según el teorema de Lagrange, tenemos que$\langle a \rangle$ es un subgrupo de$\mathbb{Z}_{n}$ para cada$a \in \mathbb{Z}_{n}$. Entonces de hecho:

ps

Answer 2

Lo siento, solo voy a sugerir un método diferente de prueba.

Cada elemento de$Z_n$ genera exactamente un subgrupo cíclico de algún orden$d\mid n$ para algunos$d$. Además$Z_n$ tiene un subgrupo exclusivo de orden$d$ para cada$d\mid n$. Entonces, deje que$D_n$ sea el conjunto de divisores de$n$. Ahora podemos decir que si$\alpha(a,d) : Z_n \times D_n$ es la función de indicador que es 1 cuando$a$ genera un subgrupo de orden$d$ y 0 de lo contrario, entonces$$ n=\sum_{a\in Z_n}1 = \sum_{a\in Z_n}\sum_{d\in D_n}\alpha(a,d) = \sum_{d\in D_n}\sum_{a\in Z_n} \alpha(a,d) = \sum_{d\mid n} \phi(d).$ $