Problems from The Euclides algorithm

Calculate the highest common factor between $252$ and $198$ by the Euclides algorithm, and write it as the sum $h c f (252, 198) = s_{n} \cdot 252 + t_{n} \cdot 198$ .

See development and solution

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 \cdot 1 = 1$ $t_{2} = t_{0} - t_{1} \cdot q_{1} = 0 - 1 \cdot 1 = - 1$

As $r_{2} \neq 0$ , 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 \cdot 3 = - 3$ $t_{3} = t_{1} - t_{2} \cdot q_{2} = 1 - (- 1) \cdot 3 = 4$ As $r_{3} \neq 0$ , 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) \cdot 1 = 4$ $t_{4} = t_{3} - t_{2} \cdot q_{2} = - 1 - 4 \cdot 1 = - 5$ As $r_{4} \neq 0$ , 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 $h c f (252, 198) = r_{4} = 18$ (because it is the one of the penultimate step). On the other hand: $h c f (252, 198) = s_{4} \cdot 252 + t_{4} \cdot 198 = 4 \cdot 252 - 5 \cdot 198$

Solution:

$h c f (252, 198) = 18 = 4 \cdot 252 - 5 \cdot 198$

Hide solution and development