Algoritmo de euclides

Solo disponible en BuenasTareas
  • Páginas : 3 (632 palabras )
  • Descarga(s) : 0
  • Publicado : 12 de octubre de 2010
Leer documento completo
Vista previa del texto
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 esuna 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 cienciasde la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.
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, éstees menor que CD y podemos repetir el proceso: restamos EF tantas veces como sea posible de CD. Si al final no queda un residuo, EF es la medida común. En caso contrario obtenemos un nuevoresiduo 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 conmensurableses clave para asegurar que el proceso termina tarde o temprano.
-------------------------------------------------
Algoritmo de Euclides tradicional
Al dividir a entre b (números enteros), se obtieneun 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 encuenta 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 divisor de a y b.
Según lo antes mencionado, paracalcular 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 | mcd(2366,273) = mcd(273,182)...
tracking img