El algoritmo de Euclides

• En este caso se tiene: $a = 252$ y $b = 198$.

• Se define: $$r_0=252, \ r_1=198$$ $$s_0=1, \ s_1=0$$ $$t_0=0, \ t_1=1$$

• Ahora se calcula la división entera entre $r_0$ y $r_1$. Se tiene que el resultado es $1$, y el residuo $45$. Por lo tanto: $$q_1=1, \ r_2=54$$ Por otro lado: $$s_2=s_0-s_1\cdot q_1=1-0\cdot1=1$$ $$t_2=t_0-t_1\cdot q_1=0-1\cdot1=-1$$

Como $r_2\neq0$, se tiene que continuar. Se hace la división entera entre $198$ (es decir $r_1$) y $54$ (es decir $r_2$), y se obtiene de resultado $q_2=3$ y residuo $r_3=36$. Entonces: $$s_3=s_1-s_2\cdot q_2=0-1\cdot3=-3$$ $$t_3=t_1-t_2\cdot q_2=1-(-1)\cdot3=4$$ Como $r_3\neq0$, se realiza un paso más. Ahora la división entera entre $54$ (que es $r_2$) y $36$ ($r_3$) y se obtiene: $q_3=1$ y el residuo es $r_4=18$. Ahora: $$s_4=s_2-s_3\cdot q_3=1-(-3)\cdot1=4$$ $$t_4=t_3-t_2\cdot q_2=-1-4\cdot1=-5$$ Como $r_4\neq0$, se vuelve a repetir el proceso. La división entera de $r_3=36$ y $r_4=18$ da como resultado $q_4=2$, y el residuo es $r_5=0$. Así pues, ¡ya no se tiene que seguir más!

• Entonces se tiene que $$mcd(252,198)=r_4=18$$ (porque es el del penúltimo paso). Por otro lado: $$mcd(252,198)=s_4\cdot252+t_4\cdot198=4\cdot252-5\cdot198$$