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 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 a y b.

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 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 con el procedimiento anterior.

Si analizamos el algoritmo de Euclides se ve claramente que necesitamos demostrar que el máximo común divisor entre a y b es igual al máximo común divisor entre b y r_1. 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 a y b, con a > b > 0, coincide con el máximo común divisor de b y r, siendo r el resto que se obtiene al dividir a entre b.

Demostración:

Sean d=mcd(a,b) y t=mcd(b,r). Vamos a demostrar que d=t.

Por definición de máximo común divisor, se tiene que d es un divisor tanto de a como de b. Por tanto a=a_1d y b=b_1d.

Por otro lado, por el algoritmo de la división se tiene que

a=bq+r, con 0 \le r < b (1)

de donde llegamos a

r=a-bq=a_1d-b_1dq=(a_1-b_1q)d

Por tanto d es un divisor de r. Como ya teníamos que también es un divisor de b entonces debe dividir a su máximo común divisor, esto es, d es un divisor de t.

Por otro lado, t es un divisor tanto de b como de r. Por ello se tiene que b=pt y r=st. Sustituyendo estas dos igualdades en (1) obtenemos lo siguiente:

a=ptq+st=(pq+s)t

Por tanto t es un divisor de a. Como también lo era de b debe ser un divisor de su máximo común divisor, es decir, t es un divisor de d.

Como d es un divisor de t y t es un divisor de d no queda otra opción más que t=d. Por tanto el algoritmo de Euclides funciona. \Box

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 mcd(721,448)

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:

  • 721=448 \cdot 1+273
  • 448=273 \cdot 1+175
  • 273=175 \cdot 1+98
  • 175=98 \cdot 1+77
  • 98=77 \cdot 1+21
  • 77=21 \cdot 3+14
  • 21=14 \cdot 1+7 *
  • 14=7 \cdot 2+0

Como marca el *, se tiene que mcd(721,448)=7, el último divisor que no es nulo.

Cálculo de mcd(25134,19185)

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:

  • 25134=19185 \cdot 1+5949
  • 19185=5949 \cdot 3+1338
  • 5949=1338 \cdot 4+597
  • 1338=597 \cdot 2+144
  • 597=144 \cdot 4+21
  • 144=21 \cdot 6+18
  • 21=18 \cdot 1+3 *
  • 18=3 \cdot 6+0

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 *, mcd(25134,19185)=3.

Share

7 comentarios

  1. Dani | 5 de octubre de 2009 | 09:40

    Vótalo Thumb up 0

    Como siempre, genial. ¡Ahora a por el algoritmo equivalente en un anillo de polinomios! :D

  2. pol | 5 de octubre de 2009 | 10:19

    Vótalo Thumb up 0

    Otro algoritmo sencillo (al menos en términos de programación) para hallar el m.c.d. es mediante restas sucesivas.

  3. Gerard | 5 de octubre de 2009 | 14:01

    Vótalo Thumb up 1

    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.

  4. PePiYo | 5 de octubre de 2009 | 20:55

    Vótalo Thumb up 0

    Justo lo que dí el otro dia en clase (1º lic. mats), muy bien explicado, gracias!

  5. Trackback | 14 dic, 2009

    Fracciones continuas y combinatoria | Gaussianos

  6. Carlos Fleitas | 1 de mayo de 2013 | 15:20

    Vótalo Thumb up 0

    Aquí tenéis una aplicación interactiva hecha con Geogebra que permite visualizar el algoritmo: http://www.matematicainteractiva.com/maximo-comun-divisor-gcd

  7. Manuel Muñoz | 13 de diciembre de 2014 | 22:10

    Vótalo Thumb up 0

    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 con el procedimiento anterior.

    Donde dice dividimos el divisor, c1. Ahí en vez de c1 debería decir b.

Escribe un comentario

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.