L'algorisme d'Euclides

• En aquest cas es té: $a = 252$ i $b = 198$.

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

• Ara es calcula la divisió entera entre $r_0$ i $r_1$. El resultat és $1$, i el residu $45$. Per tant: $$q_1=1, \ r_2=54$$ Per altra banda: $$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$$

Com que $r_2\neq0$, s'ha de continuar. Es fa la divisió entera entre $198$ (és a dir $r_1$) i $54$ (és a dir $r_2$), i s'obté de resultat $q_2=3$ i residu $r_3=36$. Llavors: $$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$$ Com que $r_3\neq0$, es realitza un pas més. Ara la divisió entera entre $54$ (que és $r_2$) i $36$ ($r_3$) i s'obté: $q_3=1$ i el residu és $r_4=18$. Ara: $$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$$ Com que $r_4\neq0$, es torna a repetir el procés. La divisió entera de $r_3=36$ i $r_4=18$ dóna com a resultat $q_4=2$, i el residu és $r_5=0$. Així doncs, ja no s'ha de seguir més!

• Llavors $$mcd(252,198)=r_4=18$$ (perquè és el del penúltim pas). Per altra banda: $$mcd(252,198)=s_4\cdot252+t_4\cdot198=4\cdot252-5\cdot198$$