Matemáticas metódicas (todo paso a paso)

Los algoritmos permiten obtener paso a paso resultados de manera consistente y duradera. Un algoritmo básico es el de Euclides que permite obtener el máximo común divisor de dos números a partir de un proceso iterativo. Con ayuda de una tabla se van poniendo las divisiones sucesivas a realizar en la fila del medio, los cocientes en la fila superior y los restos en la inferior y seguimos el hilo de los datos que se obtiene:

Algoritmo de Euclides para el cálculo del máximo común divisor de dos números (D y d, con D>d):
1) Ponemos los datos del dividendo, D, y el divisor, d, en dos celdas consecutivas de la fila central y efectuamos la división, obteniendo un cociente, C, y un resto, r. El cociente se pone encima del divisor d y el resto debajo.
2) Se pasa el resto a la derecha del divisor y ahora se realiza de nuevo la división siendo D=d y d=r.
3) Se sigue repitiendo el paso 2 hasta que el resto de la división sea 0. En ese caso, el penúltimo resto es el máximo común divisor buscado.



mcd(45,12)=3








El algoritmo es correcto gracias a que mcd(D,d)=mcd(d,r). Esto es así porque el máximo común divisor de D y d también es un divisor de r, puesto que: Si mcd(d,d)=m, entonces, D=mD' y d=md'. Por la división euclidea D=dC+r. Sustituyendo D y d, queda: mD'=md'C+r, y despejando r, r=m(D'-d'C), lo cual establece que m también es divisor de r.