Algoritmo de Euclides

En matemáticas, el algoritmo de Euclides, o algoritmo euclidiano, es un método eficiente para calcular el máximo común divisor (MCD) de dos números enteros, el número más grande que los divide a ambos sin dejar resto.Lleva el nombre del antiguo matemático griego Euclides, quien lo describió por primera vez en Elementos (ca.La versión del algoritmo euclidiano descrita anteriormente (y por Euclides) puede requerir muchos pasos de resta para encontrar el MCD cuando uno de los números dados es mucho más grande que el otro.Se desarrollaron métodos adicionales para mejorar la eficiencia del algoritmo en el siglo XX.El algoritmo euclidiano se puede usar para resolver ecuaciones diofánticas, como encontrar números que satisfagan múltiples congruencias de acuerdo con el teorema chino del resto, para construir fracciones continuas y para encontrar aproximaciones racionales precisas a números reales.En la concepción griega de la matemática, los números se entendían como magnitudes geométricas.Euclides describe en la proposición I.2 en su Libro VII 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.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.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.En lenguaje moderno, el algoritmo se describe como sigue: El hecho de que los segmentos son conmesurables es clave para asegurar que el proceso termina tarde o temprano Al dividirTambién es importante tener en cuenta que el máximo común divisor de cualquier númeroEste 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 naturalesAplicando estas reglas se obtiene la siguiente secuencia de operaciones: Como la sucesión de residuos va disminuyendo, al final un residuo tiene que ser cero y es en ese momento cuando el algoritmo termina.Se puede expresar este algoritmo de manera más formal usando pseudocódigo.pertenecientes a un dominio euclídeo Salida: Un máximo común divisor deSupóngase que se utiliza el algoritmo de Euclides tradicional para calcular los valoresEsta propiedad no debería ser sorprendente, pues esta multiplicación de matrices equivale al método antes descrito donde se substituye cada ecuación en la anterior.Utilizando el primer renglón de esta matriz se puede leer quePara expresar el algoritmo de Euclides extendido es conveniente notar la manera en que se calculan los valoresPor lo tanto el algoritmo en pseudocódigo se puede expresar como sigue: Entrada: Valorespertenecientes a un dominio euclídeo Salida: Un máximo común divisor de(aunque también se puede generalizar para cualquier otro dominio euclídeo) si al dividirlos entrePor ejemplo, 7 es congruente con 12 módulo 5 porque al dividir 7 entre 5 y 12 entre 5, en ambos casos obtenemos el mismo residuo (que es 2).Más aún, si al usar el algoritmo de Euclides extendido (ahora conPor ejemplo, si se desea calcular el máximo común divisor deEn términos de complejidad computacional, esto significa que se requierenEl número promedio de divisiones efectuadas por el algoritmo se estuvo investigando desde 1968, pero solo hasta apenas el año 2002, Brigitte Vallée demostró que si los dos números se pueden representar conEn general, los algoritmos 1 y 2 no son muy apropiados para implementarse directamente en un lenguaje de programación, especialmente porque consumen mucha memoria.