The Euclides algorithm

• 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$$