Explicación sobre Teorema del sistema reducido del residuo

Question

Necesito una explicación de la siguiente teorema

Teorema 3-7 $If (m,n)=1$ $\varphi(mn)=\varphi(m)\varphi(n)$

Prueba: Tomar números enteros m,n con $(m,n)=1$, y cuenta los números de la forma $mx+ny$. Si podemos restringir los valores que x y y suponga que estos números forman una reducción de los residuos del sistema (mod mn), debe de ser $\varphi(mn)$ de ellos. Pero su número es también el producto del número de valores que x asume y el número de valores que y asume. Claramente, para $mx+ny$ a ser el primer para m, es necesario que el $(m,y)=1$, y de la misma manera debemos tener $(n,x)=1$. Por el contrario, si estas dos condiciones se cumplen, entonces $(mx+ny,mn)=1$, ya que en este caso cualquier divisor primo de m o de n, divide exactamente uno de los dos términos en$ mx+ny$. Por lo tanto vamos a x el rango a través de una reducción de los residuos del sistema (mod n), decir $x_1,...,x_{\varphi(n)}$, y sea y ejecutar a través de una reducción de los residuos del sistema (mod m), decir $y_1,...,y_{\varphi(m)}$. Si para algunos índices $i,j,k,l$ hemos

$$mx_i+ny_j \equiv mx_k + ny_l (mod\text{ } mn)$$

entonces

$$m(x_i-x_k)+n(y_j-y_l)\equiv 0(mod \text{ } mn)$$

Desde la divisibilidad por mn implica la divisibilidad por m, tenemos

$$m(x_i-x_k)+n(y_j-y_l) \equiv 0(mod\text{ } m)$$ $$n(y_j-y_l) \equiv 0 (mod\text{ } m)$$ $$y_j \equiv y_l(mod\text{ } m)$$

de dónde $j =l$. Del mismo modo, $i=k$. Por lo tanto los números de $mx+ny$ así formados son incongruentes (mod mn). Ahora vamos a un ser cualquier número entero primer a mn: en particular, $(a,m)=1$$(a,n)=1$. Entonces el teorema de 2-6 muestra que existen números enteros X,Y (no necesariamente en la opción de reducción de residuos de los sistemas)) tal que $mX+nY=a$, de donde también se $mX+nY \equiv a(mod\text{ } mn)$. Desde $(m,Y)=(n,X)=1$, hay un $x_i$ tal que $X\equiv x_i(mod n)$ y hay un $y_j$ tal que $Y \equiv y_j(mod\text{ } m)$. Esto significa que no son enteros $k,l$ tal que $X=x_i+kn$, $Y=y_j+lm$. Por lo tanto,

$$mX+nY=m(x_i+kn)+n(y_j+lm)\equiv mx_i+ny_j \equiv a(mod\text{ } mn)$$

Por lo tanto, como x y y ejecutar más de reducción fija de sistemas de residuos (mod n) y (mod m), respectivamente, $mx+ny$ se ejecuta a través de una reducción de los residuos del sistema (mod mn), y la prueba está completa.

El libro estaba haciendo un muy buen trabajo explicando los teoremas de una manera fácil hasta el último. No podía odiar a que la prueba más. Se evita un montón de cosas que son difíciles de entender. He subrayado algunas de las cosas que no entendía, pero todavía hay más. Yo estaría encantado si alguien de forma simplificada o explica mejor prueba de este teorema. La primera cosa que me gustaría entender es que cuando se refieren a la x que van más un residuo del sistema. ¿Qué significa eso?. ¿Eso significa que x es congruente con algún término específico residuo sistema mod n?

Answer 1

Primero voy a tratar de ayudarle con el dado prueba y, a continuación, voy a mostrar una más fáciles de la prueba.

