Question

6.6. Using the extended Euclidean algorithm, compute the greatest common divisor and the parameters s,t of 1. 198 and 243 2. 1819 and 3587 For every problem check if s r0 +t r1 = gcd(r0,r1) is actually fulfilled. The rules are the same as above: use a pocket calculator and show what happens in every iteration step.

Answer 1

1) The gcd is 9

9 = 9*243-11*198

2) The gcd is 17

17 = -36*3587+71*1819

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