Determine integers u and v from GCD(308,273) using GCD algorithm

Question

I'm having trouble determining u and v using gcd algorithm, stuck on combining reverse of 308 and 273. I'm lost on what to do after laying out d=rk=... Is there a fixed order to what lines to use?

Work:

273u+308v=GCD(308,273)

a=273

b=308

d=7

273=35x7+28

308=273x1+35

35=308+(-273)x1

28=273+(-35)x7

7=35+(-28)x1

7=28x1+7

=28x1+(35+(-28)x1)

=??

Answer 1

Once you have $d=7$ (which is the GCD) you're done, as it divides both 308 and 273. Once you have $d$ you can compute $u$ and $v$.

Answer 2

The way I would obtain the GCD would be through the Euclidean algorithm therefore y would write: $$308=273(1)+35 \tag{1.}$$ $$\Rightarrow 273=35(7)+28 \tag{2.}$$ $$\Rightarrow 35=28(1)+7 \tag{3.}$$

Once you have the GDC, you use the operations you already have to rewrite the GDC. Therefore: $$7=35-28$$ Then susbsitute 28 with the identity of (2) and repeat the process for 35. That should in the end give you u and v.

Answer 3

I like the method of continued fractions to find the Bezout coefficients

$$ \gcd( 308, 273 ) = ??? $$

$$ \frac{ 308 }{ 273 } = 1 + \frac{ 35 }{ 273 } $$ $$ \frac{ 273 }{ 35 } = 7 + \frac{ 28 }{ 35 } $$ $$ \frac{ 35 }{ 28 } = 1 + \frac{ 7 }{ 28 } $$ $$ \frac{ 28 }{ 7 } = 4 + \frac{ 0 }{ 7 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 1 & & 7 & & 1 & & 4 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 8 }{ 7 } & & \frac{ 9 }{ 8 } & & \frac{ 44 }{ 39 } \end{array} $$ $$ $$ $$ 44 \cdot 8 - 39 \cdot 9 = 1 $$

$$ \gcd( 308, 273 ) = 7 $$
$$ 308 \cdot 8 - 273 \cdot 9 = 7 $$