обозначим d = gcd(a, b)
хотим x, y: a*x + b*y = d

Евклид (a, b) -> (b, a % b)
если b = 0, то можно вернуть x = 1, y = 0 (1*a + 0*0 = a)
иначе рекурсивно нашлось x'*b + y'*(a % b) = d
x'*b + y'(a - (a/b)*b) = d
x'*b + y'*a - y'*(a/b)*b = d
y'*a + (x' - y'*(a/b))*b = d
то есть пересчитываем x = y', y = x' - y'*(a/b)

пересчет вперед, без рекурсии
обозначим за s, t изначальные числа, от которых ищем gcd, x, y
на очередном шаге есть a, b, x1, y1, x2, y2
при этом поддерживаем a = x1*s + y1*t, b = x2*s + y2*t
как поддерживаем?
сначала x1 = 1, y1 = 0, x2 = 0, y2 = 1, ибо s = 1*s + 0*t, t = 0*s + 1*t
при переходе от (a, b) к (b, a%b) имеем
b = x2*s + y2*t, как и раньше
a % b = a - (a/b)b = x1*s + y1*t - (a/b)*(x2*s + y2*t) = (x1 - (a/b)*x2)*s + (y1 - (a/b)*y2)*t
в конце стало (a, 0), при этом a = x1*s + y1*t, ответ -- a, x1, y1

а теперь пусть есть уравнение ax + by = c, где a, b, c даны, ищем целые x, y
находим Евклидом ax' + by' = d (d = gcd(a, b))
a(c/d)x' + b(c/d)y' = c
если с не делится на d, то ответ не существует -- при любых x, y имеем, что ax + by делится на d
иначе ответ (c/d)x', (c/d)y', где x' и y' из Евклида