§ 2. Теория сравнений

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

Так, если целые числа разбиваются на классы четных и нечетных чисел. Если , классы в этом смысле составляют числа вида при целых k и т. д. Числа, относящиеся к одному классу, называются сравнимыми, и изучение свойств классов носит название теории сравнений. Переходим к точным определениям относящихся сюда понятий.

1. Определение и простейшие свойства.

Пусть m — натуральное число. Два целых числа а и b называются сравнимыми по модулю , если их разность а — b делится на т. Высказывание «а и b сравнимы по модулю » записывается в виде .

Предложение ; далее, если , то если а , то

Действительно, делится на любое число; если делится на , то и делится на ; если а — b и делятся на , то тоже делится на .

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

Предложение 2. Каждое целое число сравнимо по модулю с одним и только одним из чисел ряда

Действительно, пусть а — некоторое целое число. Поделим его на m с остатком: . Ясно, что ибо делится на Итак, каждое целое число а сравнимо со своим остатком при делении на . Остается показать, что среди чисел нет сравнимых по модулю . Но это ясно — если взять два различных целых числа этого ряда и вычесть из большего меньшее, мы получим в качестве разности положительное число, меньшее чем , и, следовательно, эта разность не делится на т. Предложение доказано.

В процессе доказательства мы убедились, что каждый класс по модулю действительно состоит из чисел, дающих один и тот же остаток при делении на т.

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

Предложение 3. Если то

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

Предложение 4. Если то

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

В частности, если и с — любое целое число, то .

Предложение 5. Если и число с взаимно просто с то

Действительно, если то делится на с взаимно просто с m и согласно предложению делится на что и требовалось доказать.

Таким образом, обе части сравнения можно сократить на множитель, взаимно простой с модулем. Без предположения о взаимной простоте это, вообще говоря, делать нельзя. Так, но