http://gaussianos.
com/category/matematicas-discreta/
El algoritmo de Euclides
Introduccin
El lunes pasado, en el post donde se desarrollaba un mtodo para resolver ecuaciones
diofnticas lineales, comentbamos la existencia de un mtodo para el clculo del mximo
comn divisor que no desarrollamos. Dicho mtodo se atribuye a Euclides y este post va a
servir para presentarlo.
El algoritmo de Euclides
El problema inicial es el siguiente:
Encontrar el mximo comn divisor entre dos nmeros enteros positivos
Todos conocemos el mtodo que se nos ensea en el colegio para ello:
Descomponemos en factores primos los dos nmeros y tomamos los factores comunes a
ambos con el menor exponente con el que aparezcan.
Aunque es un mtodo bastante til y sencillo para conseguirlo que queremos tiene un evidente
problema: si los nmeros son muy grandes, o si sus factores primos lo son, la cosa se complica
ya que el clculo de la descomposicin se torna bastante tedioso.
Por ello es interesante tener a mano otro mtodo 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 mximo comn divisor entre dos nmeros enteros positivos
dividimos el ms grande, digamos
proporcionar un cociente,
es cero dividimos el divisor,
resto,
. Si
, entre el ms pequeo, digamos
, y un resto,
. Si
, entre el resto,
, entonces
. Esta divisin nos
, entonces
, obteniendo otro cociente,
. Si no
, y otro
. Si no es cero volvemos a dividir divisor
entre resto. Y as sucesivamente.
Esto es, el mximo comn divisor entre
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
mximo comn divisor entre
es igual al mximo comn divisor entre
. As esa
igualdad se mantendr durante todo el proceso y llegaremos a que el ltimo resto distinto de
cero es el mximo comn divisor de los dos enteros positivos iniciales. Vamos a demostrar este
hecho para despus ilustrar el algoritmo con un ejemplo:
Teorema:
El mximo comn divisor de dos nmeros enteros positivos
y , con
, coincide
con el mximo comn divisor de
y , siendo
el resto que se obtiene al dividir
entre
.
Demostracin:
Sean
. Vamos a demostrar que
Por definicin de mximo comn divisor, se tiene que
Por tanto
es un divisor tanto de
como de
Por otro lado, por el algoritmo de la divisin se tiene que
, con
(1)
de donde llegamos a
Por tanto
es un divisor de
. Como ya tenamos que tambin es un divisor de
debe dividir a su mximo comn divisor, esto es,
es un divisor de
entonces
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 tambin lo era de
su mximo comn divisor, es decir, es un divisor de
Como
que
debe ser un divisor de
.
es un divisor de y es un divisor de
no queda otra opcin ms
. Por tanto el algoritmo de Euclides funciona.
Ejemplos de aplicacin del algoritmo
En esta seccin del artculo vamos a ver un par de ejemplos de aplicacin del
algoritmo de Euclides. Vamos con ellos:
Clculo de
Como hemos explicado antes dividimos el nmero 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 comodividendo=divisor cociente + resto) son:
Como marca el *, se tiene que
nulo.
, el ltimo divisor que no es
Clculo de
Vamos con el segundo ejemplo, con nmeros ms grandes en este caso.
Expresamos los resultados parciales de la misma forma que en el ejemplo
anterior:
Vemos que aunque los nmeros son bastante mayores que los anteriores el
nmero de operaciones necesarias para el clculo es el mismo. Concluyendo,
tenemos que, como marca el *,
.
