Расширенный алгоритм Евклида

От алгоритма Евклида можно получить больше, чем просто нахождение НОД. Расширенный алгоритм Евклида позволяет найти такие два числа $x, \ y$, что $ax + by = (a, b)$.

Почему такое представление НОДа в виде линейной комбинации $a$ и $b$ возможно? Это будет следовать непосредственно из приведенного ниже алгоритма.

Для ясности будем работать с рекурсивной реализацией алгоритма Евклида. Пусть функция gcd(a, b) возвращает три числа - найденный НОД и два коэффициента $x, \ y$. Если $b = 0$, то линейная комбинация определяется легко: $$(a, b) = (a, 0) = a = 1\cdot a + 0 \cdot b$$ из gcd(a,b)