Версия 08:41, 25 августа 2014

Теоретико-числовая база построения системы остаточных классов

Сравнения и их основные свойства

Возьмём произвольное фиксированное натуральное число Шаблон:Math и будем рассматривать остатки при делении на Шаблон:Math различных целых чисел.

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

Определение. Два целых числа Шаблон:Math и Шаблон:Math называются сравнимыми по модулю m, если их разность Шаблон:Math делится без остатка на Шаблон:Math.

Символически сравнимость записывается в виде формулы (сравнения):

Число Шаблон:Math называется модулем сравнения.

Эквивалентная формулировка:

Определение’. Целые числа Шаблон:Math и Шаблон:Math называются сравнимыми по модулю m, если остатки от деления этих чисел наШаблон:Math равны.

Отношение сравнимости по модулю Шаблон:Math обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.

Отнесём все целые числа, дающие при делении на Шаблон:Math один и тот же остаток в один класс, поэтому получится Шаблон:Math различных классов по модулю Шаблон:Math. Множество всех чисел сравнимых с Шаблон:Math по модулю Шаблон:Math называется классом вычетов Шаблон:Math по модулю Шаблон:Math

Подробнее о свойствах сравнений и классах вычетов смотри

Теорема о делении с остатком. Алгоритм Евклида

Китайская теорема об остатках

Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю

Числа Мерсенна, Ферма и операции над ними

Математические модели модулярного представления и параллельной обработки информации

Представление числа в системе остаточных классов. Модульные операции

Основные методы и алгоритмы перехода от позиционного представления к остаткам

Восстановление позиционного представления числа по его остаткам

Расширение диапазона представления чисел

Литература