Глава двенадцатая. ТЕОРИЯ СРАВНЕНИЙ С АРИФМЕТИЧЕСКИМИ ПРИЛОЖЕНИЯМИ

§ 1. СРАВНЕНИЯ И ИХ СВОЙСТВА

Сравнения в кольце целых чисел.

Пусть — кольцо целых чисел, — фиксированное целое число и — множество всех целых чисел, кратных .

ОПРЕДЕЛЕНИЕ. Два целых числа а и b называют сравнимыми по модулю , если делит .

Если а сравнимо с b по модулю , то это записывается так:

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

Отметим, что отношение сравнимости по модулю совпадает с отношением сравнимости по модулю Отношение сравнимости по модулю 0 совпадает с отношением равенства. Любые два целых числа сравнимы по модулю 1.

Так как отношение сравнимости по модулю есть отношение эквивалентности на множестве Z, то классы эквивалентности, т. е. классы вычетов по модулю , обладают следующими свойствами:

СВОЙСТВО 1.1. Любые два класса вычетов по модулю либо совпадают, либо не пересекаются. Объединение всех классов вычетов по модулю совпадает с множеством Z всех целых чисел.

СВОЙСТВО 1.2. Пусть А и В — классы вычетов по модулю . Смежные классы, совпадают тогда и только тогда, когда

СВОЙСТВО 1.3. Если А — класс вычетов по модулю — любой элемент из А, то .

ПРЕДЛОЖЕНИЕ 1.1. Числа сравнимы по модулю тогда и только тогда, когда при делении на они дают одинаковые остатки.

Доказательство. Пусть при делении с остатком чисел а и b на получаются частные q и и остатки

Предположим, что Вычитая из первого равенства второе, получим

Если , то согласно определению сравнимости а — b делится на и поэтому . С другой стороны, если то в силу (1) делится на , т. е. .

Простейшие свойства сравнений.

Многие свойства сравнений аналогичны свойствам равенств.

СВОЙСТВО 1.4. Сравнения можно почленно складывать и вычитать, т. е. если , то .

Доказательство. По условию, Следовательно, .

СВОЙСТВО 1.5. Сравнения можно почленно перемножить, т. е. если , то .

В частности, обе части сравнения можно умножить на одно и то же целое число.

Доказательство. По условию, . Следовательно,

СВОЙСТВО 1.6. Обе части сравнения можно разделить на их общий множитель, если он взаимно простой с модулем.

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

СВОЙСТВО 1.7. Обе части сравнения и модуль можно разделить на их общий делитель.

Доказательство. Если то делится на Следовательно, делится на , т. е. .

СВОЙСТВО 1.8. Пусть есть любой делитель числа т. Если то а

Доказательство. Если то делится на . Так как — делитель , то делится на .