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

Текущая версия на 12:59, 24 июня 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$ .

Можно доказать, что любая совокупность $m$ чисел $m>1$ , попарно несравнимых по модулю $m$ , есть полная система вычетов по модулю $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$ .

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

@@ Строка 35: / Строка 35: @@
 Для фиксированного натурального числа <math> m </math> отношение сравнимости по модулю <math> m </math> обладает следующими свойствами:
 * '''Рефлексивность:''' для любого целого <math>a</math> справедливо <math> a \equiv a \pmod m </math>.
 * '''Симметричность:''' если <math> a \equiv b \pmod m </math>, то <math> b \equiv a \pmod m </math>.
 * '''Транзитивность:''' если <math> a \equiv b \pmod m </math> и <math> b \equiv c \pmod m </math>, то <math> a \equiv c \pmod m </math>.
 Таким образом, отношение сравнимости по модулю <math>m</math> является отношением эквивалентности на множестве целых чисел.
-Другие свойства:
+:'''Другие свойства:'''
-* Если <math>a \equiv b \pmod m</math> и k – произвольное целое число, то <math> k \cdot a \equiv k \cdot b \pmod m</math>.
-* Если <math> k \cdot a \equiv k \cdot b \pmod m </math> и <math> (k, m) = 1 </math>, то <math>a \equiv b \pmod m</math>.
+* Обе части сравнения можно умножить на произвольное целое число.
+:Если <math>a \equiv b \pmod m</math> и <math>k</math> – произвольное целое число, то <math> k \cdot a \equiv k \cdot b \pmod m</math>.
-* Если <math>a \equiv b \pmod m,</math> и k – произвольное натуральное число, то <math> k \cdot a \equiv k \cdot b \pmod {k \cdot m}</math>.
-* Если <math> k \cdot a \equiv k \cdot b \pmod {k \cdot m}</math>, где k и m – произвольные натуральные числа, то <math>a \equiv b \pmod m</math>.
+* Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.
+:Если <math> k \cdot a \equiv k \cdot b \pmod m </math> и <math> (k, m) = 1 </math>, то <math>a \equiv b \pmod m</math>.
+* Обе части сравнения и модуль можно умножить на одно и то же целое.
+:Если <math>a \equiv b \pmod m</math> и <math>k</math> – произвольное натуральное число, то <math> k \cdot a \equiv k \cdot b \pmod {k \cdot m}</math>.
+* Обе части сравнения и модуль можно разделить на любой их общий делитель.
+:Если <math> k \cdot a \equiv k \cdot b \pmod {k \cdot m}</math>, где <math>k</math> и <math>m</math> – произвольные натуральные числа, то <math>a \equiv b \pmod m</math>.
+* К любой части сравнения можно прибавить (или отнять от нее) любое число, кратное модуля.
+:Если <math>a \equiv b \pmod m</math> то при любом целом <math>n</math> <math>a+n\cdot m \equiv b \pmod m</math>.
+* Сравнения можно почленно складывать и вычитать.
+:Если <math>a \equiv b \pmod m</math> и <math>c \equiv d \pmod m</math>, то <math>a+c \equiv b+d \pmod m</math> и <math>a-c \equiv b-d \pmod m</math>.
+* Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть.
+* Сравнения можно почленно перемножать.
+:Если <math>a \equiv b \pmod m</math> и <math>c \equiv d \pmod m</math>, то <math>a \cdot c \equiv b \cdot d \pmod m</math>.
+* Если <math>a \equiv b \pmod m</math> и <math>f(x) = c_0 + c_1 \cdot x_1 + \ldots + c_n \cdot x_n</math> - произвольный многочлен с целыми коэффициентами, то <math>f(a) = f(b) \pmod m</math>.
+* Если сравнение выполняется по модулю <math>m</math>, то оно выполняется и по модулю <math>d</math>, равному любому делителю числа <math>m</math>.
+:Если <math>a \equiv b \pmod m</math> и <math>d|m</math>, то <math>a \equiv b \pmod d</math>.
+* Если <math>a \equiv b \pmod m</math>, то множество общих делителей <math>a</math> и <math>m</math> совпадает с множеством общих делителей <math>b</math> и <math>m</math>. В частности, <math>(a,m) = (b,m)</math>.
+* Если сравнение <math>a \equiv b</math> имеет место по нескольким модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
+:Если <math>a \equiv b \pmod m_1, a \equiv b \pmod m_2, \ldots, a \equiv b \pmod m_s</math>, то <math>a \equiv b \pmod m</math>, где <math>m = [m_1, m_2, \ldots, m_s]</math>.
+* Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения делится на это число.
 == Классы вычетов ==
