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

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

пререквизиты Алгоритм Евклида

Просто для нахождения $\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}$.