El algoritmo de Euclides es un m\u00e9todo antiguo y eficiente para calcular el m\u00e1ximo com\u00fan divisor (mcd). Se basa en el siguiente resultado:\n<\/p>\n
\nTeorema<\/strong>:
\n Si $a$ y $b$ son n\u00fameros enteros, $$mcd(a,b)=mcd(b,r),$$ donde $r$ es el resto del algoritmo de la divisi\u00f3n para $a$ y $b$ ($a=qb+r$).\n<\/p>\n<\/blockquote>\nUtilizando este resultado calculamos el mcd(a,b)<\/b> de dos enteros (ambos ><\/u>0, suponemos a ><\/u> b) definiendo qi<\/sub> y ri<\/sub> recursivamente mediante las ecuaciones:<\/p>\n
<\/p>\n
a = bq1<\/sub> + r1<\/sub> (0<<\/u>r1<\/sub><b)<\/p>\n
\n b = r1<\/sub>q2<\/sub> + r2<\/sub> (0<<\/u>r2<\/sub><r1<\/sub>)<\/p>\n
\n r1<\/sub> = r2<\/sub>q3<\/sub> + r3<\/sub> (0<<\/u>r3<\/sub><r2<\/sub>)<\/p>\n
\n …. <\/p>\n
\n rk-3<\/sub> = rk-2<\/sub>qk-1<\/sub> + rk-1<\/sub> (0<<\/u>rk-1<\/sub><rk-2<\/sub>)<\/p>\n
\n rk-2<\/sub> = rk-1<\/sub>qk<\/sub> (rk<\/sub>=0)<\/p>\n
\n <\/cite><\/p><\/blockquote>\n
Del teorema anterior, se sigue que:<\/p>\n
\n$$mcd(a,b)=mcd(b,r_1)=mcd(r_1,r_2)=\\ldots=mcd(r_{k-2},r_{k-1})=r_{k-1}$$<\/p>\n
Una curiosidad es que el n\u00famero de pasos necesarios para calcular el mcd <\/strong> de dos n\u00fameros es menor que 5 veces el n\u00famero de d\u00edgitos del menor de ellos.<\/p>\n
Este algoritmo lo vamos a utilizar precisamente en uno de los resultados m\u00e1s importantes, el que conocemos como teorema de Bezout<\/a>:<\/p>\n
\nTeorema<\/strong>:
\n Si $a$ y $b$ son n\u00fameros enteros, entonces existen enteros $x$ e $y$ tales que $$ax + by =mcd(a,b)$$\n<\/p>\n<\/blockquote\n\n\n<\/p>\n