algoritmo de euclides

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 porEuclides 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 áreascomo á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 Aplicaciones4.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. Untema 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 cuandoestablecen 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 enté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 mayormedida pues nada mayor a CD puede medir aCD. 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 leprecede. Y sea CDmidiendo BE dejando EA menor que sí mismo y sea EA midiendo DF dejando FCmenor que sí mismo y sea FC medida de AE. Entonces, como FC mide AE y AE mideDF, 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 aEA. Así mide a todo BA y también mide a CD. Esto es, CF mide tanto a AB y CD por loque 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 alresiduo 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. EntoncesCF 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:
1. Dados dos segmentos AB y CD (con AB>CD), restamos CD de AB tantas veces como sea...