Решение сравнения первой степени с использованием расширенного алгоритма Евклида

Рассмотрим расширенный алгоритм Евклида[6].

Как мы убедились в обычном алгоритме Евклида чтобы найти надо выражать через друг друга остатки , что не удобно.

Данный алгоритм позволяет найти в , .

Необходимо работать с системой равенств:

На первом шаге полагаем:

На очередном шаге проверяем: если , то искомые значения равны . Иначе производим деление с остатком: ,

.

 

Пример

Решим сравнение расширенным алгоритмом Евклида .

 

Решение

 

Шаг 1.

Так как , то производим деление: . Значит, . Далее вычисляем:

 

Шаг 2.

Так как , то производим деление: . Значит, . Далее вычисляем:

 

Шаг 3.

Так как , то производим деление: . Значит, . Далее вычисляем:

 

Шаг 4.

Так как , то производим деление: . Значит, . Далее вычисляем:

 

Шаг 5.

Так как , то найдено разложение: , ,.

: . Верно. По формуле (4.3) находим решение исходного сравнения: .●