-Отнесём все целые числа, дающие при делении на <math> m </math>  один и тот же остаток в один класс, поэтому получится <math> m </math> различных классов по модулю <math> m </math>.
+При делении целых чисел на модуль <math>m</math> в остатке получатся числа <math>0, 1, 2, 3,\ldots, {m-1}</math>.
+Отнесём все целые числа, дающие при делении на <math>m</math> один и тот же остаток в один класс, поэтому получится <math>m</math> различных классов по модулю <math>m</math>. В один класс попадут равноостаточные числа, они называются вычетами друг друга.
+'''Определение.''' Множество всех чисел сравнимых с <math>a</math> по модулю <math>m</math> называется '''классом вычетов''' <math>a </math> по модулю <math>m</math>.
+Обозначим через <math>A_0</math> класс вычетов, которые при делении на <math>m</math> дают остаток <math>0</math>.
+Например, числа вида <math>mt, t \in Z</math>.
+Через <math>A_1</math> – числа, дающие при делении остаток <math>1</math>.
+Например, числа вида <math>mt+1, t \in Z</math>.
+Через <math>A_2</math> – числа, дающие при делении остаток <math>2</math>.
+Например, числа вида <math>mt+2, t \in Z</math>.
+Через <math>A_{m-1}</math> – числа, дающие при делении остаток <math>m-1</math>.
+Например, числа вида <math>mt+(m-1), t \in Z</math>.
+'''Определение.''' Полной системой вычетов по модулю <math>m</math> называется совокупность <math>m</math> целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю <math>m</math>.
+Каждый класс вычетов по модулю <math>m</math> содержит в точности одно из чисел совокупности всех возможных остатков от деления на <math>m</math>: <math>0, 1, \ldots, m-1</math>.
+Можно доказать, что любая совокупность <math>m</math> чисел <math>m>1</math>, попарно несравнимых по модулю <math>m</math>, есть полная система вычетов по модулю <math>m</math>.
+Часто рассматривают полную систему наименьших неотрицательных вычетов по модулю <math>m</math>:
+:<math>0, 1, \ldots, m-1</math>;
+полную систему наименьших положительных вычетов:
+:<math>1, 2, \ldots, m</math>;
+полную систему наименьших по абсолютной величине вычетов:
+:<math>{-\frac{m}{2}+1}, {-\frac{m}{2}+2}, \ldots, -2, -1, 0, 1, 2, \ldots, {\frac{m}{2}}</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>.
+'''Определение.''' Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем <math>m</math>.
-Множество всех чисел сравнимых с <math> a </math> по модулю <math> m </math> называется '''классом вычетов''' <math> a </math> по модулю <math> m </math>.
+Иначе говоря, приведённая система вычетов по модулю <math>m</math> - это система чисел, взаимно простых с модулем, взятых по одному и только по одному из каждого класса вычетов по модулю <math>m</math>. Приведенную систему обычно выбирают из системы наименьших неотрицательных вычетов. Число классов, взаимно простых с модулем <math>m</math>, равно значению функции Эйлера <math>\varphi(m)</math>.

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

Текущая версия на 12:59, 24 июня 2015

Содержание

Определения

Примеры

Свойства

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты