Este algoritmo consiste en lo siguiente: Dado dos números, se divide el mayor de ellos con el menor. Si la división es exacta entonces el máximo común divisor es el menor. En caso contrario, se divide el segundo número por el primer resto. A continuación, se divide el primer resto por el segundo resto, el segundo resto por el tercero y así sucesivamente hasta obtener un resto 0. En donde el penúltimo resto es el máximo común divisor.

Ejemplo 1.

Hallar el mcd(560,432)

Cómo en la última división se obtiene un residuo igual a 0, entonces el penúltimo residuo 16 es el máximo común divisor de 560 y 432, mcd(560,432)=16.

Cuando se desea hallar el máximo común divisor de más de dos números, se halla primero el máximo común divisor de dos de esos números, una vez obtenido el primer m.c.d., se halla el m.c.d. del siguiente número con el primer m.c.d., después se halla el m.c.d. del siguiente número con el segundo m.c.d., y así sucesivamente hasta terminar con todos los números. El último m.c.d. obtenido es el m.c.d. de todos los números.

Ejemplo 2.

Hallar el mcd(336,504,560,1834)

Se halla el m.c.d. de dos de los primeros números, mcd(504,336).

Se halla el m.c.d. del primer m.c.d. 168, con el siguiente número 560, mcd(560,168)

Se halla el m.c.d. del segundo m.c.d. 16, con el siguiente número 1834, mcd(1834,56).

Al no haber más números, entonces el último m.c.d. 14, es el máximo común divisor de 336, 504, 560 y 1834. Es decir mcd(336,504,560,1834) = 14.