I am trying to find $\gcd (211,88)$ and $\gcd (-26400,63300)$ and the smallest linear combination that gives the Greatest Common Divisor (a.k.a. $\gcd$) .
I have been using the following algorithm
For $gcd(211,88)$ I got:
$$211=1(211)+0(88)\\88=0(211)+1(88)\\35=1(211)-2(88)\\18=-2(211)+5(88)\\17=3(211)-7(88)\\1=-5(211)+12(88)\\ 0=88(211)-211(88)$$
And the operations were:
$R_1-2R_2 , R_2-2R_3,R_3-R_4,R_4-R_5,R_5-17R_6$
What is the $\gcd$ ? the one before $0?$
In the case of $\gcd(-26400,63300)$ or in the case that we have one or two negative numbers, how do we use the algorithm?
No comments:
Post a Comment