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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 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>a \equiv b \pmod{m}</math>
  
 
Число <math> 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> 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> является отношением эквивалентности на множестве целых чисел.
 
  
 
== Классы вычетов ==
 
== Классы вычетов ==

Версия 09: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 .

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