El Teorema Chino de los Restos apareció por primera vez en un libro del matemático chino Sun Tzi (s. III). Versiones del teorema volvieron a aparecer a partir del siglo X, tras introducción en occidente de las cifras arábigas y el sistema numérico posicional y se recogió en las primeras aritméticas como, por ejemplo, en el Liber Abaci (1202) de L. Fibonacci (1170-1250), que fue el primer libro completo de aritmética práctica utilizando los numerales indo-arábigos. El modelo de exposición y la selección de los temas tratados en el Liber Abaci fue seguido y, en los años siguientes por numerosos manuscritos sobre Aritmética Mercantil en las que se utilizaban las cifras indo arábigas, la numeración posicional y en las que se exponían algoritmos numéricos de cálculo.
El teorema de Sun Tzi se utiliza para operar con números grandes trabajando con números pequeños. Se basa en jugar con las congruencias y el Teorema demuestra que si dividimos un número N en partes de n1 elementos, pudiendo sobrar una cantidad r1 < n1, después dividimos N en partes de n2 elementos, pudiendo sobrar una cantidad r2 < n2 , luego en partes de n3 elementos pudiendo sobrar una cantidad r3 < n3 y así sucesivamente. El teorema afirma que podemos determinar el número original N siempre que n1, n2, n3, … sean primos entre sí.
El enunciado del problema original que implica el teorema de los residuos chinos lo recogió Sun Zi en su obra del modo siguiente:
Disponemos de un número no conocido de objetos pero sabemos que si hacemos grupos de tres sobran dos; si hacemos grupos de cinco sobran tres y si hacemos grupos de siete sobran dos. ¿Cuántas cosas pueden ser?
Sun Tzi resolvió el problema de la siguiente forma: [El problema lo podemos escribir N ≡ 2 (mod 3), N ≡ 3 (mod 5), N ≡ 2 (mod 7)]
Estimó que el problema se podía resolver usando los números 15, 21 y 70, que eran, respectivamente, múltiplos de 3·5, 7·3 ⋅y de 5·7, (productos de los módulos de las congruencias dos a dos). Observó que la suma:
2·15+ 3·21 + 2·70 + = 233, era una solución.
Luego, restó a 233 múltiplos de 7·5·3 = 105 (productos de los tres módulos) tantas veces como fuera posible, obteniendo el número 23, siendo este número el menor entero positivo que es solución del problema.
[Sun Zi pensó de modo parecido a este:
- 15 (y cualquier múltiplo suyo) dará resto cero cuando se divida entre 3 o entre 5 y buscó entre los múltiplos de 15 uno que diera resto 2 al dividir entre 7 y obtuvo el 2·15 =30, que cumple 30 = 4·7 + 2
- 21 (y cualquier múltiplo suyo) dará resto cero cuando se divida entre 3 o entre 7 y buscó, entre los múltiplos de 21, uno que diera resto 3 al dividir entre 5 y obtuvo el 3·21 = 63, que cumple 63 = 12·5 + 3
- 35 (y cualquier múltiplo suyo) dará resto cero cuando se divida entre 5 o entre 7 y buscó, entre los múltiplos de 35, uno que diera resto 2 al dividir entre 3 y obtuvo el 2·70 =4·35 = 140, (podría haberle servido el 35)], que cumple 140 = 46·3 + 2
- La suma 30 + 63 + 140 = 233 le dió una solución, como le podía haber servido también 30 + 63 + 35 = 128)
Antes de comenzar con casos elementales del teorema de los residuos recordaremos un poco de vocabulario de congruencias numéricas:
Definición.- Dos números enteros a y b son congruentes respecto a un número, (o módulo), m y lo escribiremos a ≡ b (mod m), si al dividirlos entre m dan el mismo resto.
Ejemplo: 19 ≡ 35 (mod 8), 25 ≡ 11 (mod 7) 37 ≡ 13 (mod 6)
Consecuencias de la definición:
- El dividendo y el resto de una división entera son congruentes respecto del divisor. Lo que quiere decir:
Si D = dividendo, m = divisor, c = cociente y r = resto, entonces: D ≡ r (mod m)
- Todo múltiplo de m es congruente con 0 (cero), respecto de m. Es decir: ṁ ≡ 0 (mod m)
- Teorema fundamental de las congruencias: La condición necesaria y suficiente para a y b sean congruentes respecto a un módulo m, es que su diferencia sea múltiplo del módulo. Es decir: a ≡ b (mod m) si y sólo si a – b = ṁ
Problema 1: (Calcular un número que da restos iguales respecto a diferentes módulos). Calcula el mínimo número de piedras de un montón tal que si se cuentan de dos en dos, de tres en tres, de cuatro en cuatro, de cinco en cinco y de seis en seis sobra una piedra en todos los casos.
Solución: Buscar un número N que da resto 1 al dividirlo entre 2, entre 3, entre 4, entre 5 y entre 6. Es decir:
N ≡ 1 (mod 2), N ≡ 1 (mod 3), N ≡ 1 (mod 4), N ≡ 1 (mod 5), N ≡ 1 (mod 6)
Tendrá que ser, a la vez, un múltiplo de 2, de 3, de 4, de 5 y de 6 más una unidad, y como buscamos el menor número:
N = m.c.m (2, 3, 4, 5, 6) + 1= 61
Problema 2: (Calcular un número que da restos por defecto iguales respecto a diferentes módulos). Calcula el mínimo número de piedras de un montón tal que si las cuento de dos en dos da resto uno, de tres en tres da resto dos, de cuatro en cuatro da resto tres, de cinco en cinco da resto cuatro y de seis en seis sobra resto cinco
Solución: Buscar un número N que da resto 1 al dividirlo entre 2; 2 al dividirlo entre 3, 3 al dividirlo entre 4, 4 al dividirlo entre 5 y 5 al dividirlo entre 6. Es decir: Tendrá que ser, a la vez, un múltiplo de 2, de 3, de 4, de 5 y de 6 menos una unidad,
N ≡ -1 (mod 2), N ≡ -1 (mod 3), N ≡ -1 (mod 4), N ≡ -1 (mod 5), N ≡ -1 (mod 6)
y, como buscamos el menor número: N = m.c.m.(2, 3, 4, 5, 6) – 1= 59
Problema 3: (Restos distintos) Calcular un número que dividido entre 5 de resto 3 y dividido entre 7 de resto 4.
En lenguaje de congruencias N ≡ 3 (mod 5), N ≡ 4 (mod 7).
Busquemos dos números X e Y tales que
X dividido entre 5 de resto 0 (sea múltiplo de 5) y que dividido entre 7 de resto 4, por ejemplo 25 e
Y dividido entre 7 de resto 0 (sea múltiplo de 7) y dividido entre 5 de resto 3, por ejemplo 28.
El número X + Y = 28 + 25= 53 cumple las dos condiciones exigidas, ya que 53 dividido entre 5 da resto 3 y dividido por 7 de resto 4. Pero 53 no es el menor número que cumple la condición exigida, restando un múltiplo del producto de los módulos, 35, el más pequeño será 53 – 35 = 18.
