Use Euclidean algorithm to obtain the g.c.d. ‘d’ of 3997 and 2947. Also find integers x and y such that d=3997x+2947y.
Answers
Answer:
d = 7
x = -87 and y = 118
Step-by-step explanation:
Euclid's algorithm is repeatedly using the Division algorithm until a remainder of 0 is reached. The previous remainder is the gcd.
3997 = 1 × 2947 + 1050
2947 = 2 × 1050 + 847
1050 = 1 × 847 + 203
847 = 4 × 203 + 35
203 = 5 × 35 + 28
35 = 1 × 28 + 7
28 = 4 × 7 + 0
So d = gcd( 3997, 2947 ) = 7.
Now use the equations above in reverse:
7 = 35 - 1 × 28
= 35 - 1 × ( 203 - 5 × 35 ) = 6 × 35 - 1 × 203
= 6 × ( 847 - 4 × 203 ) - 1 × 203 = 6 × 847 - 25 × 203
= 6 × 847 - 25 × ( 1050 - 1 × 847 ) = 31 × 847 - 25 × 1050
= 31 × ( 2947 - 2 × 1050 ) - 25 × 1050 = 31 × 2947 - 87 × 1050
= 31 × 2947 - 87 × ( 3997 - 1 × 2947 ) = 118 × 2947 - 87 × 3997
So a solution to d = 3997x + 2947y is:
x = -87 and y = 118