Calculate the highest common factor between $$252$$ and $$198$$ by the Euclides algorithm, and write it as the sum $$hcf (252,198)=s_n\cdot 252+t_n\cdot 198$$.
Development:
-
In this case we have that: $$a = 252$$ and $$b = 198$$.
-
We define: $$$r_0=252, \ r_1=198$$$ $$$s_0=1, \ s_1=0$$$ $$$t_0=0, \ t_1=1$$$
- Now the integer division is calculated between $$r_0$$ and $$r_1$$.The result is $$1$$, and the remainder $$45$$. Therefore: $$$q_1=1, \ r_2=54$$$ On the other hand: $$$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$$$
As $$r_2\neq0$$, it is necessary to continue. We do the integer division between $$198$$ (that is to say $$r_1$$) and $$54$$ (that is to say $$r_2$$), and we get $$q_2=3$$ and remainder $$r_3=36$$. Then: $$$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$$$ As $$r_3\neq0$$, we do one more step. Now the integer division between $$54$$ (that is $$r_2$$) and $$36$$ ($$r_3$$) and the result is: $$q_3=1$$ and the remainder is $$r_4=18$$. Now: $$$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$$$ As $$r_4\neq0$$, we repeat the procedure. The integer division of $$r_3=36$$ and $$r_4=18$$ gives as a result $$q_4=2$$, and the remainder is $$r_5=0$$. And so, it is not necessary to continue any more!
- Then we have $$$hcf(252,198)=r_4=18$$$ (because it is the one of the penultimate step). On the other hand: $$$hcf(252,198)=s_4\cdot252+t_4\cdot198=4\cdot252-5\cdot198$$$
Solution:
$$hcf(252,198)=18=4\cdot252-5\cdot198$$