La primera parte en negrita es sólo una introducción a lo que el autor trata de demostrar. Para la segunda parte tenga en cuenta que si $p \mid m$$p \not \mid ny \implies p \not \mid ny + mx$. Argumento Similar para $x$ muestra que $(ny + mx, mn) = 1$. Y para la tercera parte tenga en cuenta que por Bezout del Lexema tenemos que existen enteros $x,y$ s.t. $mx + ny = 1 \implies m(ax) + n(ay) = a \implies mX + nY = a$. Obviamente, esto demuestra la existencia de $X$$Y$. Supongo que el resto de la prueba es comprensible para usted.

De todos modos esta prueba parece bastante malo. En realidad uno puede primera prueba de que $\phi(n) = n \prod_{p \mid n} \left(1 - \frac 1p \right)$ por la Inclusión-Exclusión Principio y, a continuación, el multiplicativity es trivial. También si usted se presentó a Anillo de Teoría (Teorema del Resto Chino), a continuación, hay una muy corto y fácil de la prueba.

Answer 2

La prueba funciona de la siguiente manera. Deje $\,U_m,\,U_m,\, U_{mn}$ reducción de residuos de los sistemas de mod $\,m,n,mn.\,$

Nos muestran que si $\,x\in U_n,\, y\in U_m$ $\,mx+ny\in U_{mn}\,$ e esta asignación se obtiene un bijection $\, U_m \times U_n \cong U_{mn}.\,$ Comparando cardinalidades llegamos $\,\varphi(m)\varphi(n) = \varphi(mn).\,$ Nota: cuando escribimos $\,z\in U_i\,$ nos referimos a $\,z\equiv z'\,$ algunos $\,z'\in U_i$

En primer lugar mostramos que $\,mx+ny\,$ se encuentra en $\,U_{mn},\,$, es decir, coprime a $\,mn.\,$ Nota

$$(mx+ny,m) = (ny,m) = (y,m) = 1\ \ {\rm by}\ \ y\in U_m$$

$$(mx+ny,n) = (mx,n) = (x,n) = 1\ \ {\rm by}\ \ x\in U_n$$

Desde $\,mx+ny\,$ es coprime a $\,m,n\,$ es coprime a sus lcm = producto, por lo que es en $U_{mn}$

A continuación se muestra el mapa es inyectiva, es decir,$1$-$1$. Si $\ mX+nY = mx+ny\ $ $\, m(X-x) = n(y-Y)\,$ $\,m,n\,$ coprime tenemos $\,m\mid y-Y,\,$ $n\mid X-x,\,$ así $\, X\equiv x\pmod n,\,$ $\,Y\equiv y\pmod m$

Finalmente mostramos el mapa es surjective (a). Deje $\,a\in U_{mn}$. Por Bezout $\, mx + ny = a\,$ algunos $\,x,y.\,$, por Lo que, mod $\,n\!:\ mx\equiv a,\,$ $\,x \equiv m^{-1}a,\,$ donde $\,m^{-1}$ existe $\,(m,n)=1.\,$ $\,(x,n) = 1,\,$ else $\,p\mid x,n\,$ $\,p\mid a= mx\!+\!ny,\,$ contra $\,(a,n)=1$ $\,(a,mn)=1.\,$ Desde $\,(x,n)=1\,$ deducimos $\,x\,$ es congruente con algunos $\,x_i\in U_n.\,$ Similarmente $\,y\equiv y_i \in U_m.\,$ Su última ecuación muestra $\,mx_1+n y_1 = m(x+jn)+n(y+kn)\equiv mx+ny\equiv a\pmod{mn},\,$ $\,(x_i,y_j)\in U_n\times U_m\,$ mapas a $\,a\in U_{mn},\,$ por lo que el mapa es sobre.

Comentario $\ $ La prueba será mucho más clara cuando se aprende sobre el anillo de la teoría de la vista de la CRT = Teorema del Resto Chino. Entonces lo que sigue es simplemente de

$$\Bbb Z/mn\, \cong\, \Bbb Z/m \oplus \Bbb Z/n\ \Rightarrow\ U(\Bbb Z/mn)\, \cong\, U(\Bbb Z/m) \times U( \Bbb Z/n) $$

donde $\,U(R)\,$ denota el grupo de unidades (invertibles) de $R$.