Euclidean algorithm for greatest integers x and y for common divisor (GCD) 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?
 A: $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$
A: 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}
A: $$ \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
