SOLUCIÓN. Dados dos números naturales $a$ y $b$, con $a \ge b$, se cumple la siguiente propiedad $$\text{m.c.d.}(a,b)=\text{m.c.d}(b,r)$$ donde $r$ representa el resto de la división $a \div b$. Iterando esta propiedad, hasta llegar a una división con resto igual a $0$, vemos que el máximo común divisor pedido ha de ser igual al divisor de la última división.
Así, pues, organizando los cálculos en una tabla con los números del ejercicio, se llega a
OBSERVACIÓN. Este método es más eficaz que el m. basado en la descomposición en factores primos de los dos números dados. El siguiente programa escrito en Logo puede implementarse en un ordenador en el que hayamos instalado un intérprete de dicho lenguaje de programación ( muy apropiado para los primeros cursos de ESO ):
Siendo $a \ge b$, el siguiente programa recursivo lleva rápidamente a la solución:
procediment mcd_Euclides :a :b
fes.local "r residu :a :b
si :r=0
[escriu.seguit [mcd=] escriu :b acaba]
[
posa.a "a :b
posa.a "b :r
mcd_Euclides :a :b
]
fi
Este otro programa utiliza el mismo algoritmo, si bien es una versión no recursiva del de arriba
procediment mcd_Euclides_2 :a :b
fes.local "r
fes.local "dividend
fes.local "divisor
si :a > :b
[
posa.a "dividend :a
posa.a "divisor :b
]
[
posa.a "dividend :b
posa.a "divisor :a
]
repeteix :dividend
[
posa.a "r residu :dividend :divisor
si :r=0
[
escriu.seguit [mcd =] escriu :divisor
acaba
]
[
posa.a "dividend :divisor
posa.a "divisor :r
]
]
fi
Una vez preparado con el editor de Logo, lo pondremos en marcha mediante la siguiente petición ( línea de comandos del entorno de programación ):