➗

Calculadora del teorema chino del resto

Resuelve un sistema de congruencias x ≡ aᵢ (mod mᵢ) con el teorema chino del resto: la menor solución, la solución general, la combinación paso a paso y módulos no coprimos.

Restos aᵢ

Módulos mᵢ

Cargando calculadora…

Cómo funciona

x ≡ aᵢ (mod mᵢ) · módulos coprimos: x = Σ aᵢ·Mᵢ·yᵢ mod M, M = Πmᵢ, Mᵢ = M/mᵢ, yᵢ = Mᵢ⁻¹ mod mᵢ · caso general: combinar por pares; hay solución si aᵢ ≡ aⱼ (mod mcd(mᵢ, mⱼ)) y el módulo es el mcm

El teorema chino del resto dice que, si los módulos son coprimos dos a dos, un sistema de congruencias tiene exactamente una solución módulo el producto de los módulos. Esta calculadora combina las congruencias de dos en dos con el algoritmo de Euclides extendido, lo que también resuelve módulos con factores comunes: en ese caso solo hay solución si los restos coinciden módulo el factor común, y es única módulo el mínimo común múltiplo.

Ejemplo resuelto

El problema clásico de Sunzi: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Combinando las dos primeras se obtiene x ≡ 8 (mod 15); al añadir la tercera, x ≡ 23 (mod 105). La menor solución es 23 y todas las soluciones son x = 23 + 105k.

Fuentes: Chinese remainder theorem — Wikipedia · Chinese Remainder Theorem — Wolfram MathWorld

Preguntas frecuentes

¿Los módulos tienen que ser coprimos?

No. Con módulos coprimos siempre hay solución. Si dos módulos comparten un factor g, solo hay solución cuando sus restos son congruentes módulo g, y entonces es única módulo el mcm.

¿Cómo se resuelve a mano?

Calcula M = m₁m₂…, Mᵢ = M/mᵢ y el inverso yᵢ de Mᵢ módulo mᵢ; entonces x = Σ aᵢMᵢyᵢ mod M. Para 2, 3, 2 módulo 3, 5, 7: 2·35·2 + 3·21·1 + 2·15·1 = 233 ≡ 23 (mod 105).

¿Para qué se usa el teorema chino del resto?

En problemas de calendarios y ciclos, para acelerar el descifrado RSA, en esquemas de secreto compartido y para operar con números enormes divididos en restos más pequeños.

¿Los restos pueden ser negativos o mayores que el módulo?

Sí. Primero se reducen: x ≡ −1 (mod 5) es lo mismo que x ≡ 4 (mod 5).

Calculadoras relacionadas

Calculadora de inverso modular

Calcula el inverso multiplicativo modular de a módulo m con el algoritmo de Euclides extendido: cada división, la identidad de Bézout, la comprobación y cuándo no existe inverso.

Calculadora de módulo y residuo

Calcula el residuo (a mod b) y el cociente de una división, con el módulo truncado y el módulo redondeado hacia abajo para números negativos. Resultado al instante.

Calculadora de MCD y MCM

Calcula al mismo tiempo el máximo común divisor (MCD) y el mínimo común múltiplo (MCM) de dos números enteros, con la comprobación MCD × MCM = a × b.

Calculadora de mínimo común múltiplo

Calcula el mínimo común múltiplo (MCM) de dos o tres números enteros usando su relación con el MCD. Ideal para sumar fracciones con distinto denominador.

Esta calculadora tiene fines informativos. Verifica los resultados importantes antes de tomar decisiones.