Algoritmo de Euclides

Para determinar del m.c.d. de dos números, se puede utilizar un método llamado algoritmo de Euclides: (Aquí no se demostrará la validez de este algoritmo, se admite que funciona)

He aquí el principio: "dados dos enteros positivos $ a$ y $ b$ , se comienza por probar si $ b$ es nulo. En caso afirmativo, entonces el m.c.d. es igual a $ a$ . Si no, se calcula $ r$ , el resto de la division de $ a$ por $ b$ . Se sustituye $ a$ por $ b$ , y $ b$ por $ r$ , y se reinicia el método.

Calculemos por ejemplo, el m.c.d. de 2160 y 888 por este algoritmo con las siguientes etapas:

$ a$ $ b$ $ r$
2160 888 384
888 384 120
384 120 24
120 24 0
24 0  

El m.c.d. de 2160 y 888 es, por tanto, 24. 24 es el mayor entero que divide simultáneamente a los dos números. De hecho, $ 2160=24\times90$ y $ 888=24\times37$ . El m.c.d. es, por tanto, el último resto no nulo.

Loïc 2007-10-30