Система остаточных классов - введение

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Содержание

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

Напомним определение деления с остатком.

Определение. Говорят, что целое число n делится на натуральное число m с остатком, если имеется пара чисел q и r, где q - целое, r - натуральное или ноль, причём 0\le r<m, такие, что n = m \cdot q+r. n называется делимым, m - делителем, q - неполным частным, r - остатком.

Пример: 48 при делении на 5 даёт остаток 3, т.к. 48=5\cdot 9+3, 0\le 3<5, -48 при делении на 5 даёт остаток 2, т.к. -48=5\cdot (-10)+2, 0\le 2<5.


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

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

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


Определение. Два целых числа  a и  b называются сравнимыми по модулю m, если их разность Невозможно разобрать выражение (лексическая ошибка): a − b

делится без остатка на  m .

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

a \equiv b \pmod{m}

Число  m называется модулем сравнения.

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

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

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

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

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


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

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

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

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

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

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

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

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

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

Литература


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация