# Determine integers u and v from GCD(308,273) using GCD algorithm [duplicate]

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)

=??

• Please search before posing questions. There are hundreds of prior questions on this topic. – Bill Dubuque Apr 4 at 2:24

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

• Trying to find integers u and v, are you saying 7 is both? – Admiral Pyro Apr 4 at 1:21

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.

• repeat substituting identity of (2) or which step;for 35? How did you simplify the statement so as to get individually u and v? – Admiral Pyro Apr 4 at 1:55
• @AdmiralPyro No, susbstitute 35 from (1). You should maybe read up on the euclidean algorithm, this would solve your problem and any other problems where you are asked to give u and v such that x(u)+y(v)=GCD(x,y) en.wikipedia.org/wiki/Euclidean_algorithm – Miguel Angel Andrade Velázquez Apr 4 at 1:57
• Thank you for the link, however I only understood it in terms of "use the 2nd last line from GCD steps as 1st line in euclidean algorithm" and am not clear on rk,rk-1 etc and how to interpret the theory. – Admiral Pyro Apr 4 at 2:01
• @AdmiralPyro When you're trying to obtain the linear combination, you are trying to go "backwards" from the method you used to obtain the GDC. So you start from (3), then subsititute 28 from (2). Then you rearrange and then susbstitute 35 from (1) and so on. So in general you want to go back the way you obtain the GDC to get finally to 308 and 273 – Miguel Angel Andrade Velázquez Apr 4 at 2:23

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

• I'm lost on how bezout results in 8 and 9 for u and v respectively, How does that lead to simplified fraction tableau then result in "44⋅8−39⋅9=1"? – Admiral Pyro Apr 4 at 1:57
• @AdmiralPyro In a continued fraction, take two consecutive fractions, called "convergents." The little cross product is either $1$ or $-1.$ For example, $8 \cdot 8 - 9 \cdot 7 = 1.$ Then $9 \cdot 39 - 44 \cdot 8 = -1$ – Will Jagy Apr 4 at 2:01