Mínimo común múltiplo, máximo común divisor y algoritmo de Euclides

El máximo comón divisor de dos números m y n, mcd(m, n) es el mayor de los divisores comunes a ambos. Tenemos dos procedimientos para hallarlo:

1. Descomponiendo totalmente ambos números en factores primos, y tomando los comunes elevados al menor exponente.

2. Aplicar el Algoritmo de Euclides, que consite en dividir el mayor por el menor, y reiteradamente el último divisor por el resto, hasta que este sea cero. El último divisor es entonces el mcd(m, n).

Cuando la descomposición factorial no es inmediata, el Algoritmo de Euclides es mucho más rápido. Descomponer en factores un número grande puede llevar mucho tiempo.

Introduce los valores de m y n en los cajetines de entrada correspondientes, y pulsa luego reiteradamente el botón [Euclides] para observar los pasos del proceso.
Para un nuevo cálculo, modifica los valores de m y/o n.

Ignacio Larrosa Cañestro (Grupo XeoDin), 26 noviembre 2013. Creado con GeoGebra