Линейные сравнения с одним неизвестным (стр. 3 )

Мы доказали даже несколько более сильное утверждение, чем теорема 8. Теперь применим эту теорему для доказательства китайской теоремы об остатках (немного в другой формулировке).

Теорема 9. Пусть даны попарно взаимно простых чисел и чиселтаких, что . Тогда существует число , дающее при делении на остаток .

Доказательство. Применим индукцию по . При утверждение теоремы очевидно. Пусть теорема справедлива при . Тогда существует число такое, что при . Пусть . Рассмотрим числа . Поскольку взаимно просто с , из доказательства теоремы 9 следует, что среди выписанных чисел найдется число , дающее при делении на остаток . В то же время при делении на число дает остатки соответственно. Теорема доказана.

И наконец, еще одна теорема.

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

.

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

Доказательство. По китайской теореме об остатках существует такое , что . Но тогда числа удовлетворяют условию теоремы.

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

Теорема 10. Пусть - попарно взаимно простые числа, ; подобраны так, что .Тогда решение системы (12) будет иметь вид: .

Пример 1. Решить сравнение .

Решение. I способ. Решим сравнение методом проб (подстановка в сравнение чисел ПСВ). Выпишем ПСВ (наименьших неотрицательных): 0, 1, 2, 3, 4, 5, 6, 7, 8 и подставим каждый вычет в данное сравнение: не сравнимо с ; не сравнимо с 5; . Следовательно, - решение. Дальше проверять не следует, т. к. поскольку , то данное сравнение имеет единственное решение. Этот способ применяется при небольших модулях. При больших модулях подстановку вычетов ПСВ проводят только на заключительном этапе построения равносильных сравнений.

II способ. Приведение сравнения I-й степени к равносильному сравнению с коэффициентом при , равном 1. Этот способ основывается на проведении ряда равносильных преобразований заданного сравнения. Прибавив в правой части 9, получим: или . Так как , то обе части сравнения можно поделить на 7. Получим: .

III способ. (способ Эйлера). Применим теорему Эйлера:

, , . Умножим обе части сравнения на . , , или , , . Можно сразу же по общей формуле записать: . Отметим, что метод решения сравнения, основанный на применении теоремы Эйлера и Ферма, нельзя отнести к рациональным методам решения сравнений.

Пример 2. Разрешимы ли следующие сравнения:

1)  ; 2) ; 3) .

Решение. 1) Так как , следовательно, сравнение имеет единственное решение: .

2)  Так как и , следовательно, сравнение имеет по модулю 21 три класса решений, которые объединяются в один класс по модулю . Данное сравнение равносильно (сокращение на 3) сравнению из условия 1). Общее решение: , где . Окончательно получим: , , .

Пример 3. Решить сравнение с помощью цепных дробей (4-способ).

Решение. Так как , , то сравнение имеет 6 решений. Поделив обе части сравнения и модуль на 6, получим сравнение . Представим в виде цепной дроби число . , . Составим таблицу подходящих дробей.