‒ Algoritmo para hallar el m.c.d. por residuos.
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)
560=432x1+128
--->
Se divide el mayor con el menor.
432=128x3+48
--->
Se divide el menor con el primer residuo 128.
128=48x2+32
--->
Se divide el primer residuo con el segundo residuo 48.
48=32x1+16
--->
Se divide el segundo residuo con el tercer residuo 32.
32=16x2+0
--->
Se divide el tercer residuo con el cuarto residuo 16.
Se obtiene una división exacta, entonces 16 es el m.c.d.
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).
504=336x1+168
--->
Se divide el mayor con el menor.
336=168x2+0
--->
Se divide el menor con el primer residuo 128.
Se obtiene una división exacta, entonces 168 es el m.c.d.
mcd(504,336)=168
Se halla el m.c.d. del primer m.c.d. 168, con el siguiente número 560, mcd(560,168)
560=168x3+56
--->
Se divide el mayor con el menor.
168=56x3+0
--->
Se divide el menor con el primer residuo 56.
Se obtiene una división exacta, entonces 56 es el m.c.d.
mcd(560,168)=56
Se halla el m.c.d. del segundo m.c.d. 16, con el siguiente número 1834, mcd(1834,56).
1834=56x32+42
--->
Se divide el mayor con el menor.
56=42x1+14
--->
Se divide el menor con el primer residuo 42.
42=14x3+0
--->
Se divide el primer residuo con el segundo residuo 14.
Se obtiene una división exacta, entonces 14 es el m.c.d.
mcd(560,168)=14
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.