Система остаточных классов - введение — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 92: | Строка 92: | ||
Другими словами, отображение, которое каждому целому числу <math>x</math>, <math>0\le x <p</math>, ставит в соответствие кортеж <math>a_1, a_2,\ldots, a_k</math>, где <math>x \equiv a_i \pmod{p_i}, i = 1, \ldots k</math> является биекцией кольца <math>Z_P</math> на декартово произведение <math>Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k}</math> колец <math>Z_{p_1}, Z_{p_2}, \ldots, Z_{p_k}</math>. | Другими словами, отображение, которое каждому целому числу <math>x</math>, <math>0\le x <p</math>, ставит в соответствие кортеж <math>a_1, a_2,\ldots, a_k</math>, где <math>x \equiv a_i \pmod{p_i}, i = 1, \ldots k</math> является биекцией кольца <math>Z_P</math> на декартово произведение <math>Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k}</math> колец <math>Z_{p_1}, Z_{p_2}, \ldots, Z_{p_k}</math>. | ||
| − | Подробности и доказательство теоремы смотри [[Китайская теорема об остатках| Китайская теорема об остатках]] | + | Подробности и доказательство теоремы смотри [[Китайская теорема об остатках| Китайская теорема об остатках]]. |
| + | |||
| + | Смотри также [[Описание КТО II|Китайская теорема об остатках(КТО II)]], [[Описание КТО III|Китайская теорема об остатках (КТО III)]]. | ||
== Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю == | == Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю == | ||
Версия 12:34, 4 сентября 2014
Содержание
Теоретико-числовая база построения системы остаточных классов
Напомним определение деления с остатком.
Определение. Говорят, что целое число 
делится на натуральное число 
с остатком, если имеется пара целых чисел 
и 
, таких, что 
и 
.
называется делимым, - делителем, - неполным частным, - остатком.
Для целых чисел:
Определение. Говорят, что целое число 
делится на натуральное число 
с остатком, если имеется пара целых чисел и , таких, что и 
.
Пример: 48 при делении на 5 даёт остаток 3, т.к. 
, 
, -48 при делении на 5 даёт остаток 2, т.к. 
, 
.
Сравнения и их основные свойства
Возьмём произвольное фиксированное натуральное число и будем рассматривать остатки при делении на различных целых чисел.
При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.
Определение. Два целых числа 
и 
называются сравнимыми по модулю , если их разность 
делится без остатка на .
Символически сравнимость записывается в виде формулы (сравнения):
Число называется модулем сравнения.
Эквивалентная формулировка:
Определение. Целые числа и называются сравнимыми по модулю , если остатки от деления этих чисел на равны.
Отношение сравнимости по модулю обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.
Отнесём все целые числа, дающие при делении на один и тот же остаток в один класс, поэтому получится различных классов по модулю .
Множество всех чисел сравнимых с по модулю называется классом вычетов по модулю .
Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства
Теорема о делении с остатком. Алгоритм Евклида
Теорема о делении с остатком
для любых целых a и b,
, существует единственный набор целых чисел q и r, что a = bq + r и 
, где |b| — модуль числа b.
На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел.
Алгоритм Евклида для целых чисел
Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое 
— это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
Тогда НОД(a,b), наибольший общий делитель и , равен
, последнему ненулевому члену этой последовательности.
Существование таких 
, то есть возможность деления с остатком на для любого целого и целого 
, доказывается индукцией.
Корректность этого алгоритма вытекает из следующих двух утверждений:
- Пусть
, тогда НОД (, ) = НОД (, ).
- НОД(0,) = для любого ненулевого (так как 0 делится на любое целое число, кроме нуля).
Китайская теорема об остатках
Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках (Chinese Remainder Theorem - CRT). Например, эта теорема гарантирует, что при правильном выборе модулей СОК каждое число из динамического диапазона имеет в СОК единственное представление, и по этому представлению можно определить представленное число. В своей первоначальной формулировке эта теорема была доказана китайским математиком Сунь-Цзы приблизительно в 100 г. н.э. В современной формулировке теорема звучит так:
Теорема.
Пусть 
- попарно взаимно простые числа, большие 1, и пусть 
. Тогда существует единственное неотрицательное решение по модулю 
следующей системы сравнений:
-
,
-
,
-
,
-
.
Другими словами, отображение, которое каждому целому числу 
, 
, ставит в соответствие кортеж 
, где 
является биекцией кольца 
на декартово произведение 
колец 
.
Подробности и доказательство теоремы смотри Китайская теорема об остатках.
Смотри также Китайская теорема об остатках(КТО II), Китайская теорема об остатках (КТО III).
