El teorema chino del resto explicado

Un número da resto 2 al dividirlo entre 3, resto 3 entre 5 y resto 2 entre 7. ¿Qué número es? Prueba los números uno a uno y al cabo de un rato llegas a 23, pero la pregunta esconde un teorema: mientras los divisores no tengan factores comunes, siempre hay exactamente una respuesta por debajo de su producto, y se encuentra sin probar nada. El teorema tiene unos 1.500 años y sigue funcionando en calendarios, en la aritmética de los ordenadores y en la criptografía que protege la web.

Tres filas de marcas para los números que dan resto 2 mod 3, 3 mod 5 y 2 mod 7, alineadas en una sola columna en el 23
Tres filas de marcas para los números que dan resto 2 mod 3, 3 mod 5 y 2 mod 7, alineadas en una sola columna en el 23

Un problema del Sunzi Suanjing

El Sunzi Suanjing, un libro de aritmética chino de los siglos III a V, pregunta por un número de cosas que, contadas de tres en tres, deja 2, de cinco en cinco deja 3 y de siete en siete deja 2. Su respuesta es 23, y su método es el que todavía se enseña: toma 70 por cada cosa que sobra al contar de tres en tres, 21 por cada una que sobra al contar de cinco en cinco y 15 por cada una que sobra al contar de siete en siete, suma y resta 105 tantas veces como puedas. 2 × 70 + 3 × 21 + 2 × 15 = 233, y 233 − 2 × 105 = 23. Un poema de la época Ming mantuvo los números 70, 21, 15 y 105 en la memoria durante siglos. Qin Jiushao dio un método general en 1247, el mismo problema aparece en el Liber Abaci de Fibonacci de 1202, y Carl Friedrich Gauss enunció el teorema en su forma moderna en sus Disquisitiones Arithmeticae de 1801.

Una página de una edición Qing del Sunzi Suanjing, el tratado aritmético chino de los siglos III–V que pide un número que deje 2, 3 y 2 al contar de tres en tres, de cinco en cinco y de siete en siete.
Una página de una edición Qing del Sunzi Suanjing, el tratado aritmético chino de los siglos III–V que pide un número que deje 2, 3 y 2 al contar de tres en tres, de cinco en cinco y de siete en siete.
Carl Friedrich Gauss, en un retrato de Christian Albrecht Jensen de 1840. Introdujo la notación de congruencia a ≡ b (mod n) en sus Disquisitiones Arithmeticae de 1801.
Carl Friedrich Gauss, en un retrato de Christian Albrecht Jensen de 1840. Introdujo la notación de congruencia a ≡ b (mod n) en sus Disquisitiones Arithmeticae de 1801.

Qué dice el teorema

Toma unos módulos n₁, n₂, …, nₖ de los que ningún par tiene un factor común, y unos restos cualesquiera a₁, a₂, …, aₖ. Entonces existe exactamente un número entero x entre 0 y N − 1, donde N = n₁ × n₂ × … × nₖ, que da resto aᵢ al dividirlo entre nᵢ, para cada i. Todas las demás soluciones se diferencian de él en un múltiplo de N. En la notación de la aritmética modular: el sistema x ≡ aᵢ (mod nᵢ) tiene solución, y es única mod N. Dicho de otro modo, un número entre 0 y N − 1 y su lista de restos llevan exactamente la misma información: 3 × 5 × 7 = 105 números y 3 × 5 × 7 = 105 listas de restos posibles, cada una usada una vez.

Construir la solución

Los números 70, 21 y 15 no son magia. Cada uno da resto 1 al dividirlo entre su propio módulo y resto 0 al dividirlo entre los demás: 70 = 2 × 35 es múltiplo de 5 y de 7 y da resto 1 al dividirlo entre 3. En general se toma Nᵢ = N / nᵢ, múltiplo de todos los módulos menos nᵢ, y se multiplica por yᵢ, el inverso de Nᵢ mod nᵢ. El inverso existe porque Nᵢ y nᵢ no tienen factores comunes, y el algoritmo de Euclides extendido lo encuentra: hace las divisiones de Euclides para el máximo común divisor y vuelve hacia atrás hasta la identidad de Bézout 1 = s × nᵢ + t × Nᵢ, de modo que t es el inverso. Entonces x = a₁N₁y₁ + a₂N₂y₂ + …, reducido mod N, cumple todas las ecuaciones, porque cada término encaja en su propia ecuación y desaparece en todas las demás.

Una ecuación cada vez

Hay un segundo método que no necesita el producto de todos los módulos. Toda solución de x ≡ 2 (mod 3) tiene la forma x = 2 + 3t. Al sustituirla en la siguiente ecuación queda 2 + 3t ≡ 3 (mod 5), es decir, 3t ≡ 1 (mod 5), y multiplicando por 2, el inverso de 3 mod 5, se obtiene t ≡ 2 (mod 5). Entonces x = 2 + 3 × 2 = 8, y las dos primeras ecuaciones juntas dicen x ≡ 8 (mod 15). Repitiendo con la tercera ecuación, 8 + 15t ≡ 2 (mod 7) da t ≡ 1, así que x ≡ 23 (mod 105). Esta sustitución mantiene los números más pequeños, es como suele resolver un ordenador estos sistemas, y sigue funcionando cuando los módulos tienen un factor común.

