SOLUCIÓN. Tengamos en cuenta la siguiente propiedad, que es muy evidente: Sean $a$ y $b$ dos números naturales, entonces si $a=b$ se tiene que $\text{m.c.d}(a,b)=a$; y, en caso contrario, si $a {>} b$ o bien $b {>}a$, deberá cumplirse que $$\text{m.c.d}(a,b)=\text{m.c.d.}\left(\text{máximo}(\{a,b\}),\text{máximo}(\{a,b\})-\text{mínimo}(\{a,b\}\right)$$ Iterando este operación [ intercambiando los términos de la resta si el minuendo fuese menor que el sustraendo ], hasta el paso en que el resultado de dicha resta sea cero, deberemos concluir entonces que el máximo común divisor de $a$ y $b$ ha de ser igual a los valores iguales de los términos de esta última resta.
La siguiente tabla ilustra el procedimiento cuando lo implementamos manualmente, organizando los cálculos en una tabla
OBSERVACIÓN. Si bien este método es menos eficaz que el de Euclides ( véase [éste otro artículo] en el que se utiliza dicho método para otro par de números ) -- ambos métodos se atribuyen a Euclides --, es muy fácil programarlo en un ordenador. En primero y segundo de ESO, recomiendo emplear el lenguaje Logo, si se dispone de un intérprete de dicho lenguaje de programación. Es preferible este método al m. basado en la descomposición en factores primos, en el caso de que los números dados no sean pequeños y sus descomposiciones en factores sean demasiado laboriosas. Y es tanto más eficaz cuanto menor sea la diferencia entre los dos números dados
El algoritmo se puede escribir en un lenguaje de programación, por ejemplo en Logo ( muy apropiado para los primeros cursos de ESO ), para poder implementarlo en un ordenador en el que tengamos instalado un intérprete de Logo:
procediment mcd_restes_successives :a :b
si :a=:b
[escriu.seguit [mcd=] escriu :a acaba]
[
si :a<:b
[posa.a "b :a]
[posa.a "a (:a - :b) mcd_restes_successives :a :b]
]
fi
Para poner en marcha el programa en el intérprete de Logo escribimos (en la línea de comandos):
dando como respuesta
$\square$
