Ask Question
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)
  1. 10 January, 19:59
    0
    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
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Mathematics if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers