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

Aquí hay un ejemplo claro que es anterior al ejemplo de David Speyer de aritmética paralela rápida, pero que utiliza el mismo truco.

Richard J. Lipton, Yechezkel Zalcstein: Word Problems Solvable in Logspace. J. ACM 24(3): 522-526 (1977)

En este trabajo se utiliza el teorema chino del resto para demostrar que el problema de la palabra en varios tipos de grupos es resoluble en el espacio logarítmico. (El teorema del resto chino no se invoca explícitamente, pero se puede utilizar para justificar los algoritmos). Por ejemplo, el artículo dice:

Corolario 6. El problema de la palabra para grupos libres finitamente generados es resoluble en el espacio logarítmico.

El problema de palabras para un grupo finito es determinar si un producto dado de elementos del grupo es igual a la identidad. Los resultados se demuestran incrustando un grupo en un grupo de matrices sobre los números enteros, y luego calculando el producto matricial módulo de todos los primos pequeños.

Answer 2

Muchas propiedades de $\mathbb{Z}/n$ se puede desglosar en propiedades de $\mathbb{Z}/p^i$ utilizando el Teorema del Resto Chino. Aquí hay un ejemplo que no tengo ni idea de cómo demostrar lo contrario:

Lista reducida de la OMI 1997 problema 15 equivale a demostrar que si algún número entero dado es un residuo cuadrado módulo $n$ y un residuo cúbico módulo $n$ al mismo tiempo, entonces es un $6$ -enésimo residuo de potencia módulo $n$ también. En general, si $n$ , $u$ , $v$ son tres enteros positivos, y algunos dados $a\in\mathbb{Z}/n$ es a la vez un $u$ -a potencia y a $v$ -enfermedad en $\mathbb{Z}/n$ entonces $a$ es un $\mathrm{lcm}\left(u,v\right)$ -enfermedad en $\mathbb{Z}/n$ .

Answer 3

El teorema del resto chino puede generalizarse como sigue: Sea $G$ sea un grupo con subgrupos normales $H,K$ de $G$ . Entonces el mapa canónico $G/(H \cap K) \to G/H \times_{G/(HK)} G/K$ es un isomorfismo. La prueba es trivial. Con el mismo argumento: Sea $R$ sea un anillo con ideales $I,J$ entonces el mapa canónico $R/(I \cap J) \to R/I \times_{R/(I+J)} R/J$ es un isomorfismo. Ahora bien, esto revela un significado geométrico del teorema del resto cinético:

Dejemos que $X$ sea un esquema y $A,B$ dos subesquemas cerrados de $X$ . Entonces $A \cup B$ es un subesquema cerrado de $X$ (intersección de las láminas ideales) y tenemos $A \cup B = A \coprod_{A \cap B} B$ .

Por lo tanto, la unión de dos subesquemas cerrados es la expulsión de $A$ y $B$ a lo largo de $A \cap B$ que es muy intuitivo.

Answer 4

Una aplicación: encontrar el producto de todos los elementos del grupo multiplicativo $({\mathfrak o}/{\mathfrak a})^\times$ , donde $\mathfrak o$ es el anillo de enteros en un campo numérico y ${\mathfrak a}\subset{\mathfrak o}$ es un ideal. El caso ${\mathfrak o}={\mathbb Z}$ es el teorema de Wilson. Véase, por ejemplo, arXiv:0711.3879v1 [math.NT].

Answer 5

El Teorema Chino del Resto da una forma de calcular exponenciales matriciales.

En efecto, dejemos que $A$ sea una matriz cuadrada compleja, ponga $B:=\mathbb C[A]$ . Se trata de un álgebra de Banach, y también de un $\mathbb C[X]$ -Álgebra ( $X$ siendo un indeterminado). Sea $S$ sea el conjunto de valores propios de $A$ , $$\mu=\prod_{s\in S}\ (X-s)^{m(s)}$$ el polinomio mínimo de $A$ e identificar $B$ à $\mathbb C[X]/(\mu)$ .

El Teorema del Resto Chino dice que la canónica $\mathbb C[X]$ -morfismo de álgebra $$\Phi:B\to C:=\prod_{s\in S}\ \mathbb C[X]/(X-s)^{m(s)}$$ es biyectiva.

Cálculo de exponenciales en $C$ es trivial, por lo que la única pieza que falta en nuestro rompecabezas es la inversión explícita de $\Phi$ .

Arreglar $s$ sur $S$ y que $e_s$ sea el elemento de $C$ que tiene un uno en el $s$ lugar y ceros en otro lugar. Basta con calcular $\Phi^{-1}(e_s)$ . Este elemento tendrá la forma $$f=\frac{\mu}{(X-s)^{m(s)}}\ g\ \mbox{ mod }\mu$$ con $f,g\in\mathbb C[X]$ El único requisito es $$g\equiv\frac{(X-s)^{m(s)}}{\mu}\mbox{ mod }(X-s)^{m(s)}$$ (la congruencia tiene lugar en el anillo de fracciones racionales definido en $s$ ). Así que $g$ viene dada por la Fórmula de Taylor.