Сравнения и их основные свойства — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 49: | Строка 49: | ||
− | Другие свойства: | + | :'''Другие свойства:''' |
− | * Обе части сравнения можно умножить на произвольное целое число. Если <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> и <math>k</math> – произвольное целое число, то <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> 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+c \equiv b+d \pmod m</math> и <math>a-c \equiv b-d \pmod m</math>. | ||
Строка 72: | Строка 80: | ||
− | * Сравнения можно почленно перемножать. Если <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>c \equiv d \pmod m</math>, то <math>a \cdot c \equiv b \cdot d \pmod m</math>. | ||
Строка 78: | Строка 87: | ||
− | * Если сравнение выполняется по модулю <math>m</math>, то оно выполняется и по модулю <math>d</math>, равному любому делителю числа <math>m</math>. Если <math>a \equiv b \pmod m</math> и <math>m | + | * Если сравнение выполняется по модулю <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>. | ||
Строка 84: | Строка 94: | ||
− | * Если <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>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>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>m</math> - это система чисел, взаимно простых с модулем, взятых по одному и только по одному из каждого класса вычетов по модулю <math>m</math>. Приведенную систему обычно выбирают из системы наименьших неотрицательных вычетов. Число классов, взаимно простых с модулем <math>m</math>, равно значению функции Эйлера <math>\varphi(m)</math>. |
Текущая версия на 12:59, 24 июня 2015
Возьмём произвольное фиксированное натуральное число и будем рассматривать остатки при делении на
различных целых чисел.
При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.
Содержание
[убрать]Определения
Определение. Два целых числа и
называются сравнимыми по модулю
, если их разность
делится без остатка на
.
Символически сравнимость записывается в виде формулы (сравнения):
Число называется модулем сравнения.
Если разность не делится на
, то запишем:
-
.
Согласно определению, означает, что
делится на
.
Теорема. сравнимо с
тогда и только тогда, когда
и
имеют одинаковые остатки при делении на
.
Поэтому в качестве определения сравнения можно взять следующую эквивалентную формулировку:
Определение. Целые числа и
называются сравнимыми по модулю
, если остатки от деления этих чисел на
равны.
Примеры
-
, т. к. 101 – 17 = 84, а 84 делится без остатка на 21.
-
, т. к. оба числа 135 и 11 при делении на 4 дают остаток 3.
Свойства
Для фиксированного натурального числа отношение сравнимости по модулю
обладает следующими свойствами:
- Рефлексивность: для любого целого
справедливо
.
- Симметричность: если
, то
.
- Транзитивность: если
и
, то
.
Таким образом, отношение сравнимости по модулю является отношением эквивалентности на множестве целых чисел.
- Другие свойства:
- Обе части сравнения можно умножить на произвольное целое число.
- Если
и
– произвольное целое число, то
.
- Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.
- Если
и
, то
.
- Обе части сравнения и модуль можно умножить на одно и то же целое.
- Если
и
– произвольное натуральное число, то
.
- Обе части сравнения и модуль можно разделить на любой их общий делитель.
- Если
, где
и
– произвольные натуральные числа, то
.
- К любой части сравнения можно прибавить (или отнять от нее) любое число, кратное модуля.
- Если
то при любом целом
.
- Сравнения можно почленно складывать и вычитать.
- Если
и
, то
и
.
- Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть.
- Сравнения можно почленно перемножать.
- Если
и
, то
.
- Если
и
- произвольный многочлен с целыми коэффициентами, то
.
- Если сравнение выполняется по модулю
, то оно выполняется и по модулю
, равному любому делителю числа
.
- Если
и
, то
.
- Если
, то множество общих делителей
и
совпадает с множеством общих делителей
и
. В частности,
.
- Если сравнение
имеет место по нескольким модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
- Если
, то
, где
.
- Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения делится на это число.
Классы вычетов
При делении целых чисел на модуль в остатке получатся числа
.
Отнесём все целые числа, дающие при делении на один и тот же остаток в один класс, поэтому получится
различных классов по модулю
. В один класс попадут равноостаточные числа, они называются вычетами друг друга.
Определение. Множество всех чисел сравнимых с по модулю
называется классом вычетов
по модулю
.
Обозначим через класс вычетов, которые при делении на
дают остаток
.
Например, числа вида .
Через – числа, дающие при делении остаток
.
Например, числа вида .
Через – числа, дающие при делении остаток
.
Например, числа вида .
Через – числа, дающие при делении остаток
.
Например, числа вида .
Определение. Полной системой вычетов по модулю называется совокупность
целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю
.
Каждый класс вычетов по модулю содержит в точности одно из чисел совокупности всех возможных остатков от деления на
:
.
Можно доказать, что любая совокупность чисел
, попарно несравнимых по модулю
, есть полная система вычетов по модулю
.
Часто рассматривают полную систему наименьших неотрицательных вычетов по модулю :
;
полную систему наименьших положительных вычетов:
;
полную систему наименьших по абсолютной величине вычетов:
при чётном
;
при нечётном
.
Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем .
Иначе говоря, приведённая система вычетов по модулю - это система чисел, взаимно простых с модулем, взятых по одному и только по одному из каждого класса вычетов по модулю
. Приведенную систему обычно выбирают из системы наименьших неотрицательных вычетов. Число классов, взаимно простых с модулем
, равно значению функции Эйлера
.