Euclidean algorithm for greatest integers x and y for common divisor (GCD)

Question

I have a problem with finding the gcd of two numbers: gcd(4620, 8190) = 210.

I did the following:

8190 / 4620 = 1 with remainder: 3570

4620 / 3570 = 1 with remainder: 1050

3570 / 1050 = 3 with remainder: 420

1050 / 420 = 2 with remainder: 210

420 / 210 = 2 with remainder: 0

GDC = 210

So far so good, but I need to find x and y as integers that satisfy this condition:

4620x + 8190y

How can I achieve that? I did find that -9 and 16 satisfy this condition, but I don't know how to justify that.

Do I need to substitute the numbers in the steps from the algorithm?

Answer 1

$210=1050+(-2)420=1050+(-2)(3570+(-3)1050)=(-2)3570+(7)1050=(-2)3570+(7)(4620+(-1)3570)=(7)4620+(-9)3570=(7)4620+(-9)(8190+(-1)4620)=(-9)8190+(16)4620$

By substituting these results

$210=1050+(-2)420$

$420=3570+(-3)1050$

$1050=4620+(-1)3570$

$3570=8190+(-1)4620$

Answer 2

$$ \frac{ 8190 }{ 4620 } = 1 + \frac{ 3570 }{ 4620 } $$ $$ \frac{ 4620 }{ 3570 } = 1 + \frac{ 1050 }{ 3570 } $$ $$ \frac{ 3570 }{ 1050 } = 3 + \frac{ 420 }{ 1050 } $$ $$ \frac{ 1050 }{ 420 } = 2 + \frac{ 210 }{ 420 } $$ $$ \frac{ 420 }{ 210 } = 2 + \frac{ 0 }{ 210 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 1 & & 1 & & 3 & & 2 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 7 }{ 4 } & & \frac{ 16 }{ 9 } & & \frac{ 39 }{ 22 } \end{array} $$ $$ $$ $$ 39 \cdot 9 - 22 \cdot 16 = -1 $$

$$ \gcd( 8190, 4620 ) = 210 $$
$$ 8190 \cdot 9 - 4620 \cdot 16 = -210 $$

well, there you go

Answer 3

There are two solutions for that:

• either you go backwards from the last but one division: $$1050=2\cdot 420+210\iff 210=1050-2\cdot 420$$ Similarly $420=3570-3\cdot 1050$, hence $$210=1050-2(3570-3\cdot 1050)=7\cdot 1050-2\cdot 3570$$ &c.
• or you use the extended Euclidean algorithm, which performs the successive divisions and simultaneously calculates the coefficients $x_i$ and $y_i$ for each of the successive remainders:

\begin{array}{rrrl} r_i & x_i&y_i &q_i\\ \hline 8190&0&1 \\ 4620&1&0&1 \\ 3570&-1&1&1 \\1050 &2&-1&3 \\ 420&-7&4&2 \\ 210&\color{red}{16}&\color{red}{-9}&2 \\\hline 0 \end{array}