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

Hay algunos ejercicios bonitos basados en el teorema del resto chino, por ejemplo,

(1) existe un número arbitrariamente grande de enteros consecutivos, ninguno de los cuales es libre de cuadrados (Concurso de Putnam de 1955),

(2) existe un número arbitrariamente grande de enteros consecutivos, ninguno de los cuales es poderoso ( $n$ es potente si para cada primo $p$ dividiendo $n$ tenemos $p^2|n$ ),

(3) existe un número arbitrariamente grande de enteros positivos consecutivos, ninguno de los cuales es una suma de dos cuadrados,

(4) el número de enteros $1\cdot 2, 2\cdot 3, \dots, n\cdot (n+1)$ divisible por $n$ es $2^{\omega(n)}$ , donde $\omega(n)$ es el número de divisores primos distintos de $n$ .

Answer 2

En la prueba de Primer Teorema de Incompletitud de Gödel , hay que elegir una forma de codificar las fórmulas y las pruebas como números. La forma más fácil de hacerlo es tomar 2 i ₀ 3 i ₁ 5 i ₃ ...p _j i _j . Sin embargo, puedes utilizar el Teorema del Resto Chino para elegir un número congruente con i ₀ mod p ₀ congruente con i ₁ mod p ₁ La ventaja de hacer esto es que ya no necesitas la exponenciación en tu teoría, sólo la multiplicación y la adición.

Answer 3

Reciprocidad cuadrática

Quizás la mejor aplicación de la TRC es la demostración de la Reciprocidad Cuadrática de Gauss, una demostración debida a Rousseau (mi versión se encuentra en mi blog aquí ) que utiliza sólo el CRT. Es muy raro que las pruebas del QR caigan sin mucho esfuerzo :)

Answer 4

Ya sacas esta idea cuando mencionas la RSA, pero quiero hacer la observación de forma más general: Hay muy buenos métodos para resolver ecuaciones polinómicas módulo primos y potencias primos. La única forma buena de resolver una ecuación módulo $N$ es factorizar $N$ ; resuelve el módulo de cada potencia prima dividiendo $N$ y utilizar el resto chino para poner una solución. Esto es cierto incluso para calcular raíces cuadradas.

Answer 5

La TRC combinada con el teorema de Dirichlet permite demostrar la existencia de infinitos primos que satisfacen cualquier sistema de congruencias que tenga solución; he esbozado una prueba de que esto implica que las raíces cuadradas de los enteros no tienen dependencias lineales no triviales aquí .