Calculadora del Teorema Chino del Residuo: Resuelve Sistemas Modulares Paso a Paso
Una calculadora del teorema chino del residuo resuelve un sistema de congruencias simultáneas – afirmaciones como x ≡ 2 (mod 3) y x ≡ 3 (mod 5) – combinándolas en una sola congruencia módulo del producto (o mínimo común múltiplo) de los módulos individuales. El método se remonta aproximadamente 1.500 años al texto matemático chino Sunzi Suanjing, y hoy respalda optimizaciones de criptografía RSA, cálculos de calendario y códigos correctores de errores, además de ser un pilar de cursos de matemáticas discretas y teoría de números. Esta guía te muestra cómo funciona la calculadora internamente, cómo verificar si un sistema tiene solución, cómo encontrar los inversos modulares de los que depende el método, dos ejemplos completamente desarrollados – uno con módulos coprimos por pares y uno sin – más errores comunes y problemas de práctica.
Contenido
- 01¿Qué es el Teorema Chino del Residuo?
- 02¿Cómo funciona una Calculadora del Teorema Chino del Residuo?
- 03¿Cómo verificas si los módulos son compatibles?
- 04¿Qué es un Inverso Modular y cómo lo encuentras?
- 05Ejemplo Desarrollado: Resolviendo Congruencias Coprimas por Pares
- 06Ejemplo Desarrollado: Conciliando Módulos No Coprimos
- 07Reconstruyendo la Solución No Negativa Más Pequeña
- 08¿Cuáles son los Errores Más Comunes del Teorema Chino del Residuo?
- 09Problemas de Práctica: Prueba tus Habilidades de Calculadora del Teorema Chino del Residuo
¿Qué es el Teorema Chino del Residuo?
El Teorema Chino del Residuo (CRT) dice que si tienes un sistema de congruencias x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ), y los módulos m₁, m₂, ..., mₙ son coprimos por pares (cada par no comparte factor común excepto 1), entonces hay exactamente una solución para x módulo M, donde M = m₁ × m₂ × ... × mₙ. El teorema toma su nombre de su primera aparición conocida en el texto chino del siglo III al V Sunzi Suanjing (Manual de Aritmética del Maestro Sun), que planteaba el ahora clásico acertijo: encuentra un número que deja resto 2 cuando se divide por 3, resto 3 cuando se divide por 5, y resto 2 cuando se divide por 7. Ese acertijo – y el método CRT que lo resuelve – reaparece constantemente fuera del aula: la criptografía RSA usa CRT para acelerar el descifrado trabajando con módulos más pequeños en lugar de uno enorme, los informáticos lo usan para representar números grandes como tuplas de residuos más pequeños para aritmética más rápida, y los sistemas de calendario lo usan para conciliar ciclos de diferentes longitudes (días de la semana, días del mes y ciclos de año bisiesto).
Teorema Chino del Residuo: para módulos m₁, ..., mₙ coprimos por pares, el sistema x ≡ aᵢ (mod mᵢ) tiene exactamente una solución módulo M = m₁ × m₂ × ... × mₙ.
¿Cómo funciona una Calculadora del Teorema Chino del Residuo?
Una calculadora del teorema chino del residuo automatiza cuatro etapas que son tediosas de seguir a mano una vez que un sistema tiene tres o más congruencias, especialmente los cálculos de inverso modular. Internamente, trata cada congruencia como un par (aᵢ, mᵢ), confirma que los módulos se pueden usar juntos, y luego construye la solución única usando una suma ponderada en lugar de prueba y error. Entender estas cuatro etapas es lo que te permite verificar la salida de una calculadora, o resolver el mismo problema a mano en un examen donde no se permite calculadora.
1. Paso 1: Verifica los módulos
Confirma que cada par de módulos sea coprimo (mcd = 1). Si algún par comparte un factor común, la calculadora cambia a la verificación de compatibilidad descrita en la siguiente sección en lugar de usar la fórmula estándar.
2. Paso 2: Calcula el módulo combinado M
Multiplica todos los módulos: M = m₁ × m₂ × ... × mₙ. Este es el módulo de la respuesta final combinada.
3. Paso 3: Encuentra cada producto parcial y su inverso modular
Para cada congruencia i, calcula Mᵢ = M / mᵢ (el producto de todos los módulos excepto mᵢ), luego encuentra el inverso modular de Mᵢ módulo mᵢ – llámalo yᵢ, donde Mᵢ × yᵢ ≡ 1 (mod mᵢ).
4. Paso 4: Combina y reduce
Suma aᵢ × Mᵢ × yᵢ sobre cada congruencia, luego reduce esa suma módulo M para obtener la única solución no negativa más pequeña x.
La fórmula detrás de cada calculadora del teorema chino del residuo: x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M, donde Mᵢ = M/mᵢ e yᵢ es el inverso modular de Mᵢ mod mᵢ.
¿Cómo verificas si los módulos son compatibles?
La versión de libro de texto del Teorema Chino del Residuo requiere módulos coprimos por pares, pero los sistemas reales – especialmente los que aparecen en problemas de programación o criptografía – a menudo tienen módulos que comparten factores. Una versión generalizada de CRT aún se aplica, pero solo si el sistema primero pasa una verificación de compatibilidad: para cada par de congruencias x ≡ aᵢ (mod mᵢ) y x ≡ aⱼ (mod mⱼ), los dos deben estar de acuerdo en la superposición, lo que significa aᵢ ≡ aⱼ (mod mcd(mᵢ, mⱼ)). Si esa verificación falla incluso para un par, el sistema no tiene solución en absoluto, sin importar lo demás – y una buena calculadora reporta esto en lugar de devolver un número incorrecto.
1. Paso 1: Calcula mcd(mᵢ, mⱼ) para cada par de módulos
Para un sistema de dos congruencias, hay solo un par a verificar. Para un sistema de tres congruencias, verifica los tres pares.
2. Paso 2: Reduce ambos residuos módulo ese mcd
Toma aᵢ mod mcd(mᵢ, mⱼ) y aⱼ mod mcd(mᵢ, mⱼ). Si coinciden, el par es compatible.
3. Paso 3: Ejemplo de un sistema incompatible
Toma x ≡ 1 (mod 4) y x ≡ 0 (mod 6). mcd(4, 6) = 2. Reduce: 1 mod 2 = 1, y 0 mod 2 = 0. Como 1 ≠ 0, ningún entero satisface ambas congruencias – el sistema no tiene solución, y una calculadora del teorema chino del residuo debería marcar exactamente esto en lugar de forzar una respuesta.
Regla de compatibilidad para módulos no coprimos: x ≡ aᵢ (mod mᵢ) y x ≡ aⱼ (mod mⱼ) pueden ser verdaderos solo si aᵢ ≡ aⱼ (mod mcd(mᵢ, mⱼ)).
¿Qué es un Inverso Modular y cómo lo encuentras?
El inverso modular de un número a módulo m es otro número b tal que a × b ≡ 1 (mod m) – juega el mismo papel que 1/a en la división ordinaria, pero restringido a números enteros dentro de un módulo fijo. Un inverso modular existe si y solo si mcd(a, m) = 1, que es exactamente por qué el Teorema Chino del Residuo estándar requiere módulos coprimos: garantiza que cada Mᵢ tenga un inverso mod mᵢ. La forma más confiable de encontrar un inverso modular a mano es el algoritmo euclidiano extendido, que ejecuta el algoritmo mcd ordinario hacia adelante y luego trabaja hacia atrás para expresar 1 como una combinación de a y m.
1. Paso 1: Ejecuta el algoritmo euclidiano hacia adelante
Encuentra el inverso de 4 mod 7. Divide repetidamente: 7 = 1×4 + 3, luego 4 = 1×3 + 1, luego 3 = 3×1 + 0. Los residuos son 3, luego 1, luego 0, confirmando que mcd(4, 7) = 1, así que existe un inverso.
2. Paso 2: Trabaja hacia atrás para aislar 1
De la penúltima línea, 1 = 4 − 1×3. Sustituye 3 = 7 − 1×4 de la primera línea: 1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7.
3. Paso 3: Lee el inverso
La ecuación 1 = 2×4 − 1×7 significa 2×4 ≡ 1 (mod 7), así que el inverso de 4 mod 7 es 2. Verificación rápida: 4 × 2 = 8 = 7 + 1, que es efectivamente ≡ 1 (mod 7).
Para módulos pequeños, a menudo es más rápido probar candidatos directamente: multiplica a por 1, 2, 3, ... mod m hasta que el producto sea 1. Para módulos más grandes, el algoritmo euclidiano extendido es mucho más confiable.
Ejemplo Desarrollado: Resolviendo Congruencias Coprimas por Pares
Este es el clásico problema de Sunzi Suanjing: encuentra x tal que x ≡ 2 (mod 3), x ≡ 3 (mod 5) y x ≡ 2 (mod 7). Los módulos 3, 5 y 7 son coprimos por pares, así que la fórmula CRT estándar se aplica directamente.
1. Paso 1: Calcula M
M = 3 × 5 × 7 = 105.
2. Paso 2: Calcula cada Mᵢ y su inverso
M₁ = 105/3 = 35. 35 mod 3 = 2, y el inverso de 2 mod 3 es 2 (ya que 2×2 = 4 ≡ 1 mod 3). M₂ = 105/5 = 21. 21 mod 5 = 1, y el inverso de 1 mod 5 es 1. M₃ = 105/7 = 15. 15 mod 7 = 1, y el inverso de 1 mod 7 es 1.
3. Paso 3: Combina
x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23.
4. Paso 4: Verifica
23 ÷ 3 = 7 resto 2 ✓. 23 ÷ 5 = 4 resto 3 ✓. 23 ÷ 7 = 3 resto 2 ✓. La solución no negativa más pequeña es x = 23, y toda otra solución es 23 + 105k para cualquier entero k.
x ≡ 23 (mod 105) – la misma respuesta que una calculadora del teorema chino del residuo devuelve instantáneamente, y el mismo acertijo que abrió esta rama de la teoría de números hace más de mil años.
Ejemplo Desarrollado: Conciliando Módulos No Coprimos
Ahora resuelve x ≡ 3 (mod 4) y x ≡ 1 (mod 6), donde 4 y 6 no son coprimos (comparten un factor de 2). La fórmula estándar del ejemplo coprimo por pares no se aplica directamente, pero el sistema aún puede tener una solución única módulo el mínimo común múltiplo de los módulos, siempre que primero pase la verificación de compatibilidad.
1. Paso 1: Verifica compatibilidad
mcd(4, 6) = 2. Reduce ambos residuos: 3 mod 2 = 1, y 1 mod 2 = 1. Coinciden, así que el sistema es compatible y existe una solución.
2. Paso 2: Encuentra el módulo combinado
En lugar de multiplicar 4 × 6 = 24, usa el mínimo común múltiplo: mcm(4, 6) = 12. La solución será única módulo 12, no 24.
3. Paso 3: Sustituye y resuelve
Escribe x = 4k + 3 de la primera congruencia, luego sustituye en la segunda: 4k + 3 ≡ 1 (mod 6), así que 4k ≡ −2 ≡ 4 (mod 6). Ambos lados y el módulo comparten un factor de mcd(4, 6) = 2, así que divide toda la congruencia por 2: 2k ≡ 2 (mod 3). El inverso de 2 mod 3 es 2, así que k ≡ 2×2 ≡ 1 (mod 3).
4. Paso 4: Reconstruye x
k = 3j + 1 para cualquier entero j, así que x = 4(3j + 1) + 3 = 12j + 7. La solución no negativa más pequeña es x = 7.
5. Paso 5: Verifica
7 mod 4 = 3 ✓. 7 mod 6 = 1 ✓. Así que x ≡ 7 (mod 12) es correcto, y dividir la congruencia por el factor compartido – en lugar de ignorarlo – es el paso que hace que el CRT no coprimo funcione.
Cuando los módulos comparten un factor común, no puedes usar la fórmula coprima por pares tal cual – debes dividir la congruencia resultante por mcd(mᵢ, mⱼ) antes de encontrar el inverso, o el inverso no existirá.
Reconstruyendo la Solución No Negativa Más Pequeña
Cada sistema del teorema chino del residuo que pasa su verificación de compatibilidad tiene infinitas soluciones enteras, no solo una – pero todas son congruentes entre sí módulo M (o módulo mcm(m₁, ..., mₙ) en el caso no coprimo). Por convención, una calculadora reporta el representante no negativo más pequeño de esa familia infinita, el valor x₀ que satisface 0 ≤ x₀ < M, porque es la única respuesta canónica que es más fácil de enunciar, comparar y verificar. Toda otra solución es solo x₀ más o menos un múltiplo de M.
1. Reduciendo una suma intermedia negativa
La suma ponderada en el Paso 4 del método de calculadora puede salir negativa si algún residuo aᵢ es negativo o si un inverso modular se calculó como un representante negativo. Si la suma es, digamos, S = −37 y M = 45, suma M repetidamente hasta que el resultado sea no negativo: −37 + 45 = 8, así que la solución no negativa más pequeña es x₀ = 8, no −37.
2. El conjunto completo de soluciones
Una vez que tienes x₀, el conjunto completo de soluciones es cada entero de la forma x₀ + kM para k = ..., −2, −1, 0, 1, 2, .... En el ejemplo de Sunzi arriba, eso es 23, 128, 233, ... y también −82, −187, y así sucesivamente – pero 23 es el que reportas a menos que se solicite un rango específico.
Un resultado intermedio negativo u oversized no es incorrecto – simplemente aún no ha sido reducido. Suma o resta múltiplos de M hasta que el valor caiga en [0, M).
¿Cuáles son los Errores Más Comunes del Teorema Chino del Residuo?
La mayoría de los errores en problemas CRT provienen de omitir una verificación en lugar de un cálculo final defectuoso, razón por la cual vale la pena ir más lentamente al principio de un problema que al final.
1. Aplicando la fórmula coprima a módulos no coprimos
Si dos módulos comparten un factor, calcular M como su producto directo y buscar inversos modulares de la forma estándar fallará silenciosamente o producirá una respuesta incorrecta – siempre verifica primero que mcd(mᵢ, mⱼ) = 1 para cada par.
2. Confundiendo un inverso modular con un recíproco regular
El inverso de 4 mod 7 es 2, no 1/4 – los inversos modulares son números enteros encontrados a través del algoritmo euclidiano extendido (o multiplicación de prueba para módulos pequeños), nunca fracciones.
3. No reducir correctamente números negativos módulo m
−2 mod 6 es 4, no −2 y no 2 – sigue sumando el módulo hasta que el resultado esté en el rango [0, m). Truncar o tomar el valor absoluto en lugar de sumar el módulo es una fuente frecuente de respuestas incorrectas.
4. Olvidar dividir por el factor compartido en sistemas no coprimos
Cuando los módulos comparten un factor común, una congruencia como 4k ≡ 4 (mod 6) debe dividirse por mcd(4, 6) = 2 para convertirse en 2k ≡ 2 (mod 3) antes de poder encontrar un inverso – 4 no tiene inverso mod 6 en absoluto, ya que mcd(4, 6) ≠ 1.
5. Detenerse antes de reducir la suma final módulo M
La suma ponderada del Paso 4 (por ejemplo, 233 en el problema de Sunzi) no es la respuesta final – debe reducirse módulo M (233 mod 105 = 23) para alcanzar la solución no negativa más pequeña.
Si tu respuesta no satisface cada congruencia original cuando la vuelves a conectar, verifica primero la prueba de compatibilidad y los inversos modulares – ahí es donde realmente sucede casi cada error de CRT.
Problemas de Práctica: Prueba tus Habilidades de Calculadora del Teorema Chino del Residuo
Trabaja a través de estos tres sistemas a mano, verificando coprimalidad por pares o compatibilidad primero, antes de comparar con las soluciones a continuación. El segundo problema es deliberadamente irresolvible – reconocer eso es tan importante como encontrar una respuesta numérica cuando existe.
1. Problema 1 (coprimo por pares)
Resuelve: x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7). Respuesta: M = 105. M₁ = 35 con inverso 2 mod 3; M₂ = 21 con inverso 1 mod 5; M₃ = 15 con inverso 1 mod 7. Suma = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244. 244 mod 105 = 34. Verificación: 34 mod 3 = 1 ✓, 34 mod 5 = 4 ✓, 34 mod 7 = 6 ✓. Solución: x ≡ 34 (mod 105).
2. Problema 2 (módulos incompatibles – sin solución)
Resuelve: x ≡ 2 (mod 8), x ≡ 5 (mod 12). mcd(8, 12) = 4. Reduce: 2 mod 4 = 2, y 5 mod 4 = 1. Como 2 ≠ 1, el sistema es incompatible y no tiene solución – una calculadora del teorema chino del residuo debería devolver esta conclusión en lugar de un número incorrecto.
3. Problema 3 (módulos compatibles no coprimos)
Resuelve: x ≡ 5 (mod 9), x ≡ 2 (mod 6). mcd(9, 6) = 3. Reduce: 5 mod 3 = 2, y 2 mod 3 = 2 – compatible. mcm(9, 6) = 18. Escribe x = 9k + 5, sustituye: 9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6). Divide por mcd(9, 6) = 3: 3k ≡ 1 (mod 2) → k ≡ 1 (mod 2). Así que k = 2j + 1, dando x = 9(2j+1) + 5 = 18j + 14. Verificación: 14 mod 9 = 5 ✓, 14 mod 6 = 2 ✓. Solución: x ≡ 14 (mod 18). Si deseas verificar cada inverso modular y paso de reducción en un problema como este, el solucionador de matemáticas paso a paso de Solvify te guiará a través de cada etapa de la misma manera que esta guía.
La forma más rápida de construir verdadera fluidez con el Teorema Chino del Residuo es resolver una mezcla de sistemas coprimos, no coprimos pero compatibles e incompatibles – reconocer qué caso tienes es la mitad de la habilidad.
Artículos relacionados
Calculadora del Teorema del Residuo: Cómo Encontrar Residuos Paso a Paso
Un concepto de residuo diferente pero relacionado – esta guía cubre el teorema del residuo polinómico, contexto útil antes de abordar congruencias modulares.
Calculadora de Eliminación Gaussiana: Resuelve Sistemas Lineales Paso a Paso
Otro método de calculadora sistemático impulsado por algoritmos – compara cómo la eliminación gaussiana y el Teorema Chino del Residuo reducen cada uno un sistema a una sola respuesta.
Resolución Paso a Paso de Problemas Matemáticos: Un Marco Repetible para Cualquier Problema
El marco de 5 pasos en esta guía se aplica directamente a problemas CRT: identifica lo que se da, elige un método, trabaja sistemáticamente y verifica el resultado.
Solucionadores matemáticos
Solucionador de Escaneo Inteligente
Toma una foto de un sistema de congruencia o problema de teoría de números y obtén una solución instantánea del Teorema Chino del Residuo paso a paso.
Soluciones Paso a Paso
Ve cada inverso modular, verificación de compatibilidad y paso de reducción explicados, no solo el residuo final.
Tutor de Matemáticas AI
Haz preguntas de seguimiento sobre inversos modulares, módulos coprimos o por qué un sistema no tiene solución, con respuestas adaptadas a tu problema exacto.
Materias relacionadas
Fundamentos de Álgebra
La comodidad con fracciones y residuos hace que la aritmética modular y el Teorema Chino del Residuo sean mucho más fáciles de entender.
Calculadora de Rango de Matriz
Otro método de calculadora adyacente a la teoría de números, impulsado por algoritmos – práctica útil para la misma mentalidad sistemática paso a paso que CRT requiere.