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