Сравнимость по модулю

Для двух целых числа х и у введем отношение сравнимости по четности, если их разность - четное число. Легко проверить, что при этом выполняются все три ранее введенные условия эквивалентности. Введенное таким образом отношение эквивалентности разбивает все множество целых чисел на два непересекающихся подмножества: подмножество четных чисел и подмножество нечетных чисел.

Обобщая этот случай, будем говорить, что два целых числа, отличающиеся на кратное какого-нибудь фиксированного натурального числа, эквивалентны. На этом основано понятие сравнимости по модулю, введенное Гауссом.

Число а, сравнимо с b по модулю m, если их разность делится на фиксированное натуральное число m, то есть а - b делится на m. Символически это записывается в виде:

а ≡ b(mod m),

а читается так: а сравнимо с b по модулю m.

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

Например, числа 7 и 19 сравнимы по модулю 4, но не сравнимы по модулю 5, т.к. 19-7=12 делится на 4 и не делится на 5.

Можно сказать также, что число х по модулю m равно остатку от деления нацело числа х на m, так как

x=km+r, r = 0, 1, 2, ... , m-1.

Легко проверить, что сравнимость чисел по данному модулю обладает всеми свойствами эквивалентности. Поэтому множество целых чисел разбивается на классы чисел, сравнимых между собой по модулю m. Число таких классов равно m, и все числа одного класса при делении на m дают один и тот же остаток. Например, если m = 3, то получается три класса: класс чисел, кратных 3 (дающих при делении на 3 остаток 0), класс чисел, дающих при делении на 3 остаток 1, класс чисел, дающих при делении на 3 остаток 2.

Примеры использования сравнений доставляются хорошо известными признаками делимости. Обычное представление числа n цифрами в десятичной системе счисления имеет вид:

n = c10² + b10¹ + a10⁰ ,

где а, b, с, - цифры числа, записанные справа налево, так что а - число единиц, b - числе десятков и т.д. Так как 10^k≡1(mod9) при любом к≥0, то из написанного следует, что

n ≡ c + b + a (mod9),

откуда вытекает признак делимости на 9: n делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. Это рассуждение проходит также и при замене 9 на 3.

Получим признак делимости на 11. Имеют место сравнения:

10≡-1(mod11), 10²≡1(mod11) 10³≡-1(mod11), и так далее. Поэтому n ≡ c - b + a - ….(mod11).

Следовательно, n делится на 11 тогда и только тогда, когда знакопеременная сумма его цифр а - b + с -... делится на 11.

Например, знакопеременная сумма цифр числа 9581 есть 1 - 8 + 5 - 9 = -11, она делится на 11, значит и число 9581 делится на 11.

Если имеют места сравнения: , то их можно почленно складывать, вычитать и перемножать так же, как и равенства:

.

Сравнение всегда можно умножить на целое число:

если , то

Однако сокращение сравнения на какой-либо множитель не всегда возможно, Например, , но нельзя произвести сокращение на общий для чисел 42 и 12 множитель 6; такое сокращение приводит к неверному результату, поскольку .

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

Выше было уже отмечено, что любое целое число сравнимо по mod m с одним из следующих чисел: 0, 1, 2,... , m-1.

Помимо этого ряда, имеются и другие ряды чисел, обладающие тем же свойством; так, например, любое число сравнимо по mod 5 с одним из следующих чисел: 0, 1, 2, 3, 4, но так же сравнимо с одним из следующих чисел: 0, -4, -3, -2, -1, или 0, 1, -1, 2, -2. Любой такой ряд чисел называется полной системой вычетов по модулю 5.

Таким образом, полной системой вычетов по modm называется любой ряд из m чисел, никакие два из которых несравнимы друг с другом. Обычно используется полная система вычетов, состоящая из чисел: 0, 1, 2, ..., m-1. Вычетом числа n по модулю m является остаток от деления n на m, что следует из представления n = km + r, 0<r<m - 1.