MAD: Algoritmo de Euclides

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)$
This entry was written by admin , posted on martes febrero 27 2018at 10:02 am , filed under Matemática Discreta . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

Deja un comentario

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>