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,

jueves, 21 de junio de 2012

La herencia de Euclides (3) El anillo Zm

Recordábamos en la entrada anterior la formación del anillo Zm mediante clases de restos hasta formar el conjunto {0, 1, 2, … m-1}. Repasa estas páginas si lo deseas:

http://es.wikipedia.org/wiki/Aritm%C3%A9tica_modular
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm
http://mathworld.wolfram.com/ModularArithmetic.html

A este conjunto Zm se le puede dotar de la suma y el producto módulo m que lo convierten en un anillo conmutativo con unidad, que es el resto 1. Esto lo tienes en

http://personales.unican.es/ruizvc/algebra/anillos1.pdf
http://en.wikipedia.org/wiki/Ring_(mathematics)
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm#residuales

En realidad, bastaría afirmar que Zm es el anillo cíclico de m elementos. Busca en la Red ese concepto, que es muy sencillo. Por esta estructura cíclica se pensó en llamarles anillos por primera vez.

En los anillos con unidad son importantes los elementos inversibles. De ellos trataremos aquí.

Un elemento A de Zm es inversible si existe otro elemento X de Zm tal que A*Xº1 (mod m) Según vimos en la entrada anterior, esta ecuación tiene solución única siempre que A sea primo con el modulo m. Luego los restos primos con m son inversibles.

Por el contrario, si A y m tienen un divisor común, para que la ecuación tuviese solución debería ser divisor también de 1, lo que es imposible. Si el elemento A tiene divisores comunes con m, entonces A no es inversible.

Llamamos divisor de cero en un anillo a aquel elemento A que multiplicado por cierto elemento no nulo C del anillo, da un producto nulo: A*Cº0. En este caso en el que A tiene factores comunes con m, es un divisor de cero, porque si D=MCD(A,m), tendremos que A=A’*D y m=m’*D. Multiplicando A por m’ (que es no nulo) resulta Am’=A’D*m/D=A’m, que es congruente con cero, luego A*m’º0 (mod m) y por tanto divisor de cero.

Los divisores de cero no son inversibles, porque si A fuera inversible y divisor de cero, se daría una igualdad del tipo A*Cº0 con C distinto de cero, pero multiplicando por el inverso resultaría:
A-1*A*C=C=A-1*0 lo que daría C=0 en contra de lo supuesto.

Así que:

 Si el elemento A es primo con el módulo m, entonces es inversible, es decir, que existe algún otro elemento B tal que A*B=B*Aº1. En entradas anteriores vimos cómo encontrarlo mediante el algoritmo extendido de Euclides.

 Si el elemento A no es primo con m, es un divisor de cero, y por tanto no inversible.

Grupo de inversibles

El producto de dos inversibles A y B también lo es, y su inverso es B-1*A-1, ya que

 (B-1*A-1)*A*BºB-1*(A-1*A)*BºB-1*1*Bº1

Como el 1 es inversible trivialmente y el inverso también, tenemos que los inversibles forman grupo abeliano, llamado grupo de las unidades Z*m


Como es conocido, la función indicatriz de Euler cuenta los números menores que m y primos con él, por tanto, el cardinal del grupo Z*m coincide con la indicatriz o función j(x) de Euler.

Si m es primo, todos los elementos son inversibles y Zm se convierte en un cuerpo, pero yo creo que eso ya lo sabías.

La hoja que estamos usando en esta serie de entradas también nos da el grupo Z*m de unidades de Zm. Nos seguimos basando en el algoritmo de Euclides extendido.

Para cada elemento de Zm se va llamando a la rutina euclides(X,m) (de ahí la ventaja de tenerla implementada como una rutina en Basic), mediante la cual se encuentra el MCD(X,m). Si es igual a 1, se escribe el inverso junto al elemento. En la imagen puedes ver el desarrollo para m=12, y nos da como elementos inversibles 1, 5, 7 y 11.




Contando los inversibles se encuentra la indicatriz de Euler, a la que volveremos próximamente.

Finalmente, a la derecha del esquema se construye el grupo multiplicativo de unidades. Observa que, como era de esperar, todos los productos pertenecen al conjunto {1, 5, 7, 11}

Con esta hoja es fácil comprender el teorema de Euler. Observa, por ejemplo, la fila que corresponde al valor 7:{7, 11, 1, 5} Esto quiere decir que 7*1º7, 7*5º11, 7*7º1 y 7*11º5. Imagina que multiplicamos las cuatro congruencias miembro a miembro:

7*1*7*5*7*7*7*11º7*11*1*5   Simplificamos entre 7*11*1*5  (porque son inversibles, si no, no se podría) y queda

