Teorema Chino del resto

El Teorema chino del resto da las condiciones bajo las cuales se garantiza que un sistema de ecuaciones lineales tenga una solución. Si conocemos los restos de la división de un entero n por otros enteros (a,b), entonces podemos determinar de manera única el resto de la división de n por el producto de esos enteros, obligatoriamente los divisores deben ser coprimos. A los coprimos los representamos como MCD (Máximo Común Divisor) (a , b ) = 1, ambos tienen el mismo resto. Una de las características de este teorema es que permite realizar cálculos con números grandes utilizando cálculos de números más pequeños.

 

En el siglo IV, Sun Tzu Suan Ching, en otras traducciones Sunzi Suanjing, se preguntó:

Tengo un conjunto de objetos. Cuando los cuento de tres en tres, me sobran dos; cuando los cuento de cinco en cinco, me sobran tres; cuando los cuento de siete en siete, me sobran dos. ¿Cuántos objetos poseo?.

 

Ahora lo vemos así:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

el resultado X = 23

 

Más tarde Abu ‘Ali al-Hasan ibn al-Haytham (Alhazen), en el siglo X, plantea y resuelve problemas, en el libro “Opuscula” que implican congruencias utilizando dos métodos, el primero es canónico, (mal llamado teorema de Wilson), mientras que el segundo implica una versión del teorema chino del resto.

 

El primero en unificar y sentar las bases de la moderna teoría de congruencias fue Carl Friedrich Gauss en el libro publicado en 1.801 “Disquisitiones Arithmeticae”. Su definición dice:

 

Dos números son congruentes entre sí respecto a un módulo m, si su diferencia es un múltiplo de m. Así, 8 es congruente a 22 módulo 7, ya que 22 – 8 = 14 que es múltiplo de 7, a esta relación se le denota simbólicamente por 8 ≡ 22 (mod 7). Vemos entonces que para que dos números sean congruentes entre sí módulo 7, basta que tengan el mismo resto al ser divididos entre 7.

 

En el mismo libro introduce el signo () para indicar que a es congruente con b módulo m.

 

El teorema está presente en muchas áreas de las matemáticas, en los sistemas de cifrado de información (cifrado pohlig-hellman), en la vida cotidiana su utilización la vemos en la mayoría de las versiones de cifrado/descifrado  RSA que usan el teorema durante la firma de certificados HTTPS. Lo podemos ver en el navegador cuando nos aparecen esas siglas al conectarnos a una página web.