Espectáculo

Question

Mostrar $\sum\limits_{d|n}\phi(d) = n$.

Ejemplo:$\sum\limits_{d|4}\phi(d) = \phi(1) + \phi(2) + \phi(4) = 1 + 1 + 2 = 4$

Me dijeron que esto tiene una prueba simple. El problema es que no puedo pensar en una forma de mostrar esto de una manera simple y directa.

Answer 1

Deje$G=\langle x\rangle$ ser el grupo cíclico de orden$n$ generado por$x$. Entonces, \begin{align} n &= |G| \\ &= \sum_{1\leq d\leq n} |\{\text{elements of order } d\}| \\ &= \sum_{d|n}|\{\text{elements of order } d\}| \end {align} por el Teorema de Lagrange. Pero$G$ tiene un subgrupo cíclico único de orden$d$ para cada$d|n$, es decir,$\langle x^{n/d}\rangle$. Además, cada uno de esos subgrupos tiene$\varphi(d)$ de generadores, entonces$$n = \sum_{d|n}\varphi(d)$ $

Answer 2

Sugerencia: Puede mostrar que$\sum\limits_{d|n}\phi(d) = \sum\limits_{d|n}\phi(\frac{n}{d}) $ pero$\phi(\frac{n}{d})$ son todos los números con GCD de$d$ con$n$. Por lo tanto, la última suma cuenta todos los números hasta$n$ y es igual a$n$.

Answer 3

La prueba más simple que sé es esta:

Considere todas las fracciones adecuadas de la forma$a/n$. Hay$n$ de esos. Cuando considera sus formas reducidas, obtiene fracciones de la forma$b/d$ con$d|n$ y$(b,d)=1$. Por definición, hay$\phi(d)$ de esos. El resultado sigue.

Answer 4

Este es un enfoque:

Considere el polinomio $x^n-1$ como un polinomio sobre los números complejos $\mathbb{C}$. Usted puede ver fácilmente, casi tautologically, que

$$x^n-1=\prod_{d\mid n}\Phi_d(x)\qquad(\ast)$$

donde $\Phi_d(x)$ es el polinomio cuyas raíces son los primitivos $d^{\text{th}}$ raíces de la unidad (es decir, las soluciones a $x^d-1$ que no satisfacen $x^c-1$$0<c<d$).

Pero, reformular la definición, $\Phi_d(x)$ es el polinomio con raíces $e^{\frac{2\pi i r}{d}}$ donde$e^{\frac{2\pi r s}{d}}\ne 1$$0<s<d$. Pero, esto es decir que el$sr\not\equiv 0\mod d$$0<s<d$, o que $d$ $r$ no tienen factores comunes. Ya que sólo necesita preocuparse por $r$, que es menor o igual a $d$ vemos que, de hecho, la se $\phi(d)$ tales raíces de $\Phi_d(x)$.

Esto nos permite concluir que $\deg \Phi_d(x)=\phi(d)$. En efecto, desde el $\Phi_d(x)\mid x^n-1$, e $x^n-1$ no tiene raíces repetidas en $\mathbb{C}$ (coprime a sus derivados) vemos que $\Phi_d(x)$ no tiene raíces repetidas. Por lo tanto, $\deg\Phi_d(x)$ es el número de raíces de $\Phi_d(x)$$\phi(d)$.

Así, mediante la comparación de los grados en $(\ast)$ obtenemos:

$$n=\sum_{d\mid n}\deg\Phi_d(x)=\sum_{d\mid n}\phi(d)$$

Answer 5

Considere el conjunto$[n]=\{1,1,2,\ldots,n\}$ de tamaño$n$. Defina una relación de equivalencia de la siguiente manera$$m\sim m'\iff (m,n)=(m',n)$$ That this is an equivalence relation should be clear. The equivalence classes are of the form $$\widehat m=\{0<m'\leqslant n:(m',n)=d\}$$ where $ d = (m, n) \ mid n$. Now, what is the size of this class? It contains all positive elements $ m '\ leqslant n$ such that $ (m ', n) = d$, or what is the same, all positive elements $$\frac{m'}d\leqslant \frac nd$$ such that $$\left(\frac{m'}{d},\frac nd \right)=1$ $

Esto equivale a$\varphi\left(\dfrac nd\right)$ elementos. Pero hay una clase para cada divisor positivo de$n$, así hemos cancelado nuestro conjunto obteniendo$$n=\sum_{d\mid n}\varphi\left(\dfrac nd\right)$ $

Pero como$d$ se ejecuta a través de todos los divisores de$n$; también lo hace$\dfrac nd$, de modo que$$n=\sum_{d\mid n}\varphi(d)$ $