Система остаточных классов - введение
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Эквивалентная формулировка: | Эквивалентная формулировка: | ||
| − | + | Определение. Целые числа <math> a </math>и <math> b </math>называются '''сравнимыми по модулю m''', если остатки от деления этих чисел на<math> m </math> равны. | |
Отношение сравнимости по модулю <math> m </math> обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности. | Отношение сравнимости по модулю <math> m </math> обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности. | ||
| Строка 40: | Строка 40: | ||
== Теорема о делении с остатком. Алгоритм Евклида == | == Теорема о делении с остатком. Алгоритм Евклида == | ||
| + | |||
| + | Теорема. для любых целых ''n'' и ''m'', | ||
| + | <math>m \not= 0</math>, существует единственный набор целых чисел ''q'' и ''r'', что n = mq + r и <math>0 \le r < |m|</math>, где |''m''| — модуль числа ''m''. | ||
| + | |||
| + | На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел. | ||
== Китайская теорема об остатках == | == Китайская теорема об остатках == | ||
Версия 16:55, 26 августа 2014
Содержание |
Теоретико-числовая база построения системы остаточных классов
Напомним определение деления с остатком.
Определение. Говорят, что целое число 
делится на натуральное число 
с остатком, если имеется пара целых чисел 
и 
, таких, что 
и 
.
называется делимым, - делителем, - неполным частным, - остатком.
Для целых чисел:
Определение. Говорят, что целое число 
делится на натуральное число 
с остатком, если имеется пара целых чисел и , таких, что и 
.
Пример: 48 при делении на 5 даёт остаток 3, т.к. 
, 
, -48 при делении на 5 даёт остаток 2, т.к. 
, 
.
Сравнения и их основные свойства
Возьмём произвольное фиксированное натуральное число и будем рассматривать остатки при делении на различных целых чисел.
При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.
Определение. Два целых числа 
и 
называются сравнимыми по модулю m, если их разность Невозможно разобрать выражение (лексическая ошибка): a − b
делится без остатка на
Символически сравнимость записывается в виде формулы (сравнения):
Число называется модулем сравнения.
Эквивалентная формулировка:
Определение. Целые числа и называются сравнимыми по модулю m, если остатки от деления этих чисел на равны.
Отношение сравнимости по модулю обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.
Отнесём все целые числа, дающие при делении на один и тот же остаток в один класс, поэтому получится различных классов по модулю .
Множество всех чисел сравнимых с по модулю называется классом вычетов по модулю .
Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства
Теорема о делении с остатком. Алгоритм Евклида
Теорема. для любых целых n и m,
, существует единственный набор целых чисел q и r, что n = mq + r и , где |m| — модуль числа m.
На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел.
