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[/latex] (1) de donde llegamos a <p align="center">[latex]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.

Print Friendly, PDF & Email
4.5 11 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