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

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

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

Определения

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

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

$a \equiv b \pmod{m}$

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

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

$a \not \equiv b \pmod{m}$.

Согласно определению, $a \equiv 0 \pmod{m}$ означает, что $a$ делится на $m$.

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

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

Примеры

$101 \equiv 17 \pmod{21}$ , т. к. 101 – 17 = 84, а 84 делится без остатка на 21.

$135 \equiv 11 \pmod{4}$ , т. к. оба числа 135 и 11 при делении на 4 дают остаток 3.

Свойства

Для фиксированного натурального числа $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$ является отношением эквивалентности на множестве целых чисел.

Другие свойства:

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

Если $a \equiv b \pmod m$ и $k$ – произвольное целое число, то $k \cdot a \equiv k \cdot b \pmod m$.

• Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.

Если $k \cdot a \equiv k \cdot b \pmod m$ и $(k, m) = 1$, то $a \equiv b \pmod m$.

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

Если $a \equiv b \pmod m$ и $k$ – произвольное натуральное число, то $k \cdot a \equiv k \cdot b \pmod {k \cdot m}$.

• Обе части сравнения и модуль можно разделить на любой их общий делитель.

Если $k \cdot a \equiv k \cdot b \pmod {k \cdot m}$, где $k$ и $m$ – произвольные натуральные числа, то $a \equiv b \pmod m$.

• К любой части сравнения можно прибавить (или отнять от нее) любое число, кратное модуля.

Если $a \equiv b \pmod m$ то при любом целом $n$ $a+n\cdot m \equiv b \pmod m$.

• Сравнения можно почленно складывать и вычитать.

Если $a \equiv b \pmod m$ и $c \equiv d \pmod m$, то $a+c \equiv b+d \pmod m$ и $a-c \equiv b-d \pmod m$.

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

• Сравнения можно почленно перемножать.

Если $a \equiv b \pmod m$ и $c \equiv d \pmod m$, то $a \cdot c \equiv b \cdot d \pmod m$.

• Если $a \equiv b \pmod m$ и $f(x) = c_0 + c_1 \cdot x_1 + \ldots + c_n \cdot x_n$ - произвольный многочлен с целыми коэффициентами, то $f(a) = f(b) \pmod m$.

• Если сравнение выполняется по модулю $m$, то оно выполняется и по модулю $d$, равному любому делителю числа $m$.

Если $a \equiv b \pmod m$ и $d|m$, то $a \equiv b \pmod d$.

• Если $a \equiv b \pmod m$, то множество общих делителей $a$ и $m$ совпадает с множеством общих делителей $b$ и $m$. В частности, $(a,m) = (b,m)$.

• Если сравнение $a \equiv b$ имеет место по нескольким модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

Если $a \equiv b \pmod m_1, a \equiv b \pmod m_2, \ldots, a \equiv b \pmod m_s$, то $a \equiv b \pmod m$, где $m = [m_1, m_2, \ldots, m_s]$.

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

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

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