Please provide work Thank you Use the Euclidean algorithm to

Please provide work. Thank you

Use the Euclidean algorithm to find gcd(a, b), and express the gal as a linear combination of a and b. ? a = 12, b = 18 ? 0 = 123, b 277 ? a = 1001, b = 1331

Solution

In Euclidean algorithm, we go on dividing the last divisor by remainder of each division process till we get the remainder zero. And once we got remainder zero, the divisor that makes this remainder zero is called our GCD (a,b)

So in first part : when a = 12 and b = 18, we do it as

12 )18 ( 1

- 12

---------- on subtracting

6 ) 12 ( 2

-12

-------

0

so as remainder is zero, when divisor is 6, so gcd (12,18) = 6 Answer

Again in second part, when a=123 and b =277

123 ) 277 ( 2

-246

------

31 ) 123 ( 3

-93

--------

30 ) 31 ( 1

- 30

-------

1 ) 30 ( 30

-30

--------

0

Now when remainder is zero, divisor is 1, so gcd(123,277) =1 Answer

Again for part 3) : When a = 1001 and b= 1331

1001 ) 1331 ( 1

   -1001

-------

   330 ) 1001 ( 3

   - 990

   -----------

31 ) 330 ( 10

- 310

---------

20 ) 31 ( 1

- 20

--------

11 ) 20 ( 1

- 11

   ---------

   9 )11 ( 1

   -- 9

   -----

   2 ) 9 ( 4

   -8

   -----

   1)2 ( 2

- 2

   ------

   0

so when remainder becomes zero, related divisor is 1, that means gcd (1001,1331 ) = 1 Answer