Система остаточных классов - введение
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
== Сравнения и их основные свойства == | == Сравнения и их основные свойства == | ||
| − | Возьмём произвольное фиксированное натуральное число | + | Возьмём произвольное фиксированное натуральное число <math> m </math> и будем рассматривать остатки при делении на <math> m </math> различных целых чисел. |
При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю. | При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю. | ||
| − | Определение. Два целых числа | + | Определение. Два целых числа <math> a </math>и <math> b </math>называются '''сравнимыми по модулю m''', если их разность <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> a </math>и <math> b </math>называются '''сравнимыми по модулю m''', если остатки от деления этих чисел на<math> m </math> равны. |
| − | Отношение сравнимости по модулю | + | Отношение сравнимости по модулю <math> m </math> обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности. |
| − | Отнесём все целые числа, дающие при делении на | + | Отнесём все целые числа, дающие при делении на <math> m </math> один и тот же остаток в один класс, поэтому получится <math> m </math> различных классов по модулю <math> m </math>. |
| − | Множество всех чисел сравнимых с | + | Множество всех чисел сравнимых с <math> a </math>по модулю <math> m </math>называется '''классом вычетов <math> a </math>по модулю <math> m </math>. |
| − | Подробнее о свойствах сравнений и классах вычетов смотри | + | Подробнее о свойствах сравнений и классах вычетов смотри [[Сравнения и их основные свойства| Сравнения и их основные свойства]] |
Версия 15:14, 25 августа 2014
Содержание |
Теоретико-числовая база построения системы остаточных классов
Сравнения и их основные свойства
Возьмём произвольное фиксированное натуральное число 
и будем рассматривать остатки при делении на различных целых чисел.
При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.
Определение. Два целых числа 
и 
называются сравнимыми по модулю m, если их разность Невозможно разобрать выражение (лексическая ошибка): a − b
делится без остатка на
Символически сравнимость записывается в виде формулы (сравнения):
Число называется модулем сравнения.
Эквивалентная формулировка:
Определение’. Целые числа и называются сравнимыми по модулю m, если остатки от деления этих чисел на равны.
Отношение сравнимости по модулю обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.
Отнесём все целые числа, дающие при делении на один и тот же остаток в один класс, поэтому получится различных классов по модулю .
Множество всех чисел сравнимых с по модулю называется классом вычетов по модулю .
Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства
