Calculadora del teorema chino del resto (TCR) — Resuelve congruencias simultáneas
Resuelve un sistema de congruencias simultáneas x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)... con el teorema chino del resto. Verifica automáticamente que los módulos sean coprimos entre sí y devuelve la solución mínima no negativa y la solución general.
Ejemplo resuelto: el problema del "número desconocido" del Sunzi Suanjing
Un problema clásico del Sunzi Suanjing (el "Clásico matemático de Sun Tzu"), un texto aritmético chino de entre los siglos III y V, considerado a menudo el origen del teorema chino del resto. La pregunta "¿qué número deja resto 2 al dividirse entre 3, resto 3 al dividirse entre 5 y resto 2 al dividirse entre 7?" tiene como respuesta 23, módulo 105.
| Condición 1 | x ≡ 2 (mod 3) |
|---|---|
| Condición 2 | x ≡ 3 (mod 5) |
| Condición 3 | x ≡ 2 (mod 7) |
| Solución | x ≡ 23 (mod 105) |
Qué es el teorema chino del resto
El teorema chino del resto resuelve sistemas de congruencias del tipo **«¿qué número deja 2 al dividirlo por 3, 3 por 5 y 2 por 7?»**. Si los módulos son todos coprimos, existe exactamente una solución dentro del rango que fija su producto. Esta herramienta toma hasta cinco congruencias y devuelve la menor solución no negativa junto con la general.
**Solo se atiende la forma clásica: aquella en que todos los módulos son coprimos.** Si dos de ellos comparten un divisor mayor que uno, el sistema no se resuelve por esta vía y un mensaje lo advierte; el teorema generalizado para módulos no coprimos queda fuera del alcance. **Los módulos han de ser enteros de 2 o más**, y los restos se normalizan solos al rango de cero hasta menos de su módulo, de modo que se admiten valores iguales o superiores al módulo, y también negativos. La aritmética corre sobre enteros de precisión arbitraria, así que no hay límite de cifras.
Cómo usar la calculadora
- Introduzca el resto y el módulo Para cada congruencia, dé el resto a y el módulo n. Representan x ≡ a (mod n).
- Añada más congruencias Use «añadir congruencia» para alinear hasta cinco. Cuantas más haya, más amplio el rango —el producto de los módulos— en que la solución sigue siendo única.
- Resuelva Pulse resolver y obtiene la menor solución no negativa junto con la solución general módulo el producto de los módulos.
- Siga el desarrollo Para cada congruencia se listan Nᵢ (el producto de los módulos quitado el propio) y Mᵢ (el inverso de Nᵢ). Sirven para contrastar una solución hecha a mano.
- Se exigen módulos coprimos Un mensaje que diga que los módulos no son coprimos significa que dos comparten un divisor —4 y 6, por ejemplo—. Revise la combinación.
Consejos para aprovecharla mejor
- Si los módulos (nᵢ) no son coprimos entre sí obtendrás un error; por ejemplo, mod 4 y mod 6 comparten el factor 2, por lo que esta calculadora no puede resolver ese sistema (haría falta el TCR generalizado).
- No es necesario reducir tú mismo el resto aᵢ: aunque sea negativo o mayor que nᵢ, la calculadora lo normaliza internamente a mod nᵢ antes de resolver.
- Puedes añadir entre 2 y 5 congruencias. Es útil para acertijos que exigen que un número cumpla tres o más condiciones periódicas a la vez, como el clásico problema de "adivinar el número de soldados".
- La solución general se muestra como x ≡ resultado (mod N): sumar cualquier múltiplo de N al resultado sigue satisfaciendo todas las congruencias originales.
Dónde ayuda el teorema
Ejercicios de teoría de números y preparación de exámenes
Sirve para contrastar una respuesta hecha a mano. Como también aparecen Nᵢ y Mᵢ, puede acotar dónde se colό el desliz.
Estudiar algoritmos criptográficos
La optimización CRT que acelera el descifrado RSA aplica este teorema directamente. Puede seguir el mecanismo en números.
Hallar cuándo coinciden ciclos
Los instantes en que sucesos de periodos distintos caen juntos pueden escribirse como un sistema de congruencias.
Reproducir el problema clásico
El «número desconocido» del Sunzi Suanjing —que deja 2 al dividir por 3, 3 por 5 y 2 por 7— es 23 módulo 105. Introdúzcalo tal cual y compruébelo.
Cuando quiera las herramientas afines de teoría de números
Para inversos y congruencias en sí, vea aritmética modular; para máximos comunes divisores, MCD y mcm; para la factorización, factorización en primos.
Términos sobre el teorema chino del resto
- Teorema chino del resto
- El teorema que afirma que un sistema de congruencias con módulos coprimos tiene solución única módulo su producto.
- Congruencia
- Una expresión de la forma x ≡ a (mod n), que dice que el resto de x al dividirlo por n es igual a a.
- Módulo
- El número por el que se divide. Aquí se limita a enteros de 2 o más.
- Coprimos
- Dos enteros cuyo máximo común divisor es 1. El teorema clásico exige que dos cualesquiera de los módulos sean coprimos.
- Coprimos dos a dos
- De tres o más números: que dos cualesquiera tomados de ellos sean coprimos. Un conjunto puede tener máximo común divisor 1 sin ser coprimo dos a dos.
- Inverso modular
- El x que satisface a·x ≡ 1 (mod n). En el teorema aparece al hallar Mᵢ, el inverso de Nᵢ.
- Algoritmo de Euclides extendido
- El algoritmo que rinde los coeficientes de Bézout junto con el máximo común divisor. Es el que calcula un inverso modular.
- Solución general
- La menor solución no negativa junto con todo múltiplo entero del producto de los módulos sumado a ella, escrita en la forma x ≡ 23 (mod 105).
Preguntas frecuentes
A propósito — De un texto aritmético del siglo III a acelerar el cifrado RSA
El teorema chino del resto se remonta a un problema del Sunzi Suanjing, un clásico aritmético chino que se cree data de entre los siglos III y V d.C. Su famoso acertijo del "número desconocido" —encontrar un número que deje restos 2, 3 y 2 al dividirse entre 3, 5 y 7 respectivamente— ya capturaba la idea esencial detrás del teorema moderno: reconstruir un número desconocido a partir de varios restos de división.
Una de las aplicaciones prácticas más importantes del teorema chino del resto hoy en día es acelerar el descifrado RSA. El descifrado RSA requiere elevar un número grande a una potencia módulo un compuesto n = p × q, donde p y q son primos grandes. En lugar de trabajar directamente módulo n, el TCR permite hacer el cálculo de forma independiente módulo p y módulo q y luego recombinar los resultados, una técnica conocida como CRT-RSA que en teoría puede acelerar el descifrado casi cuatro veces, y que está implementada en muchas bibliotecas criptográficas.
Esta herramienta admite la forma clásica del teorema, que exige que todos los módulos sean coprimos entre sí. Cuando los módulos comparten factores comunes (por ejemplo mod 4 y mod 6), a veces todavía existe una solución, pero determinarla y calcularla requiere el teorema chino del resto generalizado, que queda fuera del alcance de esta herramienta.