Función totient de Euler suma de divisores. Teorema 2.2 Apostol

Question

Demuestra que : Si $n\ge 1$, entonces $\sum_{d|n}\phi(d)=n$.

Sea $S$ el conjunto $\{1,2,...,n\}$. Distribuimos los enteros de $S$ en conjuntos disjuntos de la siguiente manera. Para cada divisor $d$ de $n$, sea

$A(d) = \{k \in S :(k,n) = d\}$

Es decir, $A(d)$ contiene los elementos de S que tienen el mcd d con n. Los conjuntos $A(d)$ forman una colección disjunta cuya unión es S. Por lo tanto, si $f(d)$ denota el número de enteros en $A(d)$ tenemos $\sum_{d|n}f(d)=n$

No entiendo por qué la suma de $f(d)$ es igual a $n$. ¿Puede alguien explicar esto?

Answer 1

Los elementos de $A(d)$ son los números $k$ en el intervalo $[1, n]$ (es decir, el conjunto $S$) tales que $\gcd(k, n) = d$. Si $k$ es un tal número, entonces $k = d\ell$ para algún $\ell \in [1, n/d]$ coprimo con $n/d$. Hay $\varphi(n/d)$ tales $\ell$ en el intervalo $[1, n/d]$. Por lo tanto, el número de elementos en $A(d)$ es $\varphi(n/d)$.

Los $A(d)$ son mutuamente disjuntos, y su unión es el conjunto $S=\{1, 2, 3, \dots, n\}$. Se sigue que $$\sum_{d|n} \varphi(n/d) = n. \tag{1}$$ Pero como $d$ varía entre los divisores de $n$, lo hace también $n/d$. Se sigue que $$\sum_{d|n} \varphi(n/d) = \sum_{d|n} \varphi(d). \tag{2}$$ Por (1), la suma en el lado izquierdo de (2) es igual a $n$. Se sigue que la suma en el lado derecho también es $n$.

Answer 2

Consideramos números racionales

• 1/n,2/n,...,n/n

• Claramente hay n números en la lista, obtenemos una nueva lista reduciendo cada número en la lista anterior a su forma más simple; es decir, expresamos la lista anterior como un cociente de enteros primos relativos. El denominador de los números en la nueva lista será un divisor de n. Si d divide a n, exactamente phi(d) de los números tendrán a d como su denominador (esto es el significado de forma más simple). Por lo tanto, hay (suma de phi(d)) en la nueva lista. Como las dos listas tienen el mismo número de términos, obtenemos el resultado deseado.

Answer 3

Me gusta la prueba de Gauß: para cada $d\mid n$, tenemos $\phi (d)$ generadores para $C_d$, donde $C_d$ es el grupo cíclico de orden $d$. Esto es porque, si $\langle g\rangle = C_d$, entonces $\langle g^k\rangle=C_d$ si y solo si $\gcd(k,d)=1$.

Dado que cada elemento de $C_n$ genera un subgrupo cíclico, y cada $C_d \le C_n$ es generado por algún elemento de $C_n$, se sigue la afirmación.

Answer 4

Aquí hay otro enfoque para resolver este problema si estás familiarizado con grupos cíclicos aunque es equivalente a los enfoques dados en otras respuestas. Pero conocer la interdependencia de las disciplinas matemáticas siempre es beneficioso.

Sea $G(a)$ el grupo cíclico generado por el elemento $a$ de orden $n$. Por el teorema fundamental de grupos cíclicos sabemos que para cada divisor $k$ de $n$, $G(a)$ tiene exactamente un subgrupo de orden $k$ - es decir, $G(a^{\frac{n}{k}})$. Además, sabemos que $G(a^k) = G(a)$ si y solo si $mcd(n,k) = 1$.

Ahora, si $d$ divide a $n$, entonces hay exactamente un subgrupo de orden $d$ y sea $G(b)$. Entonces, cada elemento de orden $d$ genera $G(b)$. Pero $G(b^k) = G(b)$ solo si $mcd(k,d)=1$. Por lo tanto, el número de elementos de orden $d$ es $\phi(d)$.

Ahora, si el número total de elementos en el grupo cíclico dado es $n$, entonces por el teorema fundamental de grupos cíclicos, $$\sum_{d|n} \phi(d) = n$$

Answer 5

Vamos a construir el mismo conjunto $S_d=\{x: 1\leq x\leq n$ y $gcd(x, n)=d\}$ de una manera diferente y descubrirlo. De esta forma, creo que se pueden apreciar todos los detalles. Aunque se pueda argumentar que algunos de estos hechos no necesitan ser demostrados porque ya son claros en su definición. Pero como he visto, la mayoría de las personas no pueden estar de acuerdo, al principio, en lo obvio de esto.

Tomemos $A_d=\{x: 1\leq x\leq \frac{n}{d}$ y $gcd(x,\frac{n}{d})=1\}$. Entonces, por supuesto, $\mid A_d\mid =\varphi(\frac{n}{d})$ ya que esa es realmente la definición de $\varphi$. Ahora consideremos el conjunto $B_d=\{x: x=d \cdot y$, $\forall y\in A_d\}$. Una vez más, por supuesto, $\mid B_d\mid =\varphi(\frac{n}{d})$. Para cualquier $x \in B_d$, tanto $gcd(x, n)=d$ como $1\leq x\leq n$ son verdad. Por lo tanto, $B_d \subseteq S_d$. Si hubiera un $m \in S_d$ pero $m \notin B_d$, entonces eso significaría que $\frac{m}{d}∉A_d$. Pero eso no puede ser posible ya que $\frac {m}{d}(=x)$ satisface $1\leq x\leq \frac {n}{d}$ y $gcd(x,\frac {n}{d})=1$, ambas condiciones para estar en $A_d$. Por lo tanto, $B_d=S_d \Longrightarrow\mid S_d\mid =\mid B_d\mid =\varphi(\frac {n}{d})$. Ahora consideremos el conjunto $S= \bigcup{S_d}$. Este conjunto debe incluir todos los enteros de $1$ a $n$. Porque si no lo hiciera, entonces existiría un $x$ tal que $1\leq x\leq n$ pero $gcd(x,n)=k$ que no es uno de los $d$ que hemos considerado. Pero eso no es posible. Así que se sigue que, $\mid S\mid =\sum{\mid S_d \mid } =\sum{\varphi(\frac{n}{d})}= \sum{\varphi(d)}=n$.