Решение линейных сравнений

Решить сравнение — значит найти все удовлетворяющие ему х. Если х — решение сравнения, то решением является весь класс вычетов, содержащий х. Сравнения с одинаковым множеством решений называются равносильными.

Легко разрешимому линейному уравнению ах= b в кольце Z соответствует линейное сравнение в Z_m, имеющее при а*- 0 вид ах — 6(modm).

Теорема 5.7. Если (а, т) = d, то линейное сравнение имеет решения d; при Ь, кратном d, сравнение имеет d решений.

?4 Если а — 0, 1,…, т — 1, то ах пробегает Z_m при (а, т) = 1, и сравнение имеет одно решение.

Пусть (а, т) = d> 1, тогда сравнение имеет решение, только если d, так как d ах при любом х. Пусть $ = b / d, а — а / d, p-m/d. Перейдем к сравнению ах = p (modp), разделив исходное сравнение на d. Поскольку (а, р) = 1, то новое сравнение имеет одно решение по модулю р. Если наименьший неотрицательный вычет х, по modp есть решение нового сравнения, то наименьшие неотрицательные вычеты х, + /р по модулю т являются решениями исходного сравнения, i = 0, 1,…, d — 1, т.с. исходное сравнение имеет d решений. ?

Один из алгоритмов решения линейных сравнений основан на использовании непрерывных дробей для чисел т / а. Достаточно рассмотреть слу;

Р Р TtX

чай, когда (т, а) = 1. Две последние подходящие дроби есть —и — = —.

Qn-1 Q" а

В соответствии с (5.3) mQ_n_, — аР_п__х = (-1)", тогда аР"_₁ = (-l)" ^_,(modw), отсюда aP"_(-y~^xb = />(modm). Следовательно, линейное сравнение имеет решение х = (-1 )^п~^хЬР_п_у Для определения х достаточно вычислить Р"_.

Пример 5.3.

Решить сравнение 111х = 75mod321. Определим: (111, 321) = 3, где 3175, значит, сравнение имеет три решения. Деля на 3, перейдем к сравнению З7. г з 25modl07 с одним решением. В ходе алгоритма Евклида находим неполные частные 2, 1,8, 4, число шагов п = А.

Отсюда единственное решение второго сравнения есть (-1)³ • 25 • 26 = -650 = = 99modl07.

Решения исходного сравнения суть: х_х = 99(mod321), х₂ = (99 + 107) mod321 = = 206mod 321, х₃ = (99 + 2 • 107) mod 321 = 313mod 321. >

При попарно взаимно простых модулях т_ь т_ъ …, т_г линейная система сравнений.

имеет, но теореме 5.5 единственное решение для х по модулю т_хт₂…т_г