Рассмотрим расширенный алгоритм Евклида[6].
Как мы убедились в обычном алгоритме Евклида чтобы найти надо выражать через друг друга остатки , что не удобно.
Данный алгоритм позволяет найти в , .
Необходимо работать с системой равенств:
На первом шаге полагаем:
На очередном шаге проверяем: если , то искомые значения равны . Иначе производим деление с остатком: ,
.
Пример
Решим сравнение расширенным алгоритмом Евклида .
Решение
Шаг 1.
Так как , то производим деление: . Значит, . Далее вычисляем:
Шаг 2.
Так как , то производим деление: . Значит, . Далее вычисляем:
Шаг 3.
Так как , то производим деление: . Значит, . Далее вычисляем:
Шаг 4.
Так как , то производим деление: . Значит, . Далее вычисляем:
Шаг 5.
Так как , то найдено разложение: , ,.
: . Верно. По формуле (4.3) находим решение исходного сравнения: .●