Сравнения и их основные свойства - История изменений

Isaeva в 12:59, 24 июня 2015

2015-06-24T12:59:58Z

Isaeva в 12:32, 24 июня 2015

2015-06-24T12:32:31Z

Isaeva в 12:53, 23 января 2015

2015-01-23T12:53:29Z

Isaeva в 12:48, 23 января 2015

2015-01-23T12:48:21Z

Isaeva в 11:56, 23 января 2015

2015-01-23T11:56:25Z

Isaeva в 10:19, 23 января 2015

2015-01-23T10:19:54Z

Isaeva в 09:44, 23 января 2015

2015-01-23T09:44:52Z

Isaeva в 09:18, 23 января 2015

2015-01-23T09:18:53Z

Isaeva в 09:54, 28 августа 2014

2014-08-28T09:54:27Z

Isaeva: Новая страница: «Возьмём произвольное фиксированное натуральное число $m$ и будем рассматривать о…»

2014-08-25T11:10:45Z

Новая страница: «Возьмём произвольное фиксированное натуральное число <math> m </math> и будем рассматривать о…»

Новая страница

Возьмём произвольное фиксированное натуральное число <math> m </math> и будем рассматривать остатки при делении на <math> m </math> различных целых чисел.

При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.

== Определения ==

== Примеры ==

== Свойства ==

Для фиксированного натурального числа <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> является отношением эквивалентности на множестве целых чисел.

@@ Строка 149: / Строка 149: @@
-'''Определение.''' Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем math>m</math>.
+'''Определение.''' Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем <math>m</math>.
+Иначе говоря, приведённая система вычетов по модулю <math>m</math> - это система чисел, взаимно простых с модулем, взятых по одному и только по одному из каждого класса вычетов по модулю <math>m</math>. Приведенную систему обычно выбирают из системы наименьших неотрицательных вычетов. Число классов, взаимно простых с модулем <math>m</math>, равно значению функции Эйлера <math>\varphi(m)</math>.
-Т.е. приведённую систему вычетов по модулю <math>m</math> - это система чисел, взаимно простых с модулем, взятых по одному и только по одному из каждого класса. Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Число классов, взаимно простых с модулем <math>m</math>, равно значению функции Эйлера <math>\varphi(m)</math>.

@@ Строка 126: / Строка 126: @@
-Полной системой вычетов по модулю <math>m</math> называется совокупность <math>m</math> целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю <math>m</math>. Каждый класс вычетов по модулю <math>m</math> содержит в точности одно из чисел совокупности всех возможных остатков от деления на <math>m</math>: <math>0, 1, \ldots, m-1</math>. Множество <math>\{0, 1, \ldots, m-1\}</math> называется полной системой наименьших неотрицательных вычетов по модулю <math>m</math>. Можно легко доказать, что любая совокупность <math>m</math> чисел <math>m>1</math>, попарно несравнимых по модулю <math>m</math>, есть полная система вычетов по модулю <math>m</math>.
+'''Определение.''' Полной системой вычетов по модулю <math>m</math> называется совокупность <math>m</math> целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю <math>m</math>.
 Часто рассматривают полную систему наименьших неотрицательных вычетов:
 :<math>0, 1, \ldots, m-1</math>;
@@ Строка 143: / Строка 149: @@
-Можно ввести в рассмотрение приведённую систему вычетов по модулю <math>m</math>, т.е. систему чисел, взятых по одному и только по одному из каждого класса, взаимно простого с модулем.
+'''Определение.''' Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем math>m</math>.
 Число классов, взаимно простых с модулем <math>m</math>, равно значению функции Эйлера <math>\varphi(m)</math>.

← Предыдущая		Версия 12:53, 23 января 2015
Строка 141:		Строка 141:

	:<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>.		:<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>.
		+
		+
		+	Можно ввести в рассмотрение приведённую систему вычетов по модулю <math>m</math>, т.е. систему чисел, взятых по одному и только по одному из каждого класса, взаимно простого с модулем.
		+	Число классов, взаимно простых с модулем <math>m</math>, равно значению функции Эйлера <math>\varphi(m)</math>.

@@ Строка 96: / Строка 96: @@
 * Если сравнение <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> a </math> по модулю <math> m </math> называется '''классом вычетов''' <math> a </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>.

@@ Строка 49: / Строка 49: @@
-Другие свойства:
+:'''Другие свойства:'''
-* Обе части сравнения можно умножить на произвольное целое число. Если <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>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>.
+* Сравнения можно почленно перемножать.
@@ Строка 78: / Строка 87: @@
-* Если сравнение выполняется по модулю <math>m</math>, то оно выполняется и по модулю <math>d</math>, равному любому делителю числа <math>m</math>. Если <math>a \equiv b \pmod m</math> и <math>m/d</math>, то <math>a \equiv b \pmod d</math>.
+* Если сравнение выполняется по модулю <math>m</math>, то оно выполняется и по модулю <math>d</math>, равному любому делителю числа <math>m</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> имеет место по нескольким модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

@@ Строка 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> является отношением эквивалентности на множестве целых чисел.
@@ Строка 45: / Строка 51: @@
 Другие свойства:
-* Если <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> 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> 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>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>k</math> – произвольное натуральное число, то <math> k \cdot a \equiv k \cdot b \pmod {k \cdot 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> 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>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>.

@@ Строка 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>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>.

@@ Строка 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>, то запишем:
 == Примеры ==
 == Свойства ==
@@ Строка 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>.
 == Классы вычетов ==

@@ Строка 4: / Строка 4: @@
 == Определения ==
 == Примеры ==
@@ Строка 16: / Строка 27: @@
 Таким образом, отношение сравнимости по модулю <math> m </math> является отношением эквивалентности на множестве целых чисел.