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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 45: Строка 45:
 
Другие свойства:
 
Другие свойства:
  
−
* Если <math>a \equiv b \pmod m</math> и k – произвольное целое число, то <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> и k – произвольное натуральное число, то <math> k \cdot a \equiv k \cdot b \pmod {k \cdot 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 {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>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>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 \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>.
  
  

Версия 09:44, 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 и 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.
  • Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть.
  • Если 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 \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 один и тот же остаток в один класс, поэтому получится m различных классов по модулю m .

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

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