7*7*7*7 º1, es decir 74º1. Pero 4 es la función de Euler de 12 y de ahí la comprobación del teorema:

7 j(12) º1 (mod 12)

Esto no es una demostración, pero si repites lo mismo con valores generales p y m con p inversible, es fácil demostrar que p j(m) º1 (mod m)

Orden de un elemento

Dado un elemento inversible a, llamaremos orden de ese elemento al mínimo número entero tal que arº1.

Según el teorema citado, ese valor existe y puede ser j(m). Si es menor, ha de ser un divisor suyo. En efecto, supongamos que j(m) no fuera múltiplo del orden r. Entonces efectuando la división entera entre ambos quedaría j(m)=qr+s, con s<r. Aplicamos esa potencia al elemento a y obtendríamos
1ºaj(m) ºaqr+sºaqr*asº as , luego asº1 en contra del carácter mínimo de r.

Así que el orden ha de ser un divisor de la función j(m)

Hemos incorporado a la hoja el cálculo del orden de los elementos inversibles, pero sería un buen ejercicio que los comprobaras usando la tabla de multiplicar. En la imagen puedes consultar el orden de los elementos en el caso de m=10. Observa que los cuatro son divisores de la indicatriz j(10)=4



miércoles, 13 de junio de 2012

La herencia de Euclides (2) La ecuación Ax=B (mod m)

La ecuación AxºB (mod m)

También aquí remitimos a otras páginas para entender las condiciones de esta ecuación. En primer lugar has de conocer la teoría elemental de las congruencias o Aritmética modular. Si no es así, puedes visitar

http://hojamat.es/parra/modular.pdf
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm
http://mathworld.wolfram.com/ModularArithmetic.html

Dentro de esta teoría uno de los primeros temas importantes es el de la resolución de la ecuación lineal AxºB (mod m)  y lo traemos aquí por su relación con el algoritmo de Euclides. En efecto, la ecuación dada equivale a exigir que Ax y B se diferencien en un múltiplo de m, es decir, que Ax+Cm=B. Si leíste la entrada anterior, esto te recordará la Identidad de Bezout.

¿Qué sabes de la estructura de anillo? La repasaremos en la siguiente entrada de esta serie. Por ahora sólo tienes que recordar que en el Álgebra Elemental la ecuación Ax=B para números reales se resuelve multiplicando por el inverso de A, si es que lo posee (siendo distinto de cero en este caso), con lo que tendremos A-1Ax=1x=x=A-1B, que es una solución para x.

En los anillos en general no todo elemento posee un inverso, es decir, otro elemento que multiplicado por él lo convierta en la unidad (si esa unidad existe – ver http://es.wikipedia.org/wiki/Anillo_unitario).
En el caso de las congruencias, el anillo Zm de las clases de restos módulo m está formado por las clases  {0,1,2,3,…m-1} a las que llamaremos restos, y en ellos existen algunos  que pueden no tener inverso. Por ejemplo, si m=9 los elementos de Z9 son los restos {0,1,2,3,…8} y si elegimos el 6, ningún múltiplo de 6 produce un 1 como resto módulo 9. Veamos (haz tú los cálculos mentalmente para practicar):

6*1º6 (mod 9);   6*2º3 (mod 9); 6*3º0 (mod 9); 6*4º6 (mod 9); 6*5º3 (mod 9); 6*6º0 (mod 9); 6*7º6 (mod 9); 6*8º3 (mod 9)

Nunca resulta un producto congruente con 1, luego el 6 carece de inverso.

Si repasas la teoría del anillo Zm (lo haremos también en la siguiente entrada) descubrirás que los elementos inversibles son los números primos con m. Como estamos hablando del conjunto de restos {0,1,2,3,…m-1}, el número de inversibles coincidirá con la indicatriz de Euler, como también veremos más adelante. Ya ves, todo se relaciona.

En la resolución de A*xºB (mod m) se presentan estos tipos:

1. Si A es primo con m, existe una sola solución x º A-1*B (mod m), por ser A inversible.

2. Si MCD(A,m)=d, con d mayor que 1, para que exista solución ha de ser B múltiplo de d. En ese caso se simplifican los tres números A, B y m con lo que se pasa al primer caso. Se puede encontrar una primera solución º A-1*B (mod m) y existirán en total d soluciones, que vienen dadas por la fórmula xr = x0+r*m/d (ver las páginas recomendadas)

En la segunda hoja de la herramienta que estamos usando (Euclides.ods o Euclides.xlsx en
http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm) se sigue este procedimiento. Escribimos los tres datos A,B y m. Sin usar macros, la hoja determina si tiene solución o no y si en caso de tenerla es única o múltiple. Si existe, simplifica los datos.



En la imagen se intenta resolver 6Xº4 (mod 10), que tomaremos como ejemplo. La hoja detecta que existen varias soluciones y simplifica 6, 4, 10 a 3, 2 y 5.

El truco está en las celdas I9, I10 y J10. Investiga y aprenderás.

Abajo figura la resolución, que se basa en la rutina Euclides(X,Y) ya explicada en la entrada anterior y en ella se dan estos pasos:


- Se calculan las reducidas y se toma el penúltimo denominador DEN(5)=2, que es un buen candidato a inverso de A (ver la identidad de Bezout en la entrada anterior).

- Se comprueba el último producto cruzado NUM(6)*DEN(5)-DEN(6)*NUM(5)=3*2-1*5=1 y como vale 1, DEN(5)=2 es el inverso por ser 3*2º1 (mod 5. Si el producto cruzado hubiera valido -1 deberíamos haber cambiado de signo.

- Según hemos explicado, la solución será igual a INV(A)*B=2*2=4. En efecto, 6*4º4 (mod 10)

- El MCD(6,4)=2, luego existirán dos soluciones a la ecuación (hablamos en Z10, porque en Z existirían infinitas). Según la teoría, bastará ir sumando el cociente 10/2=5 a las soluciones, lo que nos da (lo ves en la imagen) las soluciones 4 y 9.

Caso homogéneo

Si B es cero, esta ecuación queda como A*x º 0 (mod m) por lo que además de la solución trivial x=0 existirán otras si M.C.D(A,m)>1, y entonces A se confirmará como divisor de cero. Por ejemplo, resuelve con la hoja 6*x º 0 (mod 9) y obtendrás las soluciones 0, 3 y 6, ya que M.C.D(6,9)=3>1. Sin embargo, resuelve 6*x º 0 (mod 7) y sólo obtendrás x=0, ya que en este caso 6 es inversible.

Te proponemos una demostración o comprobación, según te atrevas.

Las diferencias existentes entre las soluciones de la ecuación A*x º B (mod m) son soluciones de la homogénea A*x º 0 (mod m). Inversamente: dada una solución de A*xºB (mod m), si le vamos sumando por separado las soluciones de la homogénea, resulta el conjunto de todas las soluciones de A*x º B (mod m

Nuestro único objetivo ha sido el que veas la relación de la resolución de esta ecuación con el algoritmo de Euclides y que recorras toda la resolución efectuada por la hoja para comprender mejor los detalles de la misma. Cualquier otro aspecto lo podrás ver en las páginas recomendadas, aunque tampoco se puede decir mucho más.

lunes, 4 de junio de 2012

La herencia de Euclides (1) El algoritmo

Hoy iniciamos una serie de entradas dedicadas al algoritmo extendido de Euclides y sus aplicaciones. La orientación será práctica y elemental, y se basará en una hoja de cálculo que abarca todas las técnicas que se explican en la serie. Quien desee profundizar deberá visitar las páginas recomendadas.

No vamos aquí a explicar el algoritmo de Euclides. Mucho mejor lo desarrollan estas páginas y documentos:

http://es.wikipedia.org/wiki/Algoritmo_de_Euclides

http://mathworld.wolfram.com/EuclideanAlgorithm.html

http://hojamat.es/parra/divisibilidad.pdf

Así que supondremos que nuestros lectores conocen el algoritmo y poseen alguna noción de su variante extendida, que viene a reducirse al desarrollo en fracciones continuas y del cálculo de convergentes o reducidas. También se puede interpretar como el recorrido inverso del algoritmo hasta llegar a la Identidad de Bezout. Si no te suena esto mucho puedes profundizar en las páginas anteriormente citadas y en estas:

http://hojaynumeros.blogspot.com/2009/09/fracciones-continuas-1-definicion.html

http://hojaynumeros.blogspot.com/2009/10/fracciones-continuas-2-reducidas.html

y mejor todavía http://www.hojamat.es/parra/fraccioncont.pdf


El algoritmo extendido supone tres fases de calculo:

(1) El algoritmo para el cálculo del MCD. Lo recordamos en esta imagen:








(2) Se despejan los restos a partir de las identidades de la división entera:


(3) Sustituimos r1 en la fórmula de r2, con lo que éste dependerá sólo de D y d. Proseguimos sustituyendo r2 en r3, éste en r4 y así hasta llegar al MCD que dependerá entonces sólo de D y d y habremos obtenido la identidad de Bezout: MCD=m*D+n*d

Este proceso puede complicarse algebraicamente, por lo que se sustituye por cálculos más automáticos, como el algoritmo de las reducidas, que explicamos en

http://hojaynumeros.blogspot.com/2009/10/fracciones-continuas-2-reducidas.html

Aquí nuestro objetivo es recorrer con una hoja de cálculo la técnica del algoritmo de Euclides extendido y su aplicación a la resolución de ecuaciones lineales en Zn, del teorema chino, los elementos inversibles de ese anillo Zn y su aplicación a las propiedades de la indicatriz de Euler. Todo un programa de trabajo que nos ocupará algunas entradas.

Rutinas y funciones

Para este estudio hemos confeccionado una hoja de cálculo en la que todo el algoritmo extendido se puede expresar mediante funciones. Así, el segundo cociente puede escribirse, según veremos, como COC(2), una convergente en el desarrollo mediante fracciones continuas como NUM(4) y DEN(4), y así con otras.

Esto se ha concebido así porque existen varios cálculos que usan el algoritmo extendido, y es preferible, en lugar de usar varias celdas cada vez, efectuar una llamada a la rutina Euclides(x;y) que nos devuelve los resultados en forma de función.

Para entenderlo es mejor estudiar la primera hoja de la herramienta que hemos confeccionado (Euclides.ods o Euclides.xlsx) y que puedes descargar en esta dirección

http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm












Se observa que en la parte superior se desarrolla el algoritmo de Euclides sin uso de macros. El M.C.D(3210,6540) se obtiene por las clásicas divisiones enteras en  las que los restos pasan a ser  divisores. Aprenderás mucho de hoja de cálculo si la analizas.

La segunda parte se activa con un botón. Esto significa que hay una macro detrás. En efecto, es la subrutina Euclides(X;Y), donde X e Y son los números a los que se les calcula el M.C.D. Estas son explicaciones sobre la programación de la hoja, pero puedes prescindir de ellas. Toma esto como una herramienta que sistematiza los cálculos. Lo importante es que según ves en la imagen, aparecen todos los datos en forma de función.

COC: Son los cocientes que aparecen en el algoritmo aplicado a 3210 y 6540 (ver imagen), 0, 2, 26, 1, 3. Estos serían también los cocientes de la fracción continua que desarrolla 3210/6540. Así que esta hoja te permite efectuar esos desarrollos. Puedes comprobar los ejemplos que da Rafael Parra en su documento para entender esto mejor.

Reducidas: También las reducidas de la fracción las tienes en la parte derecha en forma de funciones. Las rotuladas como NUM son los numeradores y DEN los denominadores.

Por curiosidad, efectúa productos cruzados entre ellos y verás que siempre obtienes +1 o -1. Por ejemplo, 26*55-53*27=-1. Esto se puede demostrar que es así. Consulta las páginas recomendadas. El más interesante es el que se forma con las dos últimas: 27*218-55*107=1, por varias razones:
  • La última reducida coincide con la fracción primitiva simplificada 3210/6540=218/107, luego esta hoja también te sirve para simplificar fracciones dividiéndolas entre el M.C.D. del numerador y el denominador, que por cierto en la hoja no se llega a efectuar esa división nunca. El algoritmo extendido simplifica los datos originales sin dividir.
  • La igualdad 27*218-55*107=1 multiplicada por el MCD 30 y quizás con un cambio de signo (que no es el caso en este ejemplo) se convierte en la Identidad de Bezout, que la tienes también reflejada en la hoja: El MCD 30 expresado como combinación lineal entera de 3210 y 6540: ( -55)* 3210+( 27)* 6540= 30. Además, 30 es el mínimo número entero positivo que satisface una relación lineal de este tipo. Siempre me ha encantado esta propiedad, que algunos autores toman como definición del MCD. Y como señalábamos más arriba, sin usar el concepto de divisor.
  • Adelantando el contenido de la siguiente hoja, la igualdad 27*218-55*107=1 permite reconocer 27 como el inverso de 218 en el anillo Z107, pero esto es correr mucho por ahora. Lo abordaremos en otra entrada.
Con esta hoja no se pretende sustituir el cálculo manual. En este blog siempre insistiremos en su necesidad. Sólo se pretendía el poder resumir en una sola página todas las consecuencias inmediatas del algoritmo de Euclides extendido.

En otra entrada posterior lo aplicaremos a la resolución de la ecuación lineal en congruencias. Puedes ir consultando la teoría mientras tanto.