El algoritmo de Euclides es un método antiguo y eficiente para calcular el máximo común divisor (mcd). Se basa en el siguiente resultado:
Teorema:
Si $a$ y $b$ son números enteros, $$mcd(a,b)=mcd(b,r),$$ donde $r$ es el resto del algoritmo de la división para $a$ y $b$ ($a=qb+r$).
Utilizando este resultado calculamos el mcd(a,b) de dos enteros (ambos >0, suponemos a > b) definiendo qi y ri recursivamente mediante las ecuaciones:
a = bq1 + r1 (0<r1<b)
b = r1q2 + r2 (0<r2<r1)
r1 = r2q3 + r3 (0<r3<r2)
….
rk-3 = rk-2qk-1 + rk-1 (0<rk-1<rk-2)
rk-2 = rk-1qk (rk=0)
Del teorema anterior, se sigue que:
$$mcd(a,b)=mcd(b,r_1)=mcd(r_1,r_2)=\ldots=mcd(r_{k-2},r_{k-1})=r_{k-1}$$
Una curiosidad es que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.
Este algoritmo lo vamos a utilizar precisamente en uno de los resultados más importantes, el que conocemos como teorema de Bezout:
Teorema:
Si $a$ y $b$ son números enteros, entonces existen enteros $x$ e $y$ tales que $$ax + by =mcd(a,b)$$
| Ejercicio:Calcular el $mcd(2055,123)$ y encontrar dos números enteros $x$ e $y$ tales que $2055x+123y=mcd(2055,123)$ |