Свойства сравнений, не зависящих от модуля (4, 5, 6)

4) К обеим частям сравнения можно прибавлять одно и то же целое число.

Док-во:; (a+t)(b+t)(mod m); a+t-b-t=a-b (a+t)(b+t)(mod m).

5) Сравнение по одному и тому же модулю можно почленно перемножать.

Доказательство: Пусть;. Докажем, что acbd (mod m), т. е. (ac-bd).

• (ac-bd)=ac-bd-bc+bc=c (a-b)+b (c-d).
• 6) Обе части сравнения можно умножать на одно и то же целое число.

Доказательство:. Докажем, что, т. е. (at-bt)m.

at-bt=t*(a-b).

Свойства сравнений, зависящие от модуля (1,2)

1) Если и mn, то .

Доказательство: Действительно, если (a-b)m и mn (a-b)n.

2) Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.

Доказательство: Пусть, т. е. a-b=mt, t? Z, ac-bc=mtc, ac-bc=(mc)tacbc (mod mc).

Свойства сравнений, зависящие от модуля (3)

3) Пусть дан многочлен f (x) с целыми коэффициентами. Тогда если, то f (a)f (b)(mod m).

Доказательство: Действительно, пусть.

+…

____.

f (a)f (b)(mod m).

Класс вычетов по модулю m

Все множество целых чисел можно разбить на n-непересекающиеся … в зависимости от деления на число m. Известно, что при делении на целое число m получаются остатки 0,1,2,…, m-1. Совокупность всех целых чисел, которые делятся на m, обозначим, которые дают остаток 1 обозначим, …,, получим m подмножеств, которые попарно пересекаются. Каждое такое подмножество называется классом вычета по модулю m.

a, b-принадлежат одному классу вычетов; (a-b)m.

верно и обратное: если (a-b)m, то они принадлежат одному классу вычетов по модулю m.

Все множество классов вычетов — Zm.

Классы вычетов можно складывать и умножать. Чтобы сложить 2а класса вычетов, а и b нужно взять по представителю из каждого класса, найти сумму с, а затем найти класс, который содержит это число с. Аналогично с умножением.

При выполнении операции «» нейтральный элемент —, а при «+» —. Операции «» и «+» -ассоциативны, коммутативны; операция «» дистрибутивна относительно «+». .

Таким образом, множество всех классов Zm с операциями «+"и ««образуют коммутативное кольцо с 1. Его называют кольцом вычетов по модулю m.