Основные теоремы о сравнениях

Теорема 1 (признак сравнимости двух чисел по модулю).Два целых числа и сравнимы по модулю тогда и только тогда, когда и имеют одинаковые остатки при делении на .

Доказательство. Пусть остатки при делении и на равны, т. е.

(1.1).

(1.2).

где.

Вычтем (1.2) из (1.1); получим т. е. или.

Обратно, пусть это означает, что или.

(1.3).

Разделим на; получим Подставив в (1.3), будем иметь т. е. при делении на получается тот же остаток, что и при делении на .

Пример 1. Определим, сравнимы ли числа и по модулю .

Решение. При делении и на получаются одинаковые остатки Следовательно,.

Определение. Два или несколько чисел, дающие при делении на одинаковые остатки, называются равноостаточными или сравнимыми по модулю .

Теорема 2. Отношение сравнимости рефлексивно: .

Доказательство. и имеют одинаковые остатки при делении на .

Теорема 3. Отношение сравнимости симметрично: если, то.

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

Теорема4. Отношение сравнимости транзитивно: если то.

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

Таким образом, отношение сравнимости есть отношение эквивалентности.

Теорема 5. Если и произвольное целое число, то.

.

Доказательство. Если, то,, .

Теорема 6. Если и1, то.

Доказательство. Если, то |, |, но тогда условие дает |, т. е.

Теорема 7. Если и произвольное натуральное число, то.

Доказательство. Если, то |,|,.

Теорема 8. Если, где и произвольные натуральные числа, то.

Доказательство. Если, то |, |,.

натуральное (, тогда |, .

Теорема 9. Если, , то и .

Доказательство. Если и, то и. Получим, что.

Теорема 9'. Если, то .

Теорема 10. Если и, то.

Доказательство. Если и, то и. Тогда по транзитивности сравнений получим, что .

Теорема 10'. Если, то.

.

Доказательство. Последовательно применяя теорему 7, получим:

.

Теорема 11. Если, то при любом целом ,.

Доказательство. При утверждение верно по теореме 2, а при оно верно согласно теореме 10', если и .

Переход от сравнений, к сравнениям.

,.

будем называть соответственно сложением (вычитанием), умножением, возведением в степень сравнений.

Так как из сравнения следует, то из сравнений и следует также, что и .

Теорема 12. Если и произвольный многочлен с целыми коэффициентами, то .

Доказательство. Если, то, согласно теоремам 7 и 11, имеем:

при .

По теореме 9', получаем, т. е.

Теорема12'. Если и многочлен с целыми коэффициентами, то.

.

Теорема 13. Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть.

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

Следствие.В левой и правой частях сравнения можно добавлять или отбрасывать одно и то же слагаемое.

Теорема 14. В сравнении можно отбрасывать или добавлять слагаемые, делящиеся на модуль.

Доказательство. Если и, т. е., то, складывая эти сравнения, получаем. Аналогично из иполучаем .

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

Теорема 15. Еслии, то.

Доказательство. Если, то. Из, в силу транзитивности отношения делимости получаем, .

Теорема 16. Если, то множество общих делителей и совпадает с множеством общих делителей и. В частности,.

Доказательство. Если, то, ,, любой общий делитель чисел и является общим делителем чисел и, и, наоборот, если и, то .

Поскольку пара и пара имеют одни и те же общие делители, то и .

Теорема 17. Если,, то, где .

Доказательство. Если,, то, то и, согласно свойствам наименьшего общего кратного,.