Respuesta :
The greatest common divisor is 12. The linear combination of 3984 and 588 is given by 12 = 61×588 - 9×3984.
The extended Euclidean algorithm is an algorithm to compute integers x and y such that: ax+by=gcd(a,b)The extended Euclidean algorithm can be viewed as the reciprocal of modular exponentiation.
By reversing the steps in the Euclidean algorithm, it is possible to find these integers x and y. The whole idea is to start with the GCD and recursively work our way backwards. This can be done by treating the numbers as variables until we end up with an expression that is a linear combination of our initial numbers.
First use Euclid's algorithm to find the GCD:
3984 = 588 ×6 + 456
588 = 456×1 +132
456= 132 ×3 + 60
132 = 60×2 +12
60 = 12×5+0
The last non-zero remainder is 12.
Thus, the greatest common divisor is 12.
Now we use the extended algorithm:
12 = 132 +(-2)×60
= 132 + (-2)×(456 + (-3)×132))
= (-2)×456 + 7×132
= (-2)×456 + 7×(588 +(-1)×456))
= 7×588 + (-9)×(3984 +(-6)×588))
= 61×588 + (-9)×3984
Thus, a = -9 and b = 61.
Thus, the linear combination of 3984 and 588 is given by 12 = 61×588 - 9×3984.
To learn more about greatest common divisor, visit brainly.com/question/2292401
#SPJ4
