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

Версия 12:18, 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$ .

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

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

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

@@ Строка 5: / Строка 5: @@
 == Определения ==
-Определение. Два целых числа <math> a </math> и <math> b </math> называются '''сравнимыми по модулю <math> m </math>''', если их разность <math> a-b </math> делится без остатка на <math> m </math>.
+'''Определение.''' Два целых числа <math>a</math> и <math>b</math> называются ''сравнимыми по модулю'' <math>m</math>, если их разность <math>a-b</math> делится без остатка на <math>m</math>.
-Символически сравнимость записывается в виде формулы ('''сравнения'''):
+Символически сравнимость записывается в виде формулы (''сравнения''):
 : <math>a \equiv b \pmod{m}</math>
 Число <math> m </math> называется '''модулем''' сравнения.
-Эквивалентная формулировка:
-Определение. Целые числа <math> a </math> и <math> b </math> называются '''сравнимыми по модулю <math> m </math>''', если остатки от деления этих чисел на <math> m </math> равны.
+Если разность <math>a-b</math> не делится на <math>m</math>, то запишем:
+: <math>a \not \equiv b \pmod{m}</math>.
+Согласно определению, <math> a \equiv 0 \pmod{m} </math> означает, что <math>a</math> делится на <math>m</math>.
+'''Теорема.''' <math> a </math>  сравнимо с <math> b </math> тогда и только тогда, когда <math> a </math> и <math> b </math>  имеют одинаковые остатки при делении на <math> m </math>.
+Поэтому в качестве определения сравнения можно взять следующую эквивалентную формулировку:
+'''Определение.''' Целые числа <math>a</math> и <math>b</math> называются ''сравнимыми по модулю'' <math>m</math>, если остатки от деления этих чисел на <math>m</math> равны.
 == Примеры ==
+: <math>101 \equiv 17 \pmod{21}</math> , т. к. 101 – 17 = 84, а 84 делится без остатка на 21.
+: <math>135 \equiv 11 \pmod{4}</math> , т. к. оба числа 135 и 11 при делении на 4 дают остаток 3.
 == Свойства ==
@@ Строка 22: / Строка 36: @@
 Для фиксированного натурального числа <math> m </math> отношение сравнимости по модулю <math> m </math> обладает следующими свойствами:
-* [[Рефлексивность|рефлексивности]]: для любого целого <math>a</math> справедливо <math> a \equiv a \pmod 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 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> 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> и 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> m </math> является отношением эквивалентности на множестве целых чисел.
 == Классы вычетов ==

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

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

Содержание

Определения

Примеры

Свойства

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

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

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

Варианты

Просмотры

Действия

Поиск

Навигация