Pregunta sobre el sistema de reducción de residuos

Question

Supongamos que $\gcd(m,n) = 1$ . Demostrar que si $x$ asume todos los valores en un sistema de residuos reducido módulo $m$ y $y$ asume todos los valores en un sistema de residuos reducido módulo $n$ entonces $nx+my$ asume todos los valores en un sistema de residuos reducido módulo $mn$ .

$\{r_1, r_2, \ldots , r_s\}$ forma un sistema de residuos reducido modulo $m$ si

• $\gcd(r_i, m) = 1$ para cada $i$

• $r_i \neq r_j$ siempre que $i \neq j$

• para cada número entero $n$ relativamente primo a $m$ corresponde un $r_i$ tal que $n \equiv r_i \pmod m$

Agradezco su ayuda.

Answer 1

Un sistema de residuos reducido modulo $mn$ es cualquier conjunto de $\varphi(mn) = \varphi(m) \varphi(n)$ enteros que son incongruentes módulo $mn$ y cada una de ellas es coprima con $mn$ .

( $\varphi(mn)$ es la función totiente de Euler, que es multiplicativa).

Hay $\varphi(m) \varphi(n)$ distintas formas de formar la suma $nx + my$ eligiendo $x$ para ser uno de los $\varphi(m)$ enteros en un sistema de residuos reducido modulo $m$ y elegir $y$ para ser uno de los $\varphi(n)$ enteros en un sistema de residuos reducido modulo $n$ . Tenemos que demostrar que estos $\varphi(m) \varphi(n)$ distintas formas de formar la suma producen $\varphi(m) \varphi(n)$ enteros incongruentes módulo $mn$ cada uno de los cuales es coprimo con $mn$ .

En primer lugar, supongamos que gcd $(nx + my, mn) = d > 1$ . Desde $d|(nx+my)$ debe ser el caso que si $d|m$ entonces $d|nx$ pero esto es imposible ya que gcd $(m, n) = 1$ y gcd $(m, x) = 1$ . Del mismo modo, ya que $d|(nx+my)$ debe ser el caso que si $d|n$ entonces $d|my$ pero esto es imposible ya que gcd $(m, n) = 1$ y gcd $(n, y) = 1$ . Por lo tanto, no podemos tener $d|m$ o $d|n$ pero esto es una contradicción ya que $d|mn$ . Por lo tanto, $d > 1$ es imposible, por lo que cada suma $nx + my$ es coprima con $mn$ .

A continuación, supongamos que $nx_i + my_i$ y $nx_j + my_j$ son dos formas cualesquiera de formar la suma, es decir $x_i \neq x_j$ en un sistema de residuos reducido modulo $m$ y/o $y_i \neq y_j$ en un sistema de residuos reducido modulo $n$ . Tenemos que demostrar que $nx_i + my_i$ y $nx_j + my_j$ debe ser entonces incongruente módulo $mn$ . Demuéstralo por contradicción. Supongamos que son congruentes módulo $mn$ . Entonces su diferencia es divisible por $mn$ por lo que para algún número entero $k$ debemos tener

$n(x_i - x_j) + m(y_i - y_j) = kmn$

Desde $m$ divide ambos $m(y_i - y_j)$ y $kmn$ también debe dividir $n(x_i - x_j)$ pero esto es imposible ya que $m$ tampoco puede dividir $n$ o $x_i - x_j$ . Esta contradicción demuestra que las dos sumas no pueden ser congruentes módulo $mn$ .

Por lo tanto, hemos demostrado que el $\varphi(m) \varphi(n)$ distintas formas de formar la suma $nx + my$ producir $\varphi(m) \varphi(n)$ enteros incongruentes módulo $mn$ cada uno de los cuales es coprimo con $mn$ es decir, $nx + my$ debe asumir todos los valores de un sistema de residuos reducido módulo $mn$ .

Answer 2

Una pista: A partir de la definición de Sistema de reducción de residuos ya que ambos $x$ y $y$ forman un sistema de residuos reducido modulo $m$ y $n$ , tienen $\phi(m)$ y $\phi(m)$ respectivamente y también los dos elementos $\gcd(x,m)=1$ y $\gcd(y,n)=1$

Ahora mira $nx + my \pmod {mn}$ , si $nx +my$ es siempre coprima a $mn$ y no hay dos valores para $nx + my$ son congruentes módulo a módulo $mn$ entonces forma un sistema de residuos reducido modulo $mn$ . Recuerde $\gcd(m,n)=1$ , $\gcd(x,m)=1$ y $\gcd(y,n)=1$ ...

¿Puede continuar?