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. 300 a. C.). Es un ejemplo de un algoritmo, un procedimiento paso a paso para realizar un cálculo de acuerdo con reglas bien definidas, y es uno de los algoritmos más antiguos que se siguen utilizando. Se puede usar para reducir fracciones a su forma más simple y es parte de muchos otros cálculos teórico-numéricos y criptográficos. El algoritmo euclidiano se basa en el principio de que el máximo común divisor de dos números no cambia si el número más grande se reemplaza por su diferencia con el número más pequeño. Por ejemplo, 21 es el MCD de 252 y 105 (ya que 252 = 21 × 12 y 105 = 21 × 5), y el mismo número 21 también es el MCD de 105 y 252 − 105 = 147. Dado que este reemplazo reduce el más grande de los dos números, al repetir este proceso se obtienen pares de números sucesivamente más pequeños hasta que los dos números se vuelven iguales. Cuando eso ocurre, son el MCD de los dos números originales. Al invertir los pasos o usar el algoritmo de Euclides extendido, el MCD se puede expresar como una combinación lineal de los dos números originales, es decir, la suma de los dos números, cada uno multiplicado por un número entero (por ejemplo, 21 = 5 × 105 + (−2) × 252). El hecho de que el MCD siempre se pueda expresar de esta manera se conoce como la identidad de Bézout. La versión...