Просто для нахождения $\gcd$ даже не нужно знать, как устроен алгоритм Евклида — он есть в компиляторе.
Расширенный алгоритм Евклида находит, помимо $g = \gcd(a, b)$, такие целые коэффициенты $x$ и $y$, что
$$ a \cdot x + b \cdot y = g $$Заметим, что решений бесконечно много: имея решение $(x, y)$, можно $x$ увеличить на $b$, а $y$ уменьшить на $a$, и равенство при этом не изменится.
#Основная идея
Алгоритм тоже будет рекурсивный. Пусть мы посчитали нужные коэффициенты $x’$ и $y’$, когда рекурсивно считали $\gcd(b, a \bmod b)$. Иными словами, у нас есть решение $(x’, y’)$ для пары $(b, a \bmod b)$:
$$ b \cdot x' + (a \bmod b) \cdot y' = g $$ Чтобы получить решение для исходной пары, запишем выражение $(a \bmod b)$ по определению как $(a - \lfloor \frac{a}{b} \rfloor \cdot b)$ и подставим в приведенное выше равенство: $$ b \cdot x' + (a - \Big \lfloor \frac{a}{b} \Big \rfloor \cdot b) \cdot y' = g $$ Теперь выполним перегруппировку слагаемых (сгруппируем по исходным $a$ и $b$) и получим: $$ a \cdot \underbrace{y'}_x + b \cdot \underbrace{(x' - \Big \lfloor \frac{a}{b} \Big \rfloor \cdot y')}_y = g $$Сравнивая это с исходным выражением, получаем, что для исходных $x$ и $y$ подходят коэффициенты при $a$ и $b$.
#Реализация
int gcd(int a, int b, int &x, int &y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
int x1, y1;
int d = gcd(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
Эта рекурсивная функция по прежнему возвращает значение $\gcd(a, b)$, но помимо этого записывает в переданные по ссылке переменные $x$ и $y$ искомые коэффициенты.
#Применения
Эта модификация алгоритма интересна, потому что с помощью неё можно искать обратный элемент по модулю: такой элемент $a^{-1}$, что $a \cdot a^{1} \equiv 1$ — что то же самое, что найти решение в целых числах:
$$ a^{-1} \cdot a + k \cdot m = 1 $$ Также с помощью расширенного алгоритма Евклида можно решать линейные диофантовы уравнения — находить решения $$ a \cdot x + b \cdot y = c $$ в целых числах. Для этого достаточно проверить, что $c$ делится на $g = \gcd(a, b)$, и если это так, то $x$ и $y$ из алгоритма нужно просто домножить на $\frac{c}{g}$.