Расширенный алгоритм Евклида: как найти x, y в ax + by = gcd(a, b) и доказать корректность?
Обычный Евклид для НОД понятен. Но в расширенном надо ещё восстановить коэффициенты x, y такие, что a·x + b·y = gcd(a, b). Никак не уложу в голове, откуда берутся формулы пересчёта x и y при возврате из рекурсии. Можно вывод?
2 ответа
Вывод идёт прямо из шага Евклида. Пусть рекурсивный вызов для пары (b, a mod b) вернул коэффициенты x1, y1:
b·x1 + (a mod b)·y1 = g
Заметим, что a mod b = a - (a/b)·b (целочисленное деление). Подставим:
b·x1 + (a - (a/b)·b)·y1 = g
a·y1 + b·(x1 - (a/b)·y1) = g
Сравнивая с a·x + b·y = g, получаем формулы пересчёта:
x = y1
y = x1 - (a/b)·y1
База рекурсии: gcd(a, 0) = a, при этом a·1 + 0·0 = a, то есть x = 1, y = 0.
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) { x = 1; y = 0; return a; }
long long x1, y1;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
Сложность та же, что у Евклида — O(log min(a, b)). Корректность по индукции: если внутренний вызов вернул верные x1, y1, то наши формулы дают верные x, y для исходной пары. База очевидна.
Грабля: x и y могут быть отрицательными и довольно большими по модулю. Если используешь их как обратный элемент или решение сравнения, нормализуй в нужный диапазон: x = (x % m + m) % m. И помни, что решение не единственно — общее решение ax + by = g это (x + k·b/g, y - k·a/g) для любого целого k. Это пригодится в диофантовых уравнениях, когда нужно неотрицательное или минимальное решение.