Algoritmo de Euclides

Se llama algoritmo de Euclides a un método para hallar rápidamente el máximo común divisor (m.c.d.) de dos números sin necesidad de descomponerlos previamente en factores primos. Dados dos números a y b,cuando se desea halla el m.c.d. (a,b), suponiendo que a < b, el algoritmo se aplica en estos pasos sucesivos:. Se divide b entre a, con lo que se obtendrá un cociente, c, y un resto, r, por lo que:. b = a·c + r. Si r = 0, entonces a divide a b, con lo que m.c.d. (a,b) = a. Si , entonces r = b – a·c, con lo que cualquier número que divida a b y a a, dividirá también a r, ya que sabemos que si un número divide a dos, divide también a su diferencia. Entonces:. m.c.d. (a,b) = m.c.d. (a,r). Continuando este proceso, se llegará a una división en la que r será nulo. El máximo común divisor buscado será entonces el último divisor empleado. Por ejemplo, hallemos el m.c.d. (144, 36). 144 : 36 = 4. Luego:. m.c.d. (144, 36) = 36. Hallemos ahora el m.c.d. (144, 60). Operando según lo...