Algoritmo de euclides

Solo disponible en BuenasTareas
  • Páginas : 6 (1409 palabras )
  • Descarga(s) : 0
  • Publicado : 30 de enero de 2011
Leer documento completo
Vista previa del texto
Algoritmo original de Euclides

AB y CD son 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 elcual 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 no es un número racional, 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 desus 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 unaunidad 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énse 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 yCD 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íademostrar.
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 posible. Si no hay residuo, entonces CD es la máxima medida común.
2. Si se obtiene un residuo EF, éste es menor que CD y podemos repetir el proceso: restamos EF tantas veces como sea posible de CD. Si alfinal no queda un residuo, EF es la medida común. En caso contrario obtenemos un nuevo residuo GH menor a EF.
3. 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 Euclidestradicional
Al dividir a entre b (números enteros), se obtiene un cociente q y un residuo r. Es posible demostrar que el máximo común divisor de a y b es el mismo que el de b y r. É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 a y 0 es precisamente a. Para fines prácticos, la notación mcd(a,b) significa máximo común...
tracking img