Calculadora del Teorema Chino del Resto

Bienvenido a la Calculadora del Teorema Chino del Resto, una potente herramienta de teoría de números que resuelve sistemas de congruencias simultáneas utilizando el Teorema Chino del Resto (TCR). Ya sea que esté estudiando aritmética modular, preparándose para concursos de matemáticas, trabajando en problemas de criptografía o explorando la teoría de números, esta calculadora proporciona una solución completa paso a paso con una visualización interactiva que muestra cómo las clases de congruencia se alinean en la solución única.

¿Qué es el Teorema Chino del Resto?

El Teorema Chino del Resto (TCR) es un resultado fundamental en la teoría de números que garantiza la existencia y unicidad de una solución para un sistema de congruencias simultáneas, siempre que los módulos sean coprimos por pares. El teorema fue descrito por primera vez por el matemático chino Sunzi (孫子) en su obra Sunzi Suanjing (孫子算經) alrededor del siglo III d.C.

Formalmente, dado el sistema:

Si todos los módulos \(m_1, m_2, \ldots, m_k\) son coprimos entre sí por pares (es decir, \(\gcd(m_i, m_j) = 1\) para todo \(i \neq j\)), entonces existe una solución única \(x\) módulo \(M = m_1 \times m_2 \times \cdots \times m_k\).

Cómo funciona el algoritmo del TCR

La prueba constructiva proporciona el algoritmo utilizado por esta calculadora:

Paso 1: Calcular M

Calcule el producto de todos los módulos:

Paso 2: Calcular cada Mᵢ

Para cada congruencia \(i\), calcule \(M_i = M / m_i\). Este es el producto de todos los módulos excepto \(m_i\).

Paso 3: Hallar los inversos modulares

Para cada \(i\), halle \(y_i\) tal que \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) utilizando el Algoritmo de Euclides Extendido. Dado que \(M_i\) y \(m_i\) son coprimos (todos los módulos son coprimos por pares), este inverso siempre existe.

Paso 4: Construir la solución

La solución general es \(x + k \cdot M\) para cualquier entero \(k\), lo que significa que la solución se repite cada \(M\) enteros.

Cómo usar esta calculadora

1. Ingrese sus congruencias: Para cada ecuación \(x \equiv a \pmod{m}\), ingrese el resto \(a\) y el módulo \(m\). Comience con 2 congruencias y haga clic en "Agregar Congruencia" para más (hasta 10).
2. Verifique sus módulos: Todos los módulos deben ser enteros positivos ≥ 2 y coprimos por pares. La calculadora verifica esto automáticamente.
3. Haga clic en "Resolver sistema": La calculadora aplica el algoritmo TCR y muestra la solución única junto con el trabajo paso a paso.
4. Revise la visualización: La recta numérica muestra cómo las clases de congruencia de cada ecuación se intersectan en la solución.
5. Verificar: La sección de verificación confirma que la solución satisface cada congruencia original.

Comprender los resultados

• Solución no negativa más pequeña (x₀): La solución única en el rango [0, M−1]
• Solución general: Todos los enteros de la forma x₀ + kM donde k es cualquier entero
• Tabla de verificación: Confirma x₀ mod mᵢ = aᵢ para cada congruencia
• Desglose paso a paso: Muestra Mᵢ, el inverso modular yᵢ y la suma parcial aᵢ·Mᵢ·yᵢ para cada ecuación
• Recta numérica: Representación visual de cómo las clases de residuos se alinean en la solución

Aplicaciones del Teorema Chino del Resto

El Problema Clásico de Sunzi

El problema original de Sunzi Suanjing pregunta: "Hay ciertas cosas cuyo número se desconoce. Si las contamos de tres en tres, nos sobran dos; de cinco en cinco, nos sobran tres; y de siete en siete, nos sobran dos. ¿Cuántas cosas hay?"

Esto se traduce en: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Usando el TCR, la respuesta es x = 23 (y más generalmente, 23 + 105k para cualquier entero no negativo k).

¿Cuándo no se aplica el TCR?

• Módulos no coprimos: Si cualquier par de módulos comparte un factor común mayor que 1, el TCR estándar no garantiza una solución. Todavía puede existir una solución si los restos son compatibles, pero esta calculadora requiere módulos coprimos por pares para el algoritmo estándar.
• Congruencia única: El TCR requiere al menos 2 congruencias. Una sola congruencia \(x \equiv a \pmod{m}\) ya tiene la solución trivial x = a.

Algoritmo de Euclides Extendido

El Algoritmo de Euclides Extendido es esencial para el TCR porque halla el inverso modular. Dados los enteros \(a\) y \(b\), encuentra los enteros \(x\) e \(y\) tales que:

Cuando \(\gcd(a, b) = 1\), entonces \(x\) es el inverso modular de \(a\) módulo \(b\), es decir, \(a \cdot x \equiv 1 \pmod{b}\).

Preguntas Frecuentes

¿Qué es el Teorema Chino del Resto?

El Teorema Chino del Resto (TCR) establece que si tienes un sistema de congruencias simultáneas x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), donde todos los módulos son coprimos por pares, entonces existe una solución única módulo M = m₁ × m₂ × ... × mₖ. Este teorema fue descrito por primera vez por el matemático chino Sunzi en el siglo III.

¿Qué significa coprimos por pares?

Coprimo por pares significa que cada par de módulos no comparte ningún factor común que no sea 1. Por ejemplo, {3, 5, 7} son coprimos por pares porque mcd(3,5)=1, mcd(3,7)=1 y mcd(5,7)=1. Sin embargo, {4, 6, 5} NO son coprimos por pares porque mcd(4,6)=2.

¿Cómo resolver un sistema de congruencias paso a paso?

Para resolver usando el TCR: (1) Verifique que todos los módulos sean coprimos por pares. (2) Calcule M = producto de todos los módulos. (3) Para cada congruencia, calcule Mᵢ = M/mᵢ. (4) Encuentre el inverso modular yᵢ de Mᵢ módulo mᵢ usando el Algoritmo de Euclides Extendido. (5) Calcule la solución x = Σ(aᵢ × Mᵢ × yᵢ) mod M. La solución general es x + k×M para cualquier entero k.

¿Cuáles son las aplicaciones del Teorema Chino del Resto?

El TCR tiene muchas aplicaciones prácticas: la criptografía RSA utiliza el TCR para un descifrado eficiente. La informática lo usa para aritmética de números grandes dividiendo los cálculos en piezas modulares más pequeñas. El procesamiento de señales aplica el TCR en códigos de corrección de errores. Los problemas de programación y calendario donde los eventos se repiten a diferentes intervalos también utilizan el TCR.

¿Qué sucede si los módulos no son coprimos?

Si los módulos no son coprimos por pares, el TCR estándar no se aplica directamente. En algunos casos, aún puede existir una solución si se cumplen ciertas condiciones de compatibilidad (los restos deben ser consistentes módulo el MCD de los módulos no coprimos). Sin embargo, si no existe tal solución, el sistema de congruencias es inconsistente.

Recursos Adicionales

• Teorema chino del resto - Wikipedia
• Aritmética modular - Wikipedia