Сравнения и их основные свойства — различия между версиями

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 141: Строка 141:
  
 
:<math>-\left[{\frac{m}{2}}\right], {-\left[{\frac{m}{2}}\right]+1}, \ldots, -2, -1, 0, 1, 2, \ldots, \left[{\frac{m}{2}}\right]</math> при нечётном <math>m</math>.
 
:<math>-\left[{\frac{m}{2}}\right], {-\left[{\frac{m}{2}}\right]+1}, \ldots, -2, -1, 0, 1, 2, \ldots, \left[{\frac{m}{2}}\right]</math> при нечётном <math>m</math>.
 +
 +
 +
Можно ввести в рассмотрение приведённую систему вычетов по модулю <math>m</math>, т.е. систему чисел, взятых по одному и только по одному из каждого класса, взаимно простого с модулем.
 +
Число классов, взаимно простых с модулем <math>m</math>, равно значению функции Эйлера <math>\varphi(m)</math>.

Версия 12:53, 23 января 2015

Возьмём произвольное фиксированное натуральное число 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 в остатке получатся числа 0, 1, 2, 3,\ldots, {m-1}.

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

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

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

Например, числа вида mt, t \in Z.

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

Например, числа вида mt+1, t \in Z.

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

Например, числа вида mt+2, t \in Z.

Через A_{m-1} – числа, дающие при делении остаток m-1.

Например, числа вида mt+(m-1), t \in Z.


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

Часто рассматривают полную систему наименьших неотрицательных вычетов:

0, 1, \ldots, m-1;

полную систему наименьших положительных вычетов:

1, 2, \ldots, m;

полную систему наименьших по абсолютной величине вычетов:

{-\frac{m}{2}+1}, {-\frac{m}{2}+2}, \ldots, -2, -1, 0, 1, 2, \ldots, {\frac{m}{2}} при чётном m;
-\left[{\frac{m}{2}}\right], {-\left[{\frac{m}{2}}\right]+1}, \ldots, -2, -1, 0, 1, 2, \ldots, \left[{\frac{m}{2}}\right] при нечётном m.


Можно ввести в рассмотрение приведённую систему вычетов по модулю m, т.е. систему чисел, взятых по одному и только по одному из каждого класса, взаимно простого с модулем. Число классов, взаимно простых с модулем m, равно значению функции Эйлера \varphi(m).

Источник — «https://vscripts.ru/w/index.php?title=Сравнения_и_их_основные_свойства&oldid=1067»