De rodo un poco

El algoritmo de Euclides
Introducción
El lunes pasado, en el post donde se desarrollaba un método para resolver ecuaciones diofánticas lineales, comentábamos la existencia de un método para elcálculo del máximo común divisor que no desarrollamos. Dicho método se atribuye a Euclides y este post va a servir para presentarlo.
El algoritmo de Euclides
El problema inicial es el siguiente:Encontrar el máximo común divisor entre dos números enteros positivos y .
Todos conocemos el método que se nos enseña en el colegio para ello:
* Descomponemos en factores primos los dos números ytomamos los factores comunes a ambos con el menor exponente con el que aparezcan.
Aunque es un método bastante útil y sencillo para conseguirlo que queremos tiene un evidente problema: si los números sonmuy grandes, o si sus factores primos lo son, la cosa se complica ya que el cálculo de la descomposición se torna bastante tedioso.
Por ello es interesante tener a mano otro método para casos en losque el procedimiento inicial se complique. El llamado algoritmo de Euclides nos servirá.
El algoritmo de Euclides nos dice lo siguiente:
Para calcular el máximo común divisor entre dos númerosenteros positivos y dividimos el más grande, digamos , entre el más pequeño, digamos . Esta división nos proporcionará un cociente, , y un resto, . Si , entonces . Si no es cero dividimos el divisor, ,entre el resto, , obteniendo otro cociente, , y otro resto, . Si , entonces . Si no es cero volvemos a dividir divisor entre resto. Y así sucesivamente.
Esto es, el máximo común divisor entre y es elúltimo resto distinto de cero que obtengamos con el procedimiento anterior.
Si analizamos el algoritmo de Euclides se ve claramente que necesitamos demostrar que el máximo común divisor entre y es igualal máximo común divisor entre y . Así esa igualdad se mantendrá durante todo el proceso y llegaremos a que el último resto distinto de cero es el máximo común divisor de los dos enteros positivos...