Система остаточных классов - введение — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Напомним определение деления с остатком. | Напомним определение деления с остатком. | ||
| − | Определение. Говорят, что целое число <math> n </math> делится на натуральное число <math> m </math> с остатком, если имеется пара чисел <math> q </math> и <math> r </math>, где q- целое, r- натуральное или ноль, причём | + | Определение. Говорят, что целое число <math> n </math> делится на натуральное число <math> m </math> с остатком, если имеется пара чисел <math> q </math> и <math> r </math>, где <math> q </math> - целое, <math> r </math> - натуральное или ноль, причём <math> 0 <= r < m, такие, что <math> n = m \cdot q + r </math>. <math> n </math> называется делимым, <math> m </math> - делителем, <math> q </math> - неполным частным, <math> r </math> - остатком. |
Пример: 48 при делении на 5 даёт остаток 3, т.к. <math> 48=5⋅9+3</math>, <math> 0≤ 3<5</math>, <math> -48</math> при делении на 5 даёт остаток 2, т.к. <math> -48=5⋅(-10)+2</math>, <math> 0≤ 2<5</math>. | Пример: 48 при делении на 5 даёт остаток 3, т.к. <math> 48=5⋅9+3</math>, <math> 0≤ 3<5</math>, <math> -48</math> при делении на 5 даёт остаток 2, т.к. <math> -48=5⋅(-10)+2</math>, <math> 0≤ 2<5</math>. | ||
Версия 13:33, 25 августа 2014
Содержание
Теоретико-числовая база построения системы остаточных классов
Напомним определение деления с остатком.
Определение. Говорят, что целое число 
делится на натуральное число 
с остатком, если имеется пара чисел 
и 
, где - целое, - натуральное или ноль, причём Невозможно разобрать выражение (лексическая ошибка): 0 <= r < m, такие, что <math> n = m \cdot q + r
. называется делимым, - делителем, - неполным частным, - остатком.
Пример: 48 при делении на 5 даёт остаток 3, т.к. Невозможно разобрать выражение (лексическая ошибка): 48=5⋅9+3
, Невозможно разобрать выражение (лексическая ошибка): 0≤ 3<5
, 
при делении на 5 даёт остаток 2, т.к. Невозможно разобрать выражение (лексическая ошибка): -48=5⋅(-10)+2
, Невозможно разобрать выражение (лексическая ошибка): 0≤ 2<5
.
Сравнения и их основные свойства
Возьмём произвольное фиксированное натуральное число и будем рассматривать остатки при делении на различных целых чисел.
При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.
Определение. Два целых числа 
и 
называются сравнимыми по модулю m, если их разность Невозможно разобрать выражение (лексическая ошибка): a − b
делится без остатка на
Символически сравнимость записывается в виде формулы (сравнения):
Число называется модулем сравнения.
Эквивалентная формулировка:
Определение’. Целые числа и называются сравнимыми по модулю m, если остатки от деления этих чисел на равны.
Отношение сравнимости по модулю обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.
Отнесём все целые числа, дающие при делении на один и тот же остаток в один класс, поэтому получится различных классов по модулю .
Множество всех чисел сравнимых с по модулю называется классом вычетов по модулю .
Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства
