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?

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