Algoritmo De Euclides.

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.

Contenido [ocultar]

1 Algoritmo original de Euclides

2 Algoritmo de Euclides tradicional

2.1 Generalización

2.2 Descripción formal

3 Algoritmo de Euclides extendido

3.1 Fundamentos

3.2 Descripción formal

4 Aplicaciones

4.1 Simplificar fracciones

4.2 Fracciones continuas

4.3 Inversos modulares

5 Complejidad del algoritmo

6 Implementación en pseudocódigo

7 Referencias

8 Enlaces externos

[editar]Algoritmo original de Euclides

AB y CD los segmentos conmensurables.

Ejemplo del algoritmo original de Euclides.

En la concepción griega de la matemática, los números se entendían como magnitudes geométricas. Un tema recurrente en la geometría griega es el de la conmensurabilidad de dos segmentos: dos segmentos (números) AB y CD son conmensurables cuando existe un tercer segmento PQ el cual cabe exactamente un número entero de veces en los primeros dos, es decir, PQ «mide» (mensura: medida) a los segmentos AB y CD.

No cualquier par de segmentos es conmensurable, como encontraron los pitagóricos cuando establecen que el lado y la diagonal de un cuadrado no son conmensurables, pero en el caso de dos segmentos conmensurables se desea hallar la mayor medida común posible.

Euclides describe en la proposición VII.2 de sus Elementos un método que permite hallar la mayor medida común posible de dos números (segmentos) que no sean primos entre sí, aunque de acuerdo a la época tal método se explica en términos geométricos, lo que se ilustra en la siguiente transcripción.

Para encontrar la máxima medida común de dos números que no sean primos entre sí.

Sean AB y CD los dos números que no son primos uno al otro. Se necesita entonces encontrar la máxima medida común de AB y CD.

Si CD mide AB entonces es una medida común puesto que CD se mide a sí mismo. Y es manifiesto que también es la mayor medida pues nada mayor a CD puede medir a CD. Pero si CD no mide a AB entonces algún número quedará de AB y CD, el menor siendo continuamente restado del mayor y que medirá al número que le precede. Porque una unidad no quedará pues si no es así, AB y CD serán primos uno del otro [Prop. VII.1], lo cual es lo contrario de lo que se supuso.

Por tanto, algún número queda que medirá el número que le precede. Y sea CD midiendo BE dejando EA menor que sí mismo y sea EA midiendo DF dejando FC menor que sí mismo y sea FC medida de AE. Entonces, como FC mide AE y AE mide DF, FC será entonces medida de DF. Y también se mide a sí mismo. Por tanto también medirá todo CD. Y CD mide a BE. Entonces CF mide a BE y también mide a EA. Así mide a todo BA y también mide a CD. Esto es, CF mide tanto a AB y CD por lo que es una medida común de AB y CD.

Afirmo que también es la mayor medida común posible porque si no lo fuera, entonces un número mayor que CF mide a los números AB y CD, sea éste G. Dado que G mide a CD y CD mide a BE, G también mide a BE. Además, mide a todo BA por lo que mide también al residuo AE. Y AE mide a DF por lo que G también mide a DF. Mide también a todo DC por lo que mide también al residuo CF, es decir el mayor mide al menor, lo cual es imposible.

Por tanto, ningún número mayor a CF puede medir a los números AB y CD. Entonces CF es la mayor medida común de AB y CD, lo cual se quería demostrar.

Euclides. Elementos VII.2

En lenguaje moderno, el algoritmo se describe como sigue:

Dados dos segmentos AB y CD (con AB>CD), restamos CD de AB tantas veces como sea posible. Si no hay residuo, entonces CD es la máxima medida común.

Si se obtiene un residuo EA, éste es menor que CD y podemos repetir el proceso: restamos EA tantas veces como sea posible de CD. Si al final no queda un residuo, EA es la medida común. En caso contrario obtenemos un nuevo residuo FC menor a EA.

El proceso se repite hasta que en algún momento no se obtiene residuo. Entonces el último residuo obtenido es la mayor medida común.

El hecho de que los segmentos son conmesurables es clave para asegurar que el proceso termina tarde o temprano

