1) Что такое расширенный алгоритм Евклида
Для двух целых чисел a и b и их НОД, то есть gcd(a, b), выполняется линейное уравнение с двумя переменными:
a·x + b·y = gcd(a, b) (1)
Расширенный алгоритм Евклида это способ найти одну пару целочисленных решений (x, y), которая удовлетворяет (1).
2) Алгоритм расширенного алгоритма Евклида
Перед тем как перейти к сути, вспомним обычный алгоритм Евклида.
Для двух целых a и b следующими шагами получаем:
gcd(a, b) = rₙ (2)
Сама цепочка делений с остатком:
a = b·q₀ + r₀
b = r₀·q₁ + r₁
r₀ = r₁·q₂ + r₂
...
rₙ₋₂ = rₙ₋₁·qₙ + rₙ
rₙ₋₁ = rₙ·qₙ₊₁
Теперь посмотрим на первую строку:
a = b·q₀ + r₀
r₀ = a − b·q₀
То есть r₀ можно выразить как линейную комбинацию a и b.
Подставим это во вторую строку:
b = r₀·q₁ + r₁
b = (a − b·q₀)·q₁ + r₁
b = a·q₁ − b·q₀·q₁ + r₁
r₁ = −a·q₁ + b·(q₀·q₁ + 1)
Получается, r₁ тоже выражается через a и b.
Если повторять эту операцию, то каждый rᵢ (0 ≤ i ≤ n) можно представить как сумму кратных a и b.
Значит, в конце:
rₙ = k·a + l·b
А из (2) получаем:
k·a + b·l = gcd(a, b) (3)
Это та же форма, что и (1). Сравнивая (1) и (3), получаем:
(x, y) = (k, l)
и эти k и l будут одной из пар целочисленных решений.
3) Реализация расширенного алгоритма Евклида
Опираясь на вышеописанное, реализуем расширенный алгоритм Евклида:
# extended_eucledean.py
def extended_eucledean(a, b):
if b == 0:
return (1, 0)
else:
xd, yd = extended_euclid(b, a % b)
return (yd, xd - a // b * yd)
Очень просто, правда?
Ну всё. Пока. 🛌
👉 @PythonPortal