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

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Напомним определение деления с остатком.
 
Напомним определение деления с остатком.
  
Определение. Говорят, что целое число <math> n </math> делится на натуральное число <math> m </math> с остатком, если имеется пара чисел <math> q </math> и <math> r </math>, где q- целое, r- натуральное или ноль, причём 0≤ r<b, такие, что <math> n = m \cdot q + r </math>, причём <math> 0 <= 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> 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>.

Версия 16:33, 25 августа 2014

Содержание

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

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

Определение. Говорят, что целое число  n делится на натуральное число  m с остатком, если имеется пара чисел  q и  r , где  q - целое,  r - натуральное или ноль, причём Невозможно разобрать выражение (лексическая ошибка): 0 <= r < m, такие, что <math> n = m \cdot q + r .  n называется делимым,  m - делителем,  q - неполным частным,  r - остатком.

Пример: 48 при делении на 5 даёт остаток 3, т.к. Невозможно разобрать выражение (лексическая ошибка): 48=5⋅9+3 , Невозможно разобрать выражение (лексическая ошибка): 0≤ 3<5 ,  -48 при делении на 5 даёт остаток 2, т.к. Невозможно разобрать выражение (лексическая ошибка): -48=5⋅(-10)+2 , Невозможно разобрать выражение (лексическая ошибка): 0≤ 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 .

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


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

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

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

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

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

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

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

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

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

Литература


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

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