Способи розв’язування конгруенцій 1-го степеня

Розглянемо деякі, найбільш поширені способи розв’язування конгруенцій 1-го степеня:

а) Підстановка в конгруенцію чисел ПСЛ. Цей спосіб використовують при невеликих модулях. При великих модулях підстановку лишків ПСЛ проводять на заключному етапі побудови рівносильних конгруенцій.

б) Зведення конгруенцій 1-го степеня до рівносильної їй конгруенції з коефіцієнтом при х , рівному 1. Цей спосіб полягає в проведенні ряду рівносильних перетворень заданої конгруенції за допомогою операцій, які ґрунтуються на властивостях конгруенцій, розглянутих раніше і не порушують множину розв’язків конгруенції.

в) Спосіб Ейлера. Нехай треба розв’язати конгруенцію , якщо . Помножаючи цю конгруенцію на , дістанемо еквівалентну конгруенцію:

(28)

. (28')

г) Розв’язування конгруенцій 1-го степеня за допомогою неперервних дробів.

Нехай дано конгруенцію

, (29)

де . Розкладемо в ланцюговий дріб. Якщо і є останні підхідні дроби, то на основі теореми 30 (лекція 5) маємо

,

.

Враховуючи, що перший член кратний модулю , дістанемо далі

,

.

, (30)

Зауваження. Перш ніж застосувати цей спосіб, слід спочатку (якщо це необхідно), використовуючи властивості конгруенцій, зробити коефіцієнт при невідомому невід’ємним і меншим за модуль.