Módulos con un factor común

Si dos módulos tienen un factor común, sus ecuaciones se solapan: x ≡ 1 (mod 4) ya dice que x es impar, y x ≡ 4 (mod 6) dice que x es par, así que ningún x cumple las dos. En general, x ≡ a (mod m) y x ≡ b (mod n) pueden cumplirse a la vez exactamente cuando a y b dan el mismo resto al dividir entre g = gcd(m, n), es decir, cuando g divide a a − b. La solución es entonces única mod lcm(m, n) = m × n / g, no mod m × n. El viejo acertijo de la cesta de huevos, que deja 1 al sacarlos de 2 en 2, de 3 en 3, de 4 en 4, de 5 en 5 o de 6 en 6 y ninguno al sacarlos de 7 en 7, tiene la respuesta 301, que se repite cada 420 = lcm(2, 3, 4, 5, 6, 7). Un sistema tiene solución exactamente cuando cada par de sus ecuaciones concuerda, así que un sistema imposible siempre contiene un par que choca.

Calendarios, ordenadores y RSA

En 1583 Joseph Escalígero combinó tres ciclos del calendario, el ciclo solar de 28 años, el ciclo lunar de 19 años y la indicción de 15 años, en el período juliano de 28 × 19 × 15 = 7.980 años. Por el teorema, cada año tiene su propia combinación de los tres números de ciclo, y el período empieza en el 4713 a. C., el último año en que los tres valían 1; los astrónomos todavía cuentan los días julianos desde ahí. Los ordenadores usan el teorema para calcular con números enormes como listas de restos pequeños, que se pueden sumar y multiplicar por separado y en paralelo, y unir al final. El descifrado RSA funciona igual: c^d mod n con n = p × q se calcula como dos potencias mod p y mod q unidas con el teorema, unas cuatro veces más rápido que una potencia mod n. Los esquemas para compartir secretos, como los de Mignotte y de Asmuth y Bloom, esconden un secreto en restos, de modo que solo suficientes de ellos juntos lo revelan.

Ron Rivest, Adi Shamir y Len Adleman (de izquierda a derecha)
Ron Rivest, Adi Shamir y Len Adleman (de izquierda a derecha)

Pruébalo

Abre la calculadora para escribir cualquier sistema de congruencias, con hasta 20 ecuaciones y números de hasta 200 cifras, o elige uno de los ejemplos resueltos: el problema de Sunzi, la cesta de huevos, el período juliano, dos horarios de autobús, el descifrado RSA y un sistema sin solución. El desarrollo se escribe con tus números, por la construcción o por sustitución, con el algoritmo de Euclides extendido para cada inverso. La imagen marca los números que cumplen cada ecuación, para que veas la única columna en la que coinciden todas, o coloca los restos de dos ecuaciones en una tabla en la que cada número tiene su propia celda.

Preguntas frecuentes

¿La solución de un sistema de congruencias es única?

Solo salvo un múltiplo del módulo. Si x = 23 resuelve el problema de Sunzi, también lo hacen 23 + 105 = 128, 233 y −82, porque sumar 105 no cambia ninguno de los restos. El teorema dice que hay exactamente una solución entre 0 y 104; con módulos que tienen factores comunes, exactamente una por debajo de su mínimo común múltiplo.

¿Por qué los módulos deben ser coprimos?

Para la construcción, porque Nᵢ debe tener inverso mod nᵢ, y eso solo existe cuando no tienen factores comunes. Para el teorema en sí, porque los factores comunes hacen que algunas ecuaciones se solapen: entonces un sistema o no tiene solución o tiene menos soluciones distintas, y las soluciones se repiten cada mínimo común múltiplo en lugar de cada producto.

¿Cómo encuentro un inverso modular a mano?

Con el algoritmo de Euclides extendido. Para el inverso de 15 mod 7: 15 = 2 × 7 + 1, así que 1 = 15 − 2 × 7, y 15 × 1 ≡ 1 (mod 7): el inverso es 1. Para 35 mod 3: 35 = 11 × 3 + 2 y 3 = 1 × 2 + 1, así que 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, y el inverso de 35 mod 3 es −1 ≡ 2. Con módulos pequeños también puedes probar simplemente 1, 2, 3, … hasta que el producto dé resto 1.

¿Qué tiene que ver el teorema con los relojes?

Un resto mod n es una posición en un reloj de n horas. Dos relojes de 3 y 5 horas que arrancan juntos y avanzan de hora en hora muestran cada uno de los 15 pares de posiciones una vez antes de volver al principio, porque 3 y 5 no tienen factores comunes. Los relojes de 4 y 6 horas vuelven tras 12 pasos y solo muestran 12 de los 24 pares: una posición impar y una par nunca aparecen juntas.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir la calculadora del teorema chino del resto