Сравнения с неизвестным

Пусть задан многочлен – многочлен с целыми коэффициентами и некоторое . Будем рассматривать уравнение

в кольце классов вычетов по модулю – , соответствующим образом интерпретируя коэффициенты многочлена. Если прибегнуть к языку сравнений, то получим сравнение с неизвестным

. (13.6)

Определение 13.16. Степенью сравнения называется наибольший показатель степени буквы , при которой коэффициент не делится на модуль .

Определение 13.17. Решением сравнения называется класс вычетов такой, что , или . Здесь .

Пример 13.17. Решением сравнения четвертой степени является класс .

Пример 13.18. Решением сравнения второй степени являются классы и .

Любое сравнение теоретически можно решать перебором значений ПСВ по модулю . Но при больших это оказывается неудобным даже в простейших случаях.

Рассмотрим сравнения первой степени. Их в общем виде можно записать так:

, где не делится на .

Перепишем это сравнение, переобозначив коэффициенты,

. (13.7)

Пусть сначала . Заставим пробегать ПСВ по модулю . В соответствии с леммой 13.23 тоже будет пробегать ПСВ модуля . Следовательно, для какого-то , причем только одного, попадет в класс, где находится число , что и дает единственное решение в этом случае.

Пусть теперь . Тогда, если бы существовало решение , то выполнялось бы числовое сравнение , откуда понятно, что число должно делиться на . Так что, если , то решения заведомо нет. Пусть . Тогда разделим обе части сравнения и модуль на . Положим, что . В этих обозначениях получаем новое сравнение

, где уже .

Такое сравнение, как было показано, имеет и притом единственное решение , которое, очевидно, будет и решением исходного сравнения по модулю . Если теперь рассмотреть вычеты

,

то все они представляют одно решение по модулю , но являются разными решениями по модулю . Таким образом, в этом случае получаем решений по модулю . Это рассуждение приводит к теореме.

Теорема 13.9.

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

Как уже было сказано, решения сравнения можно искать, перебирая какую-либо ПСВ по модулю . Но кроме этого имеется компактный способ описания решения. Пусть для определенности . Тогда по теореме Эйлера 13.8

,

откуда легко видеть, что класс будет решением сравнения (13.7) . Для получения такого решения явно требуется вычисление значения функции Эйлера, а это

далеко не простая задача. Поэтому приведем весьма эффективный метод решения, использующий разложение в непрерывную дробь числа , по-прежнему считая . Из доказанного свойства непрерывных дробей (лемма 13.8) следует, что

.

В нашем случае, если – длина разложения, то , а . Поэтому имеем

.

Отсюда можно записать сравнение

.

Значит, ,

И тогда ,

т.е., решением исходного сравнения будет класс . Вычисление числителя подходящей дроби может быть эффективно проведено, как показано выше.

Пример 13.19. Пусть надо решить сравнение . Разложим число в непрерывную дробь, точнее вычислим числители и знаменатели подходящих дробей:

,

,

,

.

Составим таблицу

	0	1	2	3	4
		8	1	3	2
	1	8	9	35	79
	0	1	1	4	9

Теперь можно выписать решение: .

Если же пользовать компактным решением, то , поэтому решение будет выглядеть так: .

Пример 13.20. Пусть надо решить сравнение . Легко видеть, не прибегая к алгоритму Евклида, что и число 3 не делит число 7. Поэтому такое сравнение неразрешимо. Немного изменим его. Пусть требуется решить сравнение . Разделим обе части сравнения и модуль на число 3, получим сравнение

.

Его легко решить перебором: . Тогда решениями исходного сравнения будут классы , , .

Рассмотрим теперь системы сравнений первой степени следующего вида:

(13.8) Решением такой системы естественно назвать класс по модулю наименьшего общего кратного , состоящий из чисел, удовлетворяющих каждому сравнению

системы. Если какое-либо сравнения не имеет решения, то вся система неразрешима. Такую систему можно решать последовательной подстановкой решений верхних сравнений в нижние.

Пример 13.21. Пусть требуется решить систему

Решая первое сравнение, получим

, т.е., , .

Подставим этот результат во второе сравнение:

,

,

,

,

.

Откуда , т.е.,

, , , .

Подставим эти результаты в выражение для х. Имеем

,

,

.

Тогда , , .

Наконец, сделаем подстановку в третье сравнение каждого решения:

, , , т.е.,

, , .

Решаем эти сравнения

, , .

Производя соответствующие подстановки в последние выражения для х , находим

В итоге получили 6 решений системы по модулю 840, но по модулю их всего 3. Именно: , , .

Рассмотрим теперь случай взаимно простых модулей, причем будем считать, что все сравнения разрешены относительно х.

Теорема 13.10 (китайская теорема об остатках).

Пусть задана система сравнений

где . Тогда такая система разрешима и имеет единственное решение . Здесь , где

, , .

Доказательство. Существование решения легко проверяется непосредственно. Остается показать единственность такого решения. Действительно, так как удовлетворяет каждое сравнение системы, то можно получить систему эквивалентную исходной в виде

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

Пример 13.22. Решить систему

Найдем . Для этого вычислим величины : , , .

Теперь вычислим , решив соответствующие сравнения:

, ;

, , ;

, , .

Отсюда .

Теорема 13.11. Сравнение , где , эквивалентно системе сравнений вида

Доказательство. Это прямое следствие свойств и числовых сравнений.

Следствие. Если , т.е., представлено в виде канонического разложения, то сравнение из теоремы равносильно системе

Таким образом, требуется уметь решать сравнения по модулю, равному степени простого числа. А последнее невозможно без умения решения сравнений по простому модулю. Метод перебора ПСВ здесь не учитывается.