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

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

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

Для ясности будем работать с рекурсивной реализацией алгоритма Евклида. Пусть функция extgcd(a, b) возвращает три числа - найденный НОД и два коэффициента $x, \ y$, таких что $a \cdot x + b \cdot y = gcd(a, b)$. Если $b = 0$, то линейная комбинация определяется легко: $$(a, b) = (a, 0) = a = 1\cdot a + 0 \cdot b$$ Если же $b \neq 0$, то в обычном алгоритме Евклида мы говорили, что $gcd(a, b) = gcd(b, a \% b)$. Попробуем развить эту идею. То есть на основе рекурсивного вызова функции extgcd(b, a % b) попробуем найти результат функции extgcd(a, b). Вызвавшись рекурсивно функцией extgcd(b, a % b), мы знаем такие $x'$ и $y'$, что $b \cdot x' + (a \% b) \cdot y' = gcd(b, a \% b) = gcd(a, b)$. Пусть $a\,//\,b = n$ ($\,//$ обозначает целую часть деления). Тогда $a = b \cdot n + (a \% b)$. Заметим, что $$b \cdot x' + (a \% b) \cdot y' = b \cdot x' - b \cdot n \cdot y' + b \cdot n \cdot y' + (a \% b) \cdot y' = $$ $$ = b \cdot x' - b \cdot n \cdot y' + a \cdot y' = b \cdot (x' - n \cdot y') + a \cdot y'$$ Тогда если $x=y'$ и $y=x' - n \cdot y'$, то $a \cdot x + b \cdot y = gcd(a, b)$. А значит мы нашли extgcd(a, b).

---

Автор конспекта: Филипп Грибов

По всем вопросам пишите в telegram @grphil