Fórmula de demostración de la función totiente de Euler

Question

Esta pregunta está motivada por el comentario de lhf aquí .

"Sería bueno relacionar esta fórmula con la cartografía natural $U_{mn} \to U_m \times U_n$ demostrando que el núcleo tiene un tamaño $d$ y la imagen tiene el índice $\varphi(d)$ ."

Aquí, $U_k$ denota el grupo de unidades del anillo $\mathbb{Z} / k \mathbb{Z}$ siempre que $k$ es un número entero positivo.

Estoy tratando de probar la fórmula $$ \varphi(mn) = \varphi(m)\varphi(n) \frac{d}{\varphi(d)} $$ considerando el mapa natural $\eta\colon U_{mn} \to U_m \times U_n$ (es decir, el mapa que envía $\overline{x} \mapsto (\overline{x},\overline{x})$ donde la barra denota la reducción mod $mn$ , $m$ o $n$ respectivamente).

He podido demostrar que el núcleo tiene el tamaño correcto de la siguiente manera:

El núcleo de $\eta$ se compone de los elementos $\overline{x} \in U_{mn}$ con $x \equiv 1 \bmod m$ y $x \equiv 1 \bmod n$ . Los números enteros $x$ que satisfacen estas condiciones son las de la forma $x = \frac{mn}{d}k + 1$ para $k \in \mathbb Z$ . Por otro lado, cualquier número entero $x$ es relativamente primo de $mn$ y por lo tanto da y elemento $\overline{x} \in U_{mn}$ . Por lo tanto, $\ker \eta$ consiste en el $d$ elementos distintos $\overline{x}$ , donde $x = \frac{mn}{d}k + 1$ y $k \in \{1,\ldots,d\}$ .

Una vez que se ha demostrado que la imagen tiene índice $\varphi(d)$ el primer teorema de isomorfismo da $$ \frac{U_{mn}}{\ker \eta} \cong Im(\eta), $$ y así $$ \frac{\varphi(mn)}{d} = \frac{|U_{mn}|}{|\ker \eta|} = |Im(\eta)| = \frac{|U_m \times U_n|}{|U_m \times U_n:Im(\eta)|} = \frac{\varphi(m)\varphi(n)}{\varphi(d)}, $$ o $$ \varphi(mn) = \varphi(m)\varphi(n) \frac{d}{\varphi(d)}. $$

Tengo problemas para mostrar que la imagen tiene el índice correcto.

Me he dado cuenta de que $\eta(\overline{x}) = \eta(\overline{x + \frac{mn}{d}})$ , por lo que la imagen se compone de las imágenes de los elementos $\overline{x}$ con $1 \leq x < \frac{mn}{d}$ . Sin embargo, no estoy seguro de que esto vaya a ninguna parte. ¿Alguna sugerencia?

Answer 1

Ajustaré un poco su notación, utilizando $x\in U_{mn}$ para un elemento invertible de $\mathbb{Z}/mn\mathbb{Z}$ , utilizando $\bar x\in U_m$ para la clase de residuo de $x$ modulo $m$ y utilizando $\tilde x \in U_n$ para la clase de residuo de $x$ modulo $n$ .

La imagen de su mapa $x \mapsto (\bar x,\tilde x)$ es generalmente menor que $U_m \times U_n$ porque $\bar x$ y $\tilde x$ será siempre el mismo módulo $d$ . Primero elegimos un sistema de residuos reducido $\{a_1=1, a_2, \ldots, a_{\varphi(d)}\}$ modulo $d$ de los elementos $U_{n}$ y considera las imágenes de los mapas $f_i: x \mapsto (\bar x, a_i\tilde x)$ . (Tenga en cuenta que cada $a_i$ es invertible módulo $n$ .) Está claro que las imágenes de estos mapas son disjuntas, tienen el mismo tamaño, y que estamos estudiando el caso especial $f_1:x \mapsto (\bar x, \tilde x)$ . De hecho, la unión de estas imágenes es toda $U_m \times U_n$ como ahora mostramos.

Tome cualquier $(y,z) \in U_m \times U_n$ . Demostramos que es igual a algún $f_i(x)$ donde $a_i \equiv zy^{-1} \pmod{d}$ . Por una ligera generalización del Teorema del Resto Chino, existe un único $x$ modulo $\frac{mn}{d}$ tal que $$x \equiv y \pmod{m}\qquad \qquad \text{and} \qquad \qquad x \equiv z{a_i}^{-1} \pmod{n}.$$ Entonces $f_i(x)=(\bar x, a_i \tilde x) =(y,z)$ . (De hecho, el $d$ preimágenes de $(y,z)$ son los elementos $x+\frac{mn}{d} k$ con $0 \leq k \leq d-1$ .)

Se requiere una generalización del Teorema del Resto Chino porque $m$ y $n$ compartir el factor $d$ . Estos sistemas de congruencias tienen solución siempre que sean compatibles módulo $d$ y esta solución es única módulo $\rm{lcm}(m,n)=\frac{mn}{d}$ . Nuestro sistema es compatible modulo $d$ ya que $y \equiv z {a_i}^{-1} \pmod{d}$ .

Así, el índice de la imagen de $x \mapsto (\bar x, \tilde x)$ es $\varphi(d)$ .

Answer 2

Jonas Kibelbek demostró directamente que el índice de la imagen de $\eta$ es $\phi(d),$ y a continuación se presenta una alternativa demostrando una secuencia exacta, que espero pueda aclarar un poco el asunto.

La secuencia exacta que quiero probar es

$$0\rightarrow \text{Ker}(f)\rightarrow U_{mn}\overset{f}{\rightarrow}U_m\times U_n\overset{g}{\rightarrow} U_d\rightarrow0,$$

donde $f(x+mn\mathbb Z)=(x+m\mathbb Z, x+n\mathbb Z),$ y $g(x+m\mathbb Z, y+n\mathbb Z)=xy^{-1}+d\mathbb Z$ (Aquí la inversa se toma como módulo $d$ ).
Prueba:
En primer lugar, $\forall (a+d\mathbb Z)\in U_d,$ tenemos que $g(a+m\mathbb Z, 1+n\mathbb Z)=(a+d\mathbb Z),$ así que $g$ es suryente. Además, está claro que $g\circ f$ desaparece. Por el contrario, si $(x+m\mathbb Z, y+n\mathbb Z)\in U_m\times U_n$ es tal que $x\equiv y\pmod d,$ entonces, por una ligera generalización del teorema chino rmainder, como en la respuesta de Kibelbek, $\exists z$ tal que $\begin{cases}z\equiv x\pmod m\\z\equiv y\pmod n\end{cases}.$ Por lo tanto, la secuencia es exacta. Q.E.D.

P.D. Esta secuencia es en esencia la secuencia en esta respuesta Con algunas reducciones y modificaciones; marco esta respuesta como CW, ya que no hay nada nuevo en esta respuesta.