De un resto a un sistema
La congruencia x ≡ a (mod n) dice que n divide a x−a. Describe una clase infinita: a, a+n, a−n y todos sus desplazamientos enteros. En un sistema buscamos un mismo entero que pertenezca a todas esas clases. Esa intersección es el conjunto solución, y se repite con un período común.
El teorema clásico
Si los módulos son coprimos dos a dos, cualquier elección de residuos admite una solución, única módulo el producto N. No basta con que el MCD de todos los módulos juntos sea 1: cada par debe tener MCD 1. Si dos enteros cumplen el sistema, su diferencia es divisible por cada módulo y, por coprimalidad, por N. Esa es la unicidad de la clase, no de un único entero. NIST DLMF, §27.15.
N=i∏ni,x=x0+kN,k∈Z Construcción directa con inversos
Para cada fila, Nᵢ=N/nᵢ contiene todos los otros módulos. Su inverso uᵢ módulo nᵢ existe por coprimalidad. Así, Nᵢuᵢ deja resto 1 en su propia fila y 0 en las demás. Multiplicar por aᵢ y sumar construye simultáneamente los restos pedidos.
ui=Ni−1(modni),x0=(i∑aiNiui)modN Cada término puede comprobarse por separado antes de reducir la suma. Este argumento constructivo se desarrolla en las notas de MIT, lección 5.
Cuando los módulos comparten factores
El sistema tiene solución si y solo si cada par de residuos coincide módulo el MCD de sus módulos. Cuando existe, el período es el mínimo común múltiplo L. Usar el producto podría omitir soluciones al describir la familia. Por ejemplo, 32 módulo 60, 2 módulo 90 y 2 módulo 150 se combinan en 452 módulo 900, uno de los ejemplos oficiales de SageMath.
ai≡aj(modgcd(ni,nj))∀i<j,L=mcm(n1,…,ns) Fusionar dos congruencias
Si la clase acumulada es x≡r (mod M), escribimos x=r+Mk e imponemos la fila siguiente x≡a (mod n). Resulta Mk≡a−r (mod n). Con g=MCD(M,n), la diferencia debe ser divisible por g. Dividir entre g deja módulos coprimos M′=M/g y n′=n/g, y el inverso de M′ módulo n′ se obtiene con el algoritmo de Euclides extendido.
k0=(ga−r(M′)−1)modn′,r′=(r+Mk0)mod(Mn′) La nueva clase tiene período Mn′. Si n′=1, la fila ya estaba contenida en la clase acumulada: k₀=0, sin invertir módulo 1. Repetir el procedimiento incorpora todo el sistema.
Sun Zi, paso a paso
El problema histórico pide restos 2, 3 y 2 al dividir por 3, 5 y 7. El producto es 105; los factores parciales son 35, 21 y 15, y sus inversos respectivos son 2, 1 y 1.
2·35·2 + 3·21·1 + 2·15·1
= 140 + 63 + 30 = 233
233 mod 105 = 23
x = 23 + 105k, k ∈ ℤ
La comprobación da 23 mod 3=2, 23 mod 5=3 y 23 mod 7=2. La fusión obtiene primero 8 módulo 15 y luego 23 módulo 105: dos construcciones, una misma clase exacta.
Un certificado de imposibilidad
Las filas x≡1 (mod 4) y x≡2 (mod 6) exigen, respectivamente, paridad impar y par. Su MCD es 2, pero los residuos dejan 1 y 0 módulo 2. Ese único par demuestra que no existe solución para el sistema completo. La incompatibilidad se demuestra, no se supone: basta exhibir un par cuyos residuos difieran módulo su MCD.
La condición de compatibilidad y la construcción para dos módulos están demostradas en Clive Newstead, §3.3, teoremas 3.3.44–45. Las fusiones la extienden al sistema finito.
Normalizar y reconocer redundancias
−1 módulo 4 y 3 módulo 4 describen la misma clase. Normalizar el residuo lo lleva al intervalo de 0 a n−1 y conserva la restricción. Dos filas normalizadas idénticas son duplicadas. También puede haber redundancia colectiva: las filas módulo 2 y módulo 3 pueden implicar una fila módulo 6 aunque ninguna la implique por separado.
Una fila redundante se puede retirar conservando las demás. Retirar todas las filas señaladas a la vez exige volver a comprobar el sistema, porque entre ellas pueden implicarse mutuamente.
Alcance: una incógnita, módulos enteros
El caso tratado aquí tiene una incógnita y filas x≡aᵢ (mod nᵢ), con módulos enteros de al menos 2. Una fila con coeficiente, como 3x≡6 (mod 9), requiere primero resolver una congruencia lineal; puede producir varias clases. Los sistemas con coeficientes, polinomios, errores en los residuos o varias incógnitas responden a condiciones de existencia distintas. Garner, la aritmética por residuos y los protocolos criptográficos son algoritmos y aplicaciones construidos sobre este teorema, no casos suyos.