Почему алгоритм Евклида находит НОД и как его реализовать?

Наибольший общий делитель двух целых чисел сохраняется, если большее число заменить остатком от деления на меньшее. Это свойство превращает медленный перебор делителей в короткую последовательность делений. Алгоритм Евклида важен не только как приём, но и как образец доказуемого уменьшения задачи.

Ключевое равенство

Пусть a = bq + r. Любой общий делитель a и b делит разность a − bq, то есть r. Обратно, общий делитель b и r делит bq + r, значит, делит a. Следовательно, множества общих делителей пар (a, b) и (b, r) совпадают.

Итерационный процесс

Пока b не равно нулю, вычисляют r = a mod b и заменяют пару на (b, r). Остаток по модулю положительного b лежит от нуля до b − 1, поэтому второй компонент строго уменьшается. При b = 0 ответом становится модуль a.

Нули и отрицательные числа

Принято считать gcd(a, 0) = |a|. Знаки исходных чисел не влияют на положительный НОД, поэтому в начале можно перейти к модулям. Случай gcd(0, 0) зависит от принятого определения и должен быть явно оговорён в контракте задачи.

Расширенный вариант

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

Трассировка

Для пары 252 и 105 выпишите столбцы a, b, q и r до нулевого остатка. Затем проверьте последний ненулевой остаток прямым делением обоих исходных чисел. В устном ответе обязательно проговорите сохранение множества общих делителей и строгую убываемость остатка.

Остаток сохраняет общий делитель

Равенство gcd(a, b) = gcd(b, a mod b) следует из представления a = qb + r: любой общий делитель a и b делит r, а общий делитель b и r делит a. Значит, множество общих делителей не меняется. Второй аргумент уменьшается, поэтому процесс заканчивается.

def gcd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a: int, b: int) -> int:
    return 0 if a == 0 or b == 0 else abs(a // gcd(a, b) * b)

assert gcd(252, 105) == 21
assert lcm(12, 18) == 36

В НОК деление выполняется до умножения, чтобы снизить риск переполнения в языках с фиксированной разрядностью. Нормализация знака делает контракт функции однозначным, включая пару отрицательных аргументов.

Практика: коэффициенты Безу

Постройте таблицу итераций для 252 и 105: a, b, частное и остаток. Затем реализуйте расширенный алгоритм Евклида, возвращающий g, x, y, для которых ax + by = g. Проверьте равенство программно для положительных и отрицательных входов. В дополнительной задаче используйте коэффициент x для поиска обратного элемента по модулю m и объясните, почему решение существует только при gcd(a, m) = 1.