§ 1. Сравнения и их основные свойства

Возьмём произвольное фиксированное натуральное число p и будем рассматривать остатки при делении на р различных целых чисел.

При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.

Определение. Целые числа а и b называются сравнимыми по модулю р, если разность чисел а - b делится на р, то есть, если . Соотношение между а, b и р запишем в виде:

(1.1)

запись mod p будет означать, что , числа а и b - вычеты.

Если разность а - b не делится на р, то запишем:

.

Согласно определению означает, что а делится на р.

Примеры:

, т. к. 101 - 17 = 84, а или , т. к. числа 135 и 11 при делении на 4 дают остаток 3.

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

Определение: Целые числа а и b называются сравнимыми по модулю р, если остатки от деления этих чисел на р равны.

Дадим основные свойства сравнений:

1. Рефлексивность отношения сравнимости:

2. Симметричность отношения сравнимости:

если, , то .

3. Транзитивность отношения сравнимости:

если , , то .

4. Если и k - произвольное целое число, то .

5. Если и (k, p) = 1, то .

6. Если и k - произвольное натуральное число, то .

7. Если , где k и р - произвольные натуральные числа, то .

8. Если , , то и .

9. Если , , то .

10. Если , то при любом целом n > 0, .

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

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

13. Если и , то .

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

15. Если , , …, , то , где .

При делении целого числа на модуль р в остатке получается 0, 1, 2, 3,…, р - 1 чисел.

Отнесём все целые числа, дающие при делении на р один и тот же остаток в один класс, поэтому получится р - различных классов по модулю р.

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

Обозначим через А₀ - класс вычетов, которые при делении на р дают остаток 0.

Например, числа вида .

Через А₁ - числа, дающие при делении остаток 1.

Например, числа вида .

Через А₂ - числа, дающие при делении остаток 2.

Например, числа вида .

Через А_р-1 - числа, дающие при делении остаток р - 1.

Например, числа вида .

Полной системой вычетов по модулю р называется совокупность р-целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю р. Каждый класс вычетов по модулю р содержит в точности одно из чисел совокупности всех возможных остатков от деления на р: 0, 1, …, р - 1. Множество {0, 1, …, р - 1} называется полной системой наименьших неотрицательных вычетов по модулю р. Можно легко доказать, что любая совокупность р чисел (р >1), попарно несравнимых по модулю р, есть полная система вычетов по модулю р. Часто рассматривают полную систему наименьших положительных вычетов: 1, 2, …, р; полную систему наименьших по абсолютной величине вычетов:

 при чётном р и

при р нечётном.

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

Число классов, взаимно простых с модулем р, равно значению функции Эйлера ц(р).