Question

11. Use Euclid’s extended algorithm to find x and y for Gcd(241, 191) = 241 x + 191 y

Show all work.

Answer 1

Use Euclid’s extended algorithm to find x and y for Gcd(241, 191) = 241 x + 191 y

Show all work.

First find the GCD(241,191)

   using Euclidean Algorithm

   241 = 1 * 191 + 50
  
   191 = 3 * 50 + 41

   50 = 1 * 41 + 9

   41 = 4 * 9 + 5

   9 = 1* 5 + 4

   5 = 1 * 4 + 1

   4 =4 * 1 + 0

   Therefore GCD(241,191) =1

By reversing the steps in the Euclidean Algorithm, it is possible to find these integers x and y

Starting with the next to last line, we have:

1 = 5 - 1(4) ---> main equation

From the line before that, we see that 4 = 9 - 1(5)

substituting the value of 4 in main equation

we get the main equation as,

1 = 5 - 1( 9 - 1(5))

1 = 2(5) - 9 ---> main equation

from reverse steps, we get the 5 as

5 = 41 - 4(9)

substituting the value of 5 in main equation we get

1 = 2(41 - 4(9)) - 9

1 = 2(41) - 9(9)

continuing the above process for the remaining steps

9 = 50 - 1(41)

1 = 2(41) - 9(50 - 1(41))

1 = 11(41) - 9(50)

41 = 191 - 3(50)

1 = 11(191 - 3(50)) - 9(50)

1 = 11(191) -42(50)

50 = 241 - 1(191)

1= 11(191) - 42( 241 - 1(191))

1=53(191) - 42(241)

Therefore x = -42
                 y = 53

`