Calcula el màxim comú divisor entre 252 i 198 mitjançant l'algorisme d'Euclides, i escriu-lo també com la suma $$mcd(252,198)=s_n\cdot 252+t_n\cdot 198$$.
Desenvolupament:
-
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$$$
Solució:
$$mcd(252,198)=18=4\cdot252-5\cdot198$