Aplicaciones del teorema del resto chino

Question

Como sugiere el título, estoy interesado en las aplicaciones de la TRC. Artículo de Wikipedia sobre CRT enumera algunas de las aplicaciones más conocidas (por ejemplo, se utiliza en el algoritmo RSA, se utiliza para construir una elegante numeración de Gödel para las secuencias...)

¿Conoces otras aplicaciones (quizás no tan conocidas)? O problemas interesantes (¿recreativos? o de concursos matemáticos como la OMI?) que se puedan resolver con la TRC. O alguna buena referencia o ejemplo en ese sentido.

Espero que con esto tenga una mejor comprensión de la TRC y de cómo utilizarla en general.

Answer 1

Computación paralela: Supongamos que tienes que hacer un gran cálculo que implica sumar, multiplicar y restar enteros. Posiblemente también dividir, pero, en ese caso, sólo la división por números de un conjunto finito S que ya conoces.

Elija los primos $p_1$ , $p_2$ , ..., $p_r$ que no dividen ningún elemento de $S$ y tal que $p_1 p_2 \cdots p_r$ es seguramente mayor que su respuesta. Divida su cálculo en $r$ procesadores, el $i$ que calcula la respuesta modulo $p_i$ . Utiliza la TRC para recomponer tu respuesta al final.

Este fue el método utilizado en el cálculo reciente de los polinomios Kazhdan-Lustig-Vogan de E8.

Answer 2

Compartir el secreto. Supongamos que tenemos $N$ personas. Queremos que cualquier $k+1$ de ellos para poder lanzar un ataque con misiles, pero no $k$ de ellos para tener este poder.

Solución: Elegir algún primo grande $p$ y un polinomio aleatorio $f(t)$ de grado $k$ con coeficientes en $\mathbb{Z}/p$ . Dígale a la persona $1$ el valor de $f(1)$ , persona $2$ el valor de $f(2)$ y así sucesivamente. (Además, todo el mundo sabe lo que $p$ es). Configure los misiles para que sólo se lancen cuando $f(0)$ es la entrada. Cualquier $k+1$ la gente puede utilizar el teorema del resto chino para calcular $f$ y por lo tanto $f(0)$ cualquier $k$ la gente no tiene suficientes datos para limitar $f(0)$ de ninguna manera.

Answer 3

El teorema del resto chino se utiliza para resolver las ambigüedades de alcance múltiple en muchos sistemas de radar.

Answer 4

La interpolación de Lagrange es un caso especial del teorema del resto chino. (Arreglo de un enlace muerto: https://artofproblemsolving.com/community/c1157h990758_the_chinese_remainder_theorem_and_lagrange_interpolation )

La forma normal de Jordan puede demostrarse muy rápidamente utilizando el teorema del resto chino para módulos sobre un anillo conmutativo. Para ello, primero hay que demostrar la descomposición Jordan-Chevalley, y luego el resto es un simple ejercicio de mostrar el aspecto real de los bloques de Jordan.

La primera es muy sorprendente para la gente, pero si se enuncia correctamente la interpolación de Lagrange, es fácil ver que la idea no sólo es similar, sino idéntica.

Answer 5

Aquí hay algunas aplicaciones que no veo entre las otras respuestas.

1. Todo el mundo sabe $5^2$ termina en 5 y $6^2$ termina en 6. Tu tarea: encontrar números de varias cifras cuyos cuadrados terminen en sí mismos (p. ej, $25^2$ termina en 25, $76^2$ termina en 76, ...). Este problema se puede dar a los estudiantes -incluso a los niños- que no saben ninguna matemática en particular y descubren experimentalmente para $n$ = 2, 3, 4, ... que normalmente hay dos $n$ -(a veces menos de 2 soluciones, pero nunca más de 2). En cuanto a si este patrón persiste para todos los $n$ , tanto que suele haber soluciones como que hay a lo sumo dos soluciones entre $n$ -números de un dígito, convertir el problema en una condición de congruencia y luego pensar en la TRC.

2. Si $f(x)$ está en ${\mathbf Z}[x]$ y todos sus valores $f(a)$ para $a$ sur ${\mathbf Z}$ son múltiplos de 2 o de 3, entonces CRT implica que todos sus valores son múltiplos de 2 o que todos sus valores son múltiplos de 3. A primera vista, esto parece algo milagroso, ¿no? (El mismo resultado funciona por CRT si se sustituye {2,3} por cualquier conjunto finito de enteros relativamente primos por pares).

3. La prueba de primalidad probabilística Solovay-Strassen. La verificación de que esta prueba admite un testigo para los módulos compuestos de impar utiliza la TRC. Cuando enseño teoría de los números en la licenciatura, la prueba de SS siempre ha sido el último tema del curso y es una buena aplicación de la TRC.

4. Si $a$ no es un cuadrado en $\mathbf Z$ entonces hay infinitos primos $p$ tal que $a \bmod p$ no es un cuadrado. Esto es una aplicación del teorema chino del resto y de la reciprocidad cuadrática. (Esto puede ser superado en un sentido cuantitativo si se utiliza el teorema de Dirichlet sobre los primos en la progresión aritmética).

5. Si $m|n$ entonces el mapa de reducción ${\mathbf Z}/n{\mathbf Z} \rightarrow {\mathbf Z}/m{\mathbf Z}$ es fácilmente suryectiva. Por favor, intente demostrar por métodos elementales que el mapa de reducción en las unidades, $({\mathbf Z}/n{\mathbf Z})^\times \rightarrow ({\mathbf Z}/m{\mathbf Z})^\times$ es surjetivo sin usando CRT. Usando la TRC es bastante fácil. (Puedes tirar del teorema de Dirichlet sobre los primos para una demostración rápida, pero ese es un resultado bastante profundo comparado con la TRC, así que no contaría como una demostración elemental evitando la TRC).