Теория
Обычный алгоритм Евклида находит только НОД. Расширенный алгоритм дополнительно подбирает целые коэффициенты \(x\) и \(y\), при которых \(ax + by = \operatorname{НОД}(a, b)\) — такое представление называется соотношением Безу.
Коэффициенты находят «обратным ходом»: цепочку делений алгоритма Евклида разматывают снизу вверх, выражая каждый остаток через исходные числа. На практике это делают таблицей, а не руками. Расширенный алгоритм — рабочая лошадка криптографии: именно он вычисляет обратный элемент по модулю, без которого не работают RSA и другие алгоритмы.
Важно: коэффициенты Безу не единственны — если пара \((x, y)\) подходит, то подойдёт и \((x + kb, y - ka)\) для любого целого \(k\).
Пример с решением
- Условие. Представьте НОД чисел 240 и 46 в виде \(240x + 46y\).
- Формула. Соотношение Безу: \(ax + by = \operatorname{НОД}(a, b)\).
- Подстановка. Алгоритм Евклида: \(240 = 46 \times 5 + 10\), \(46 = 10 \times 4 + 6\), \(10 = 6 \times 1 + 4\), \(6 = 4 \times 1 + 2\), \(4 = 2 \times 2 + 0\). НОД = 2.
- Вычисление. Обратный ход: \(2 = 6 - 4\), \(4 = 10 - 6\), \(6 = 46 - 4 \times 10\), \(10 = 240 - 5 \times 46\); после подстановок получается \(2 = 240 \times (-9) + 46 \times 47\).
- Ответ. \(x = -9\), \(y = 47\): проверка \(240 \times (-9) + 46 \times 47 = -2160 + 2162 = 2\). Калькулятор с полями 240 и 46 выдаст ту же пару коэффициентов.
Главное
- Соотношение Безу: \(ax + by = \operatorname{НОД}(a, b)\) с целыми \(x\), \(y\).
- Коэффициенты получаются обратным ходом алгоритма Евклида.
- Применение — обратный элемент по модулю, основа криптографии.