[editar]Algoritmo de Euclides tradicional

Al dividir entre (números enteros), se obtiene un cociente y un residuo . Es posible demostrar que el máximo común divisor de y es el mismo que el de y (Sea c el máximo común divisor de y ,.Como a=bq+r y c divide a y a divide también a r.Si existiera otro número mayor que c que divide a b y a r, también dividiría a a , por lo que c no sería el mcd de y , lo que contradice la hipótesis). Éste es el fundamento principal del algoritmo. También es importante tener en cuenta que el máximo común divisor de cualquier número y es precisamente . Para fines prácticos, la notación significa máximo común divisor de y .

Según lo antes mencionado, para calcular el máximo común divisor de 2366 y 273 se puede proseguir de la siguiente manera:

Paso Operación Significado

1 2366 dividido entre 273 es 8 y sobran 182

2 273 dividido entre 182 es 1 y sobran 91

3 182 dividido entre 91 es 2 y sobra 0

La secuencia de igualdades implican que . Dado que , entonces se concluye que . Este mismo procedimiento se puede aplicar a cualesquiera dos números naturales. En general, si se desea encontrar el máximo común divisor de dos números naturales y , se siguen las siguientes reglas:

Si entonces y el algoritmo termina

En otro caso, donde es el resto de dividir entre . Para calcular se utilizan estas mismas reglas

Asuma que llamamos y . Aplicando estas reglas se obtiene la siguiente secuencia de operaciones:

Paso Operación Significado

1 dividido entre es y sobran

2 dividido entre es y sobran

3 dividido entre es y sobran

dividido entre es y sobran

dividido entre es y sobra

Como la sucesión de residuos va disminuyendo, eventualmente un residuo tiene que ser cero y es en ese momento cuando el algoritmo termina. El máximo común divisor es precisamente (el último residuo que no es cero).

[editar]Generalización

En realidad el algoritmo de Euclides funciona no sólo para los números naturales, sino para cualesquiera elementos donde exista una "división con residuo". A este tipo de divisiones se les llama divisiones euclidianas y a los conjuntos donde se puede definir dicha división se les llama dominios euclídeos. Por ejemplo, el conjunto de los números enteros y el de los polinomios con coeficientes racionales son dominios euclídeos porque podemos definir una división con residuo (véase División polinomial). De esta manera, se puede calcular el máximo común divisor de dos números enteros o de dos polinomios.

Por ejemplo, para calcular el máximo común divisor de los polinomios y el algoritmo de Euclides sugiere la siguiente secuencia de operaciones:

Paso Operación Significado

1 dividido entre es y sobra

2 dividido entre es y sobra

3 dividido entre es y sobra 0

De esta manera se concluye que su máximo común divisor es .

[editar]Descripción formal

Se puede expresar este algoritmo de manera más formal usando pseudocódigo. En este caso la expresión "" significa "el residuo de dividir entre " (véase Aritmética modular).

Algoritmo 1 de Euclides

Entrada: Valores y pertenecientes a un dominio euclídeo

Salida: Un máximo común divisor de y

,

Mientras haga lo siguiente:

El resultado es:

Vale la pena notar que este algoritmo no es eficiente ser implementado directamente en una computadora, ya que requeriría memorizar todos los valores de .

[editar]Algoritmo de Euclides extendido

El algoritmo de Euclides extendido permite, además de encontrar un máximo común divisor de dos números enteros y , expresarlo como la mínima combinación lineal de esos números, es decir, encontrar números enteros y tales que . Esto se generaliza también hacia cualquier dominio euclideano.

[editar]Fundamentos

Existen varias maneras de explicar el algoritmo de Euclides extendido, una de las más comunes consiste en la siguiente:

Usar el algoritmo tradicional de Euclides. En cada paso, en lugar de " dividido entre es y de resto " se escribe la ecuación (véase algoritmo de la división).

Se despeja el resto de cada ecuación.

Se sustituye el resto de la última ecuación en la penúltima, y la penúltima en la antepenúltima y así sucesivamente hasta llegar a la primera ecuación, y en todo paso se expresa cada resto como combinación lineal.

Sin embargo, en aras de la comprensión y memorización de este algoritmo,

...