(modm). Следовательно, линейное сравнение имеет решение х = (-1)п~хЬРп_у Для определения х достаточно вычислить Р"_. Один из алгоритмов решения линейных сравнений основан на использовании непрерывных дробей для чисел т / а. Достаточно рассмотреть слу; Легко разрешимому линейному уравнению ах= b… Читать ещё >
Решить сравнение — значит найти все удовлетворяющие ему х. Если х — решение сравнения, то решением является весь класс вычетов, содержащий х. Сравнения с одинаковым множеством решений называются равносильными.
Легко разрешимому линейному уравнению ах= b в кольце Z соответствует линейное сравнение в Zm, имеющее при а*- 0 вид ах — 6(modm).
Теорема 5.7. Если (а, т) = d, то линейное сравнение имеет решения d; при Ь, кратном d, сравнение имеет d решений.
?4 Если а — 0, 1,…, т — 1, то ах пробегает Zm при (а, т) = 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) mQn_, — аРп_х = (-1)", тогда аР"_1 = (-l)" _,(modw), отсюда aP"_(-y~xb = />(modm). Следовательно, линейное сравнение имеет решение х = (-1 )п~хЬРп_у Для определения х достаточно вычислить Р"_.
Пример 5.3.
Решить сравнение 111х = 75mod321. Определим: (111, 321) = 3, где 3175, значит, сравнение имеет три решения. Деля на 3, перейдем к сравнению З7. г з 25modl07 с одним решением. В ходе алгоритма Евклида находим неполные частные 2, 1,8, 4, число шагов п = А.
S. | |||||
<h | |||||
Ps |
Отсюда единственное решение второго сравнения есть (-1)3 • 25 • 26 = -650 = = 99modl07.
Решения исходного сравнения суть: хх = 99(mod321), х2 = (99 + 107) mod321 = = 206mod 321, х3 = (99 + 2 • 107) mod 321 = 313mod 321. >
При попарно взаимно простых модулях ть тъ …, тг линейная система сравнений.
имеет, но теореме 5.5 единственное решение для х по модулю тхт2…тг