El algoritmo consiste en descomponer los números en sus factores primos, una vez obtenido factores primos de cada número, se multiplican los factores primos con bases comunes y de menor exponente.
Ejemplo 1.
Hallar el mcd(2100, 1260, 750, 5600)
Descomponemos los números en sus factores primos:
Los factores primos con bases comunes y de menor exponente son : 2x52, por consiguiente el m.c.d de 2100, 1260, 750 y 5600 es 2x52=50, mcd(2100, 1260, 750, 5600)=50
El algoritmo anterior, se puede abreviar haciendo una descomposición en factores primos comunes de todos los números. Para ello se descompone a la vez los factores primos comunes de todos los números hasta que ya no tengan más factores primos comunes. Los factores primos comunes que se obtienen se multiplican para obtener el m.c.d.
Ejemplo 2.
Hallar el mcd(2100, 1260, 750, 5600)
El primer factor primo común es el 2.
El 3 sería factor primo común porque no divide a 2800, se pasa al siguiente factor primo que es el 5.
El 5 sería el último factor primo común, el 42, 126, 15 y 112, ya no tienen más factores primos comunes.
Los factores primos comunes son 2x52, por consiguiente: mcd(2100, 6300, 750, 5600)=50.