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.

Question

Caitlin Park

Mathematics

10 January, 19:55

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.

+2

Answers (1)

Know the Answer?

Duncan · Answer 1

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