Calculadora del teorema chino del resto
Cuenta un montón de cosas de tres en tres y sobran 2, de cinco en cinco sobran 3, de siete en siete sobran 2: hay 23, o 128, o 233, una respuesta cada 105. Es el problema del Sunzi Suanjing que dio nombre al teorema chino del resto. Escribe cualquier sistema de congruencias x ≡ a (mod n), con tantas ecuaciones y números tan grandes como quieras, y verás la respuesta, el desarrollo con tus números y una imagen de por qué funciona. Cuando las ecuaciones no pueden cumplirse todas, la calculadora nombra las dos que chocan y muestra por qué. Escribe las ecuaciones x ≡ a (mod n), una por fila: a es el resto y n el módulo. Añade una fila con Añadir ecuación, o pulsando Intro en el último módulo, y quítala con ×. Funcionan números enteros de hasta 200 cifras, y a puede ser negativo. O elige un ejemplo resuelto. Las fichas muestran la solución más pequeña y cada cuánto se repite; debajo aparecen las primeras soluciones positivas y una comprobación de cada ecuación. La imagen marca los números que cumplen cada ecuación, y la columna en la que todas las filas tienen una marca es la solución; la tabla de restos muestra dos ecuaciones a la vez. El desarrollo se escribe con tus números, por la construcción clásica o por sustitución.
Cómo funciona
- Escribe las ecuaciones x ≡ a (mod n), una por fila, o elige un ejemplo resuelto como el problema de Sunzi, la cesta de huevos o el período juliano.
- Lee la solución más pequeña, el módulo con el que se repite y las primeras soluciones positivas, cada una comprobada con todas las ecuaciones.
- Sigue el desarrollo paso a paso, por la construcción o por sustitución, y cambia la imagen entre la recta numérica y la tabla de restos.
Cómo funciona la construcción
Cuando ningún par de módulos tiene un factor común, la solución se puede construir directamente. Multiplica los módulos: para el problema de Sunzi, N = 3 × 5 × 7 = 105. Para cada ecuación toma Nᵢ = N / nᵢ, múltiplo de todos los demás módulos: 35, 21 y 15. Después busca el inverso yᵢ de Nᵢ mod nᵢ con el algoritmo de Euclides extendido: 35 da resto 2 al dividir entre 3, y 2 × 2 = 4 ≡ 1 (mod 3), así que y₁ = 2; 21 y 15 dan resto 1, así que sus inversos son 1. Entonces x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, y 233 mod 105 = 23. Cada término encaja en su propia ecuación y es múltiplo de los demás módulos, así que la suma encaja en todas.
Cuando los módulos tienen un factor común
Un sistema cuyos módulos tienen factores comunes también puede tener solución. Dos ecuaciones x ≡ a (mod m) y x ≡ b (mod n) pueden cumplirse a la vez exactamente cuando a − b es múltiplo de gcd(m, n), y entonces la solución se repite cada lcm(m, n) en lugar de cada m × n. Dos autobuses que salen en los minutos 5 y 11, cada 12 y cada 18 minutos, coinciden en el minuto 29 y luego cada 36 minutos, porque 11 − 5 = 6 es múltiplo de gcd(12, 18) = 6. Pero x ≡ 1 (mod 4) y x ≡ 4 (mod 6) nunca pueden cumplirse a la vez: la primera hace x impar y la segunda par. Un sistema entero tiene solución exactamente cuando cada par de sus ecuaciones la tiene, y así encuentra la calculadora las dos que chocan.
Preguntas frecuentes
¿Qué dice el teorema chino del resto?
Si ningún par de los módulos n₁, n₂, … tiene un factor común, entonces para cualesquiera restos a₁, a₂, … existe exactamente un x entre 0 y N − 1 con x ≡ aᵢ (mod nᵢ) para cada i, donde N es el producto de los módulos. Cualquier otra solución se diferencia de ella en un múltiplo de N: para el problema de Sunzi las soluciones son 23, 128, 233 y así sucesivamente, una cada 105.
¿Por qué se llama chino?
El problema más antiguo conocido de este tipo está en el Sunzi Suanjing, un libro de aritmética chino escrito entre los siglos III y V: contadas de tres en tres, de cinco en cinco y de siete en siete, unas cosas dejan restos 2, 3 y 2. Qin Jiushao dio un método general para estos problemas en 1247, y Carl Friedrich Gauss enunció el teorema en su forma moderna en 1801.
¿Y si los módulos no son coprimos?
Entonces puede no haber solución, y cuando la hay se repite cada mínimo común múltiplo de los módulos en lugar de cada producto. Dos ecuaciones concuerdan cuando sus restos coinciden módulo el gcd de sus módulos. El acertijo de los huevos usa 2, 3, 4, 5, 6 y 7, que tienen factores comunes, y aun así tiene solución: 301, que se repite cada 420.
¿Cómo usa RSA el teorema chino del resto?
Descifrar un mensaje RSA consiste en calcular c^d mod n, donde n = p × q. Es más rápido calcular c^d mod p y c^d mod q por separado, con el exponente reducido mod p − 1 y q − 1, y unir los dos resultados con el teorema. Con números de la mitad de longitud, cada una de las dos potencias cuesta alrededor de una octava parte del trabajo, así que el descifrado es unas cuatro veces más rápido, y la mayoría del software RSA lo hace así.
¿Qué tamaño pueden tener los números?
Hasta 20 ecuaciones, con números de hasta 200 cifras cada uno. La calculadora trabaja con números enteros exactos en tu navegador, así que la respuesta es exacta por larga que sea, y no se envía nada a ninguna parte.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor