0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Where do matrices occur in this algorithm ? $\endgroup$ – Peter Dec 25 '17 at 14:27
  • 1
    $\begingroup$ @Peter Sorry, I meant row operations, edited the title $\endgroup$ – gbox Dec 25 '17 at 14:31
  • 1
    $\begingroup$ For computing gcd with $-a$ use $gcd(-a,b)=-gcd(a,b)$, or define a gcd to be the absolute value of this. $\endgroup$ – Dietrich Burde Dec 25 '17 at 14:54
  • $\begingroup$ @DietrichBurde And what about the linear combination $gcd(a,b)=xa+yb$? I can not just take $-x,y$ $\endgroup$ – gbox Dec 25 '17 at 15:13
  • 1
    $\begingroup$ One can take $-x$ instead of $x$ in $d=xa+yb$ for $-a$, so that $xa=(-x)(-a)$ is the same. And if we have $-b$ instead of $b$, then take $-y$ instead of $y$. $\endgroup$ – Dietrich Burde Dec 25 '17 at 15:16
1
$\begingroup$

$$ \gcd( 211, 88 ) = ??? $$

$$ \frac{ 211 }{ 88 } = 2 + \frac{ 35 }{ 88 } $$ $$ \frac{ 88 }{ 35 } = 2 + \frac{ 18 }{ 35 } $$ $$ \frac{ 35 }{ 18 } = 1 + \frac{ 17 }{ 18 } $$ $$ \frac{ 18 }{ 17 } = 1 + \frac{ 1 }{ 17 } $$ $$ \frac{ 17 }{ 1 } = 17 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 2 & & 2 & & 1 & & 1 & & 17 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 5 }{ 2 } & & \frac{ 7 }{ 3 } & & \frac{ 12 }{ 5 } & & \frac{ 211 }{ 88 } \end{array} $$ $$ $$ $$ 211 \cdot 5 - 88 \cdot 12 = -1 $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

$$ \gcd( 63300, 26400 ) = ??? $$

$$ \frac{ 63300 }{ 26400 } = 2 + \frac{ 10500 }{ 26400 } $$ $$ \frac{ 26400 }{ 10500 } = 2 + \frac{ 5400 }{ 10500 } $$ $$ \frac{ 10500 }{ 5400 } = 1 + \frac{ 5100 }{ 5400 } $$ $$ \frac{ 5400 }{ 5100 } = 1 + \frac{ 300 }{ 5100 } $$ $$ \frac{ 5100 }{ 300 } = 17 + \frac{ 0 }{ 300 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 2 & & 2 & & 1 & & 1 & & 17 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 5 }{ 2 } & & \frac{ 7 }{ 3 } & & \frac{ 12 }{ 5 } & & \frac{ 211 }{ 88 } \end{array} $$ $$ $$ $$ 211 \cdot 5 - 88 \cdot 12 = -1 $$

$$ \gcd( 63300, 26400 ) = 300 $$
$$ 63300 \cdot 5 - 26400 \cdot 12 = -300 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.