viernes, 29 de junio de 2012

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 M1, M2, M3…Mn son números enteros primos entre sí dos a dos y B1, B2, B3,…Bn, otros números enteros cualesquiera, existe otro número natural N único que cumple NºBi (mod Mi) para todo i entre 1 y n.
NºB1(mod M1)
NºB2 (mod M2)
NºB3 (mod M3)

NºBn (mod Mn)

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 N1 y N2 fueran dos soluciones distintas, serían congruentes respecto a todos los módulos M1, M2, M3…Mn  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 Mi y sea M’i = H/Mi.

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


 donde hemos llamado Ei al producto Mi*mi

 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’1=9 ; M’2=10 ; m1=9 (porque 9*9=81º1 (mod 10) ); m2=1 (porque 1*10=10º1 (mod 9) ). Así tenemos que E1=9*9=81 y E2=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 Ei 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 Mi, los valores de Bi y el número de ecuaciones. En el central se calcula H, las Hi 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 Zm×Zn y el conjunto Zmn (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 Z8×Z9 y el conjunto Z72.


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 Zmn, según el teorema chino, corresponde un resto p en Zm y otro q en Zn 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 Zm×Zn le corresponde la suma N+N’ en Zmn. 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 Zm×Zn y el anillo Zmm


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 Zm, será porque no tiene factores primos comunes con m. De igual forma, si q es inversible en Zn, 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 Zm como en Zn. Por tanto, N es inversible en Zmn

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

Volvemos a la tabla ejemplo: 5 es inversible en Z8, 4 es inversible en Z9. 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,