¿Cuál es la forma más tangible de introducir el Teorema del Resto chino? ¿Cuáles son los ejemplos prácticos y realmente interesantes de este teorema? Estoy buscando ejemplos que tengan un impacto real en los estudiantes.
Respuesta
¿Demasiados anuncios?
Yo llame a la CRT la "modular coordenadas teorema".
Si usted tiene un montón de números de $m_1...m_n$, entonces cualquier número $k$ se puede dar un "coordinar" dando la $n$-tupla de sus restos modulo cada $m_i$: $(k \mod m_1,\ ...\ k \mod m_n)$. La pregunta es: ¿se puede determinar de forma única un número de su tupla de coordenadas?
Bueno, por supuesto que no, no se si nuestro número $k$ es cualquier entero arbitrario. Sólo hay $\prod m_i$ posibles tuplas y un número infinito de valores de $k$. De hecho, se puede mostrar que la de coordinar las tuplas son $\prod m_i$-periódico de la siguiente manera. En primer lugar observamos que la tupla de coordenadas de $k$ únicamente determina las coordenadas de $k+1$, ya que se puede obtener de la segunda por la adición de $1$ y teniendo un remanente para cada valor de la tupla de coordenadas de $k$. Siguiente, obviamente, la tupla de coordenadas de $\prod m_i$ $0$ - es congruente a $0$ modulo cualquiera de las $m_i$. Cualquier secuencia que tanto determinista (cada valor sólo depende del valor anterior) y, finalmente, vuelve a su valor inicial es, obviamente, periódico después de ese punto.
Por tanto, si nuestro sistema de coordenadas se reinicia y comienza a repetir después de $\prod m_i$, entonces podemos ciertamente única esperanza para determinar un número $k$ a partir de sus coordenadas si sabemos que $k$ entre $0$$\prod m_i$. Pero, ¿podemos siempre hacer eso? Tal vez algunos números en que rango tienen la misma coordenada.
Primero de todos, te obviamente ejecutar en problemas si el $m_i$ no pares distintos. Imagina si tuviéramos $m_1=m_2=2$. Entonces la coordenada "tupla" de $k$ es en realidad sólo un valor único el resto de $k$ modulo $2$. Ciertamente no se puede identificar de forma única cualquier número entre el $0$ $m_1m_2=4$ con esa información. Si la coordenada es $0$ $k$ podría ser $0$ o $2$, y si es $1$ podría ser $1$ o $3$.
También estamos en problemas si $m_1=2$$m_2=4$, como muestra la tabla siguiente:
Como usted puede ver, hay varios números que comparten coordinar las tuplas. El problema aquí es que, aunque la de coordinar las tuplas son, de hecho, $m_1m_2=8$- periódico, que no es su menor período. También son $4$-periódico y $4$ es el más pequeño período de la coordenada de tuplas. Además, se puede ver que para $k<4$, se puede determinar de forma única a $k$ a partir de sus coordenadas. $4$, dicho sea de paso, pasa a ser el MCM de a$m_1$$m_2$.
Podemos mostrar, en general, que la de coordinar las tuplas modulo $m_1...m_n$ son inyectiva entre el$0$$\mathrm{LCM}(m_1,...m_n)$, es decir, los números en que rango se determina únicamente por sus coordenadas tupla. Además, esto también es el máximo rango en el que las coordenadas son inyectiva. Este, en particular, implica el estándar de la declaración del Teorema del Resto Chino, ya que el MCM de un conjunto de coprime números enteros es su producto.
Prueba:
Mi favorito de la prueba es similar al argumento que me dio anteriormente, mostrando que las coordenadas son las $\prod m_i$-periódico. Supongamos que estamos trabajando con los modulos $m_1...m_n$. Voy a abreviar $\mathrm{LCM}(m_1,...m_n)$$M$. Obviamente, el coordinar las tuplas son $M$-periódico, ya que la tupla de coordenadas de $M$ es todo ceros. Por el argumento anterior, la de coordinar las tuplas debe repetir después de ese punto. También, es la tupla de coordenadas de $k$ es todo ceros, a continuación, $k$ debe ser un múltiplo común de a $m_1, ... m_n$. Por lo tanto, no hay ningún número menor que $M$ cuyo tupla es todo ceros.
Ahora, supongamos que tenemos $k < k' < M$, de tal manera que las coordenadas de tuplas de $k$ $k'$ eran idénticos. De nuevo, desde la tupla de coordenadas de un número determina la tupla de coordenadas de la siguiente serie, sabemos que la coordenada de tuplas debe repetir después de $k'$. En particular, las coordenadas de los números de $k...k'$ se repite infinitamente. Desde $M>k'$, esto significa que las coordenadas de a $M$ debe ser el mismo que el de coordenadas de algún número entre el$k$$k'$. Pero esto es imposible, ya que la tupla de coordenadas de $M$ es todo ceros, y no el número más pequeño, tiene todo de cero de coordenadas, como se ha demostrado previamente. Por lo tanto las coordenadas de $k$ $k'$ no son idénticos. $\blacksquare$
Este "sistema de coordenadas" punto de vista nos lleva a la interesante cuestión de si hemos tenido un conjunto infinito $m_1, m_2, ...$ de coprime modulos (es decir, el conjunto de los números primos), sería la resultante del sistema de coordenadas de ser inyectiva $\Bbb N$?
