Answer:
1) The gcd is 9
9 = 9*243-11*198
2) The gcd is 17
17 = -36*3587+71*1819
Step-by-step explanation:
1) First, we divide the greater number with the smallest:
243/198 = 1.227....
The whole value is 1, and the remainder is243-1*198 = 45
Now we take the second number, 198 and 45 and repeat the same process:
198/45 = 4.4
The whole part is 4
the remainder is
198 - 4*45 = 18
Now we take 45 and 18 and repeat the process
45/18 = 2.5
the whole part is 2, the remainder is 45-2*18 = 9
Now,
18/9 = 2 is a whole number, so we stop in 9, which is the gcd.
How we find s,t?
We have to start from 9 and go upwards, replacing in bigger numbers (used in our algorithm) if possible
9 = 45-2*18
Now, we replace 18, using 18 = 198-4*45
9 = 45-2*18 = 45- 2*(198-4*45) = 9*45 - 2*198
Now, time to replace 45, using 45 = 243-198
9 = 9*45-2*198 = 9*(243-198) - 2*198 = 9*243 - 11*198
If we make the computation 9*243-11*198 = 2187-2178 = 9
Thus, the gcd is 9 and the parameters are 9 for 243 and -11 for 198.
2)
Lets divide 3587 with 1819
3587/1819 = 1.971...
The whole part is 1, the remainder is
3587-1*1819 = 1768
Now, its the turn for 1819 and 1768
clearly, the whole part oof the division will be 1, since ther are similar numbers. The remainder is 1819-1768 = 51
Now, lets continue with 1768 and 51
1768/51 = 34.66666
The whole part is 34, the remainder is
1768-34*51 = 34
Now, between 51 and 34:
The whole part of 51/34 is 1 and the remainder is 51-34 = 17
And between 34 and 17:
34/17 = 2, which is a whole number. So we stop in 17.
The gcd is 17, lets find now the parameters. We start by replacing 17
17 = 51 - 1*34
Now 34: 34 = 1768-34*51
51-34 = 51-(1768-34*51) = 35*51-1768
Now, we replace 51 = 1819-1768:
35*51-1768 = 35*(1819-1768) - 1768 = 35*1819-36*1768
And last, we replace 1768 with 3587-1819
35*1819-36*1768 = 35*1819-36*(3587-1819) = 71*1819 - 36*3587
So, the parameters for 3587 and 1819 are -36 and 71 respectively and the gcd is 17.
Lets check:
-36*3587+71*1819 = -129132+129149 = 17
