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.
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.
No hay comentarios:
Publicar un comentario