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?

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