# Extended Euclidean Algorithm As Row Operations

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?

• Where do matrices occur in this algorithm ? – Peter Dec 25 '17 at 14:27
• @Peter Sorry, I meant row operations, edited the title – gbox Dec 25 '17 at 14:31
• For computing gcd with $-a$ use $gcd(-a,b)=-gcd(a,b)$, or define a gcd to be the absolute value of this. – Dietrich Burde Dec 25 '17 at 14:54
• @DietrichBurde And what about the linear combination $gcd(a,b)=xa+yb$? I can not just take $-x,y$ – gbox Dec 25 '17 at 15:13
• 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$. – Dietrich Burde Dec 25 '17 at 15:16

$$\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$$