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

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

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

Определения

Определение. Два целых числа $a$ и $b$ называются сравнимыми по модулю $m$, если их разность $a-b$ делится без остатка на $m$.

Символически сравнимость записывается в виде формулы (сравнения):

$a \equiv b \pmod{m}$

Число $m$ называется модулем сравнения.

Эквивалентная формулировка:

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

Свойства

Для фиксированного натурального числа $m$ отношение сравнимости по модулю $m$ обладает следующими свойствами:

• рефлексивности: для любого целого $a$ справедливо $a \equiv a \pmod m$.
• симметричности: если $a \equiv b \pmod m$, то $b \equiv a \pmod m$.
• транзитивности: если $a \equiv b \pmod m$ и $b \equiv c \pmod m$, то $a \equiv c \pmod m$.

Таким образом, отношение сравнимости по модулю $m$ является отношением эквивалентности на множестве целых чисел.

Классы вычетов

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

Множество всех чисел сравнимых с $a$ по модулю $m$ называется классом вычетов $a$ по модулю $m$.