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 el cá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 y tomamos 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 son muy 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 los que 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úmeros enteros 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 igual al 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 iniciales. Vamos a demostrar este hecho para después ilustrar el algoritmo con un ejemplo:
Teorema:
- El máximo común divisor de dos números enteros positivos
y
, con
, coincide con el máximo común divisor de
y
, siendo
el resto que se obtiene al dividir
entre
.
Demostración:
Sean y
. Vamos a demostrar que
.
Por definición de máximo común divisor, se tiene que es un divisor tanto de
como de
. Por tanto
y
.
Por otro lado, por el algoritmo de la división se tiene que
, con
Por tanto es un divisor de
. Como ya teníamos que también es un divisor de
entonces debe dividir a su máximo común divisor, esto es,
es un divisor de
.
Por otro lado, es un divisor tanto de
como de
. Por ello se tiene que
y
. Sustituyendo estas dos igualdades en (1) obtenemos lo siguiente:
Por tanto es un divisor de
. Como también lo era de
debe ser un divisor de su máximo común divisor, es decir,
es un divisor de
.
Como es un divisor de
y
es un divisor de
no queda otra opción más que
. Por tanto el algoritmo de Euclides funciona.
Ejemplos de aplicación del algoritmo
En esta sección del artículo vamos a ver un par de ejemplos de aplicación del algoritmo de Euclides. Vamos con ellos:
Cálculo de
Como hemos explicado antes dividimos el número mayor entre el menor; si el resto no es cero dividimos el divisor entre el resto; y así sucesivamente hasta que llegamos a un punto en el que el resto es cero. Los resultado de las divisiones (expresados como dividendo=divisor · cociente + resto) son:
*
Como marca el *, se tiene que , el último divisor que no es nulo.
Cálculo de
Vamos con el segundo ejemplo, con números más grandes en este caso. Expresamos los resultados parciales de la misma forma que en el ejemplo anterior:
*
Vemos que aunque los números son bastante mayores que los anteriores el número de operaciones necesarias para el cálculo es el mismo. Concluyendo, tenemos que, como marca el *, .
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Como siempre, genial. ¡Ahora a por el algoritmo equivalente en un anillo de polinomios! 😀
Otro algoritmo sencillo (al menos en términos de programación) para hallar el m.c.d. es mediante restas sucesivas.
Añado que el coste del algoritmo es O(log(n)), lo que, computacionalmente hablando, es excelente. Si no recuerdo mal, salvo pequeñas modificaciones, se sigue utilizando como EL algoritmo para encontrar mcd.
Justo lo que dí el otro dia en clase (1º lic. mats), muy bien explicado, gracias!
[…] son los cocientes parciales que obtenemos aplicando el algoritmo de Euclides a una fracción irreducible , con , todos los serán enteros […]
Aquí tenéis una aplicación interactiva hecha con Geogebra que permite visualizar el algoritmo: http://www.matematicainteractiva.com/maximo-comun-divisor-gcd
Hay un error: Para calcular el máximo común divisor entre dos números enteros positivos a y b dividimos el más grande, digamos a, entre el más pequeño, digamos b. Esta división nos proporcionará un cociente, c_1, y un resto, r_1. Si r_1=0, entonces mcd(a,b)=b. Si no es cero dividimos el divisor, c_1, entre el resto, r_1, obteniendo otro cociente, c_2, y otro resto, r_2. Si r_2=0, entonces mcd(a,b)=r_1. Si no es cero volvemos a dividir divisor entre resto. Y así sucesivamente. Esto es, el máximo común divisor entre a y b es el último resto distinto de cero que obtengamos… Lee más »
Alguien me puede explicar, ¿por que si «d» es divisor de «b» y también de «r» entonces tiene q dividir a » t» (su m.c.d)? Hay un teorema q diga eso?