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

Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя [5].

Выполним следующие деление с остатком:

Тогда . То есть равен последнему отличному от нуля остатку в алгоритме Евклида.

 

Пример

Найдем .

Решение

Значит, .

Если мы хотим найти линейное разложение НОД’а: , то надо остатки выражать друг через друга:

 

Пример

Решим сравнение .

Решение

.

Найдем линейное разложение НОД’а: :

Значит, . По формуле (4.3): . Проверим, действительно ли так: ●

 

Пример

Решим сравнение .

Решение

. Получаем: . Найдем линейное разложение НОД’а: :

Значит, .

Получается, что .

Исходное_решение: ●