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

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

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

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

Определение. Целые числа а и b называются сравнимыми по модулю р, если разность чисел а - b делится на р, то есть, если . Таким образом сравнение представляет собой соотношение между тремя числами a,b и p, причем p,играющее своего рода эталона сравнения, мы называем модулем. Для краткости мы будем это соотношение между a, b и p записывать следующим образом: a?b (mod p), a и b будем называть соответственно левой и правой частями сравнения. Число p, стоящее под знаком модуля, будем всегда считать положительным, т.е запись mod p будет означать, что, числа а и b - вычеты. Если разность а - b не делится на р, то а не сравнимо с b по mod p.

Согласно определению а ? 0 (mod p) означает, что а делится на р.

Пример:

101 ? 17 (mod 21)т. к. 101 - 17 = 84, а 84?21.

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

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

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

1. Рефлексивность отношения сравнимости: а ? a (mod p)

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

если, а ? b (mod p) то b ? a (mod p).

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

если а ? b (mod p), b ? c (mod p), то а ? c(mod p).

4. Если а ? b (mod p) и k - произвольное целое число, то kа ? kb (mod p)

5. Если kа ? kb (mod p) и (k, p) = 1, то а ? b (mod p).

6. Если а ? b (mod p)и k- произвольное натуральное число, то kа ? kb (mod kp)

7. Если kа ? kb (mod kp), где k и р - произвольные натуральные числа, то а ? b (mod p)

8. Если а ? b (mod p),c ? d (mod p), то а+c ? b+d (mod p)и а-c ? b-d (mod p).

9. Если а ? b (mod p), c ? d (mod p), то аc ? bd (mod p)

10. Если а ? b (mod p), то при любом целом n > 0,а ? b (mod p).

11. Если а ? b (mod p) и f(x)= +++... - произвольный многочлен с целыми коэффициентами, то f(а) ? f(b) (mod p)

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

13. Если а ? b (mod p) и , то а ? b (mod d)

14. Если а ? b (mod p), то множество общих делителей а и р совпадает с множеством общих делителей b и р. В частности, (a,p)=(b,p).

15. Если а ? b (mod ),а ? b (mod )…,а ? b (mod ), то а ? b (mod p), где p=[,,...,].

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