La herencia de Euclides (4) El teorema chino de los restos

Este teorema lo conocemos todos, pero quizás no hayamos pensado que es la garantía de algún isomorfismo de anillos. Lo iremos viendo.

Se enuncia así:

Si M₁, M₂, M₃…M_n son números enteros primos entre sí dos a dos y B₁, B₂, B₃,…B_n, otros números enteros cualesquiera, existe otro número natural N único que cumple NºB_i (mod M_i) para todo i entre 1 y n.
NºB₁(mod M₁)
NºB₂ (mod M₂)
NºB₃ (mod M₃)
…
NºB_n (mod M_n)

Todas las demás soluciones del sistema son congruentes con N respecto a un módulo H igual al producto de los módulos.

La demostración la puedes consultar en cualquier manual. A nosotros nos va interesar especialmente la unicidad de la solución respecto al módulo H. Su fundamento está en que si dos números son congruentes respecto a módulos primos entre sí, también serán congruentes respecto al producto de los módulos. Así, en este caso, si N₁ y N₂ fueran dos soluciones distintas, serían congruentes respecto a todos los módulos M₁, M₂, M₃…M_n  y por tanto congruentes respecto a H, que es lo que garantiza su unicidad.

La resolución más popular de este sistema de ecuaciones es la que ideó Gauss:

Algoritmo de Gauss

Para calcular el número N se sigue el proceso:

 Llamemos H al producto de todos los módulos M_i y sea M’_i = H/M_i.

 Se buscan unas m_i tales que m_i.M’_iº1 (mod M_i) es decir, sus inversos,  y entonces la solución será:

 donde hemos llamado E_i al producto M_i*m_i

 Se puede demostrar que las demás soluciones son congruentes con N módulo H

Ejemplo

Encontrar un número n tal que al dividirlo entre 10 nos dé de resto 7, y al dividirlo entre 9 obtengamos un resto de 3.

H=9.10 = 90 ; M’₁=9 ; M’₂=10 ; m₁=9 (porque 9*9=81º1 (mod 10) ); m₂=1 (porque 1*10=10º1 (mod 9) ). Así tenemos que E₁=9*9=81 y E₂=10*1=10 y por último:

N=81.7+10.3= 597.  Lo reducimos a módulo 90 y queda 57. En efecto, 57º7 (mod 10) y 57º3 (mod 9)

Para encontrar las demás soluciones bastará con ir sumando H=90: 57, 147, 237, 327,…

Estos coeficientes E_i tienen la ventaja de que sólo dependen de los módulos, por lo que se pueden tener almacenados si se van a usar varias veces. Por ejemplo, si el resto deseado para módulo 10 hubiese sido el 2 y para módulo 9 el 6, la solución hubiera sido N=81.2+10.6=162+60=222º42 (mod 90) y se cumple que el resto de 42 respecto a 10 es 2 y respecto a 9 es 6, como deseábamos.

Ya te habrás imaginado que vendría la hoja de cálculo en nuestro auxilio para librarnos de algunos cálculos si el número de ecuaciones aumenta. En la imagen tienes el desarrollo del ejemplo anterior:

En la región superior escribimos los módulos M_i, los valores de B_i y el número de ecuaciones. En el central se calcula H, las H_i y sus inversos (mediante el algoritmo de Euclides interno que estamos usando en esta serie). Por último, se efectúa la suma de los productos triples y se reduce a módulo H, se escriben varias soluciones y se comprueba la primera.

El caso de dos ecuaciones

Si la solución de este problema es única, podríamos definir una función y(a,b,m,n) tal que a cada par de enteros a y b y dos módulos m y n primos entre sí les asignara la solución N tal que Nºa (mod m)  y  Nºb (mod n). Si los módulos no fueran primos entre sí le podríamos asignar el valor de alarma, por ejemplo el cero.

Por otra parte, para todo entero N existen dos enteros únicos a y b tales que Nºa (mod m)  y  Nºb (mod n). Por tanto, tenemos delante una correspondencia biunívoca entre el conjunto Z_m×Z_n y el conjunto Z_mn (Recuerda que m y n han de ser coprimos).

Esta biyección la hemos representado en la hoja de cálculo que nos sirve de herramienta en esta serie. En una hoja dedicada a la misma puedes consultar las distintas correspondencias. En la imagen tienes la existente entre Z₈×Z₉ y el conjunto Z₇₂.

Pero esta correspondencia es más fuerte, porque constituye un isomomorfismo de anillos para la suma y el producto. En efecto, sabemos que para cada resto N de Z_mn, según el teorema chino, corresponde un resto p en Z_m y otro q en Z_n y que esa correspondencia es biunívoca. Supongamos otro N’ que se corresponda con p’ y q’ respectivamente. Así, si N’ºp’ (mod m) y N’ºq' (mod n), podemos sumar y multiplicar miembro a miembro ambas congruencias y quedará: N+N’ºp+p’ (mod m) y de igual forma N+N’ºq+q’ (mod n). Por tanto, a la suma (p,q)+(p’+q’) en Z_m×Z_n le corresponde la suma N+N’ en Z_mn. Esto nos demuestra que la correspondencia es un homomorfismo para la suma. Igual razonaríamos para el producto.

Por tanto, nuestra función y quedará como un isomorfismo entre anillo Z_m×Z_n y el anillo Z_mm


y(a+a’, b+b’)= y(a, b)+ y(a’, b’)   y  y(a*a’, b*b’)= y(a, b)* y(a’, b’)

Compruébalo en la tabla de más arriba m=8 y n=9:y(4,7)=52, :y(2,4)=58 y si sumamos modularmente, y(6,2)=38, que es congruente con 52+58=110, módulo 72. Si multiplicamos modularmente ocurre lo mismo: y(0,1)=64 y 52*58=3016º64 (mod 72)

Correspondencia entre inversibles

Si el resto p es inversible en Z_m, será porque no tiene factores primos comunes con m. De igual forma, si q es inversible en Z_n, no compartirá factores con n. Si aplicamos la función y(p,q)=N (si suponemos que m y n son coprimos), este resultado N será coprimo con m y con n, pues en caso contrario produciría divisores de cero tanto en Z_m como en Z_n. Por tanto, N es inversible en Z_mn

La correspondencia y(p,q)=N convierte inversibles en inversibles.

Volvemos a la tabla ejemplo: 5 es inversible en Z₈, 4 es inversible en Z₉. Les aplicamos la función y y según la tabla queda y(5,3)=13, que es inversible módulo 72.

La consecuencia de esto queda para otra entrada,