Algoritmo de Euclides

https://commons.wikimedia.org/wiki/File:Euclides_2.jpg

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:

  1. 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.

  1. Si , entonces r = ba·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)

  1. 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 expuesto:

144: 60 144 = 60 · 2 + 24

Dividiendo el divisor empleado (60) por el resto obtenido (24):

60 : 24 60 = 24 · 2 + 12

Dividiendo nuevamente el divisor empleado (24) entre el resto obtenido (12):

24 : 12 24 = 12 · 2 + 0

Como se ha llegado a resto nulo, el máximo común divisor buscado es el último divisor empleado (12), luego:

m.c.d. (144, 60) = 12

Una propiedad interesante de los números naturales es la que relaciona el máximo común divisor de dos números con su mínimo común múltiplo (m.c.m.). Esta propiedad afirma que el producto de los dos valores anteriores es igual al producto de ambos números. Es decir, que:

[m.c.m. (a,b)] · [m.c.d. (a,b)] = a · b

Puede comprobare la propiedad con los números 144 y 60. Como:

144 = 24 · 32 y 60 = 22 · 3 · 5

resulta que:

m.c.m. (144, 60) = 24 . 32 . 5 m.c.m. (144, 60) = 720

m.c.d. (144, 60) = 12

cumpliéndose que:

720 · 12 = 144 · 60 8.640 = 8.640