Система остаточных классов — различия между версиями
Bundin (обсуждение | вклад) (→Основные определения) |
Bundin (обсуждение | вклад) (→Основные определения) |
||
| Строка 2: | Строка 2: | ||
== Основные определения == | == Основные определения == | ||
| − | Системой остаточных классов называют произвольное конечное множество <math>\{m_1,\ldots ,m_n\}\subset\mathbb{N}</math>, такое что <math>\gcd\limits_{i\ne j}(m_i,m_j)=1</math>, где <math>n\in\mathbb{N}</math>. Пусть задана произвольная система остаточных классов <math>\{m_1,\ldots ,m_n\}</math> и положим, что <math>M=\prod\limits_{i=1}^{n}m_i</math>. Тогда в силу [http://ru.wikipedia.org/wiki/Китайская_теорема_об_остатках= китайской теоремы об остатках] имеем эпиморфизм колец <math>\varphi: \mathbb{Z}\to\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</math>, т.ч. <math>\operatorname{Ker}\varphi=M\mathbb{Z}</math>, который индуцирует канонический изоморфизм <math>\mathbb{Z}/M\mathbb{Z}\cong\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</math>. | + | Системой остаточных классов называют произвольное конечное множество <math>\{m_1,\ldots ,m_n\}\subset\mathbb{N}</math>, такое что <math>\gcd\limits_{i\ne j}(m_i,m_j)=1</math>, где <math>n\in\mathbb{N}</math>. Пусть задана произвольная система остаточных классов <math>\{m_1,\ldots ,m_n\}</math> и положим, что <math>M=\prod\limits_{i=1}^{n}m_i</math>. Тогда в силу [http://ru.wikipedia.org/wiki/Китайская_теорема_об_остатках= китайской теоремы об остатках] имеем [http://ru.wikipedia.org/wiki/Эпиморфизм= эпиморфизм] [http://ru.wikipedia.org/wiki/Кольцо_(математика)= колец] <math>\varphi: \mathbb{Z}\to\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</math>, т.ч. <math>\operatorname{Ker}\varphi=M\mathbb{Z}</math>, который индуцирует канонический [http://ru.wikipedia.org/wiki/Изоморфизм= изоморфизм] <math>\mathbb{Z}/M\mathbb{Z}\cong\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</math>. |
== Выполнение арифметических операций == | == Выполнение арифметических операций == | ||
Версия 09:56, 28 января 2013
Система остаточных классов используется для представления больших чисел N, обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит изоморфизм 
, который доставляет китайская теорема об остатках.
Содержание
Основные определения
Системой остаточных классов называют произвольное конечное множество 
, такое что 
, где 
. Пусть задана произвольная система остаточных классов 
и положим, что 
. Тогда в силу китайской теоремы об остатках имеем эпиморфизм колец 
, т.ч. 
, который индуцирует канонический изоморфизм 
.
Выполнение арифметических операций
С использованием системы остаточных классов можно выполнять основные арифметические операции.
Сложение и вычитание
Пусть 
- произвольные натуральные числа. Положим, что представляются в виде системы остаточных классов как 
и 
соответственно. Формально, 
. В силу того, что 
- изоморфизм будем иметь 
. Обозначим через 
остаток 
от деления на 
. Тогда представляется в виде системы остаточных классов как 
.
Умножение
- остаток от деления 
на . Тогда представляется в виде системы остаточных классов как 
.
Деление
Деление 
на 
с использованием системы остаточных классов можно выполнять не всегда. Положим, что 
- остаток 
от деления на . На языке теории колец это означает, что 
обратим и 
- обратный. Тогда представляется в виде 
.
Факторизация полупростых чисел
Пусть 
- полупростое число. Рассмотрим систему остаточных классов 
, где 
— 
-е простое число.
