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

Просто для нахождения $\gcd$ даже не нужно знать, как устроен алгоритм Евклида — он есть в компиляторе.

Расширенный алгоритм Евклида находит, помимо $g = \gcd(a, b)$, такие целые коэффициенты $x$ и $y$, что

Заметим, что решений бесконечно много: имея решение $(x, y)$, можно $x$ увеличить на $b$, а $y$ уменьшить на $a$, и равенство при этом не изменится.

#Основная идея

Алгоритм тоже будет рекурсивный. Пусть мы посчитали нужные коэффициенты $x’$ и $y’$, когда рекурсивно считали $\gcd(b, a \bmod b)$. Иными словами, у нас есть решение $(x’, y’)$ для пары $(b, a \bmod b)$:

Сравнивая это с исходным выражением, получаем, что для исходных $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$ — что то же самое, что найти решение в целых числах: