MATEMÁTICA: Experiencias con Scratch #1

Algoritmo de Euclídes para determinar el máximo común divisor entre dos números.

Supongamos que queremos calcular m.c.d.(5293, 4757). Lo primero que se nos ocurre, es intentar dividir estos números por 2, 3, 5, 7, 11, 13 (quizás por algún número más) y al no obtener ninguna división exacta llegues a la conclusión errónea de que los números son co-primos y por tanto que su máximo común divisor es 1. Pero si sigues dividiendo por 17, 19, 23,... después de un buen rato comprobarás que 67 es divisor tanto de 5293 como de 4757.

Hay un método sencillo llamado algoritmo de Euclides o de las divisiones sucesivas que nos lleva rápidamente al máximo común divisor.
Este método se basa en dos teoremas:
1º)   Si dos números son divisibles el uno por el otro, el menor es su máximo común divisor.
2º)   Si dos números a y b (a>b) no son divisibles el uno por el otro, los divisores comunes de a y b son los mismos que los de b y r, siendo r el resto de la división entera de a entre b.

Para hallar el m.c.d.(5293, 4757):

Dividiremos el mayor número entre el menor. Si el resto es 0, el m.c.d. es el menor.
Si el resto no es 0, se divide el menor por dicho resto, a continuación este resto por el segundo, y así sucesivamente hasta llegar a una división exacta. El último divisor empleado es el máximo común divisor.