Algoritmo de Euclides

Carta Rara · N.º 61215

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…

Leer en Wikipedia