Question

Express gcd of the following integers A and B has a x + b y where x and y are integers also find X and Y gcd 2210 and 357.



hello all​

Answer 1

Answer:

To do this, the easiest way is to use Euclid’s algorithm to find the GCD. We start with the pair of numbers, 57970 and 10353 and produce a new pair of numbers by (1)replacing the larger number by its remainder when divided by the smaller and (2)retaining the smaller number. In other words, if (x, y) denotes the pair and x > y, then the new pair is (x mod y, y).

So, we get:

57970 = 5*10353 + 6205, so new pair is (10353, 6205)

10353 = 1*6205 + 4148; so new pair is (6205, 4148)

6205 = 1*4148 + 2057, so new pair is (4148, 2057)

4148 = 2*2057 + 34, so new pair is (2057, 34)

2057 = 60*34 + 17, so new pair is (34, 17)

Since 34 = 2*17, the GCD is 17. As you can check, both 57970 and 10353 are multiples of 17.

You can now “unravel” the algorithm:

From the last step, we get 17 = 2057 - 60*34 = 2057 - 60*(4148 - 2*2057) = 121*2057 - 60*4148 = 121*(6205–4148) - 60*4148 = 121*6205–181*4148 = 121*6205 - 181*(10353–6205) =302*6205 - 181*10353 = 302*(57970 - 5*10353) -181*10353 = 302*57970 - 1691*10353.

You can check this last result, which is an expression for the gcd, 17, as a linear combination of the two numbers you started with.

BTW, it is best to do the calculation using a spreadsheet!!!