Система остаточных классов
Материал из Модулярная арифметики
(Различия между версиями)
Bundin (обсуждение | вклад) (Новая страница: «Система остаточных классов используется для представления больших чисел N, обеспечивая …») |
Bundin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Система остаточных классов используется для представления больших чисел N, обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит изоморфизм \mathbb{Z}/ | + | Система остаточных классов используется для представления больших чисел N, обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит изоморфизм <math>\mathbb{Z}/m_1\cdot\ldots\cdot m_n\mathbb{Z}\cong\mathbb{Z}/m_1\times\ldots\times\mathbb{Z}/m_n</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>. Тогда имеем эпиморфизм колец <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}\to\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}</math>. |
| Строка 9: | Строка 9: | ||
=== Сложение и вычитание === | === Сложение и вычитание === | ||
| − | Пусть | + | Пусть <math>A,B</math>- произвольные натуральные числа. Положим, что <math>A,B</math> представляются в виде системы остаточных классов как <math>(a_1,\ldots ,a_n)</math> и <math>(b_1,\ldots b_n)</math> соответственно. Формально, <math>\varphi^{-1}(a_1,\ldots ,a_n)=A, \varphi^{-1}(b_1,\ldots b_n)=B</math>. В силу того, что <math>\varphi</math>- изоморфизм, то <math>\varphi^{-1}((a_1,\ldots ,a_n)+(b_1,\ldots b_n))=\varphi^{-1}(a_1,\ldots ,a_n)+\varphi^{-1}(b_1,\ldots b_n)</math>. Обозначим через <math>C</math> остаток <math>A+B</math> от деления на <math>M</math>. Тогда <math>C</math> представляется в виде системы остаточных классов как <math>(a_1+b_1,\ldots ,a_n+b_n)</math>. |
=== Умножение === | === Умножение === | ||
| − | $D$- остаток от деления | + | $D$- остаток от деления <math>A\cdot B</math> на <math>M</math>. Тогда <math>D</math> представляется в виде системы остаточных классов в виде <math>(a_1b_1,\ldots ,a_nb_n)</math>. |
=== Деление === | === Деление === | ||
| − | Деление | + | Деление <math>A</math> на <math>B</math> с использованием системы остаточных классов можно выполнять не всегда. Положим, что <math>E</math>- остаток <math>AB^{-1}</math> от деления на <math>M</math>. На языке теории колец это означает, что <math>b_i,1\le i\le n</math> обратим и <math>b_i^{-1}</math>- обратный. Тогда <math>AB^{-1}</math> представляется в виде <math>(a_1b_1^{-1},\ldots ,a_nb_n^{-1})</math>. |
Версия 06:16, 26 января 2013
Система остаточных классов используется для представления больших чисел N, обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит изоморфизм 
, который доставляет китайская теорема об остатках.
Содержание |
Основные определения
Системой остаточных классов называют произвольное конечное множество 
, такое что 
, где 
. Пусть задана произвольная система остаточных классов 
и положим, что 
. Тогда имеем эпиморфизм колец 
, т.ч. 
, который индуцирует канонический изоморфизм 
.
Выполнение арифметических операций
С использованием системы остаточных классов можно выполнять основные арифметические операции.
Сложение и вычитание
Пусть 
- произвольные натуральные числа. Положим, что представляются в виде системы остаточных классов как 
и 
соответственно. Формально, 
. В силу того, что 
- изоморфизм, то 
. Обозначим через 
остаток 
от деления на 
. Тогда представляется в виде системы остаточных классов как 
.
Умножение
$D$- остаток от деления 
на . Тогда 
представляется в виде системы остаточных классов в виде 
.
Деление
Деление 
на 
с использованием системы остаточных классов можно выполнять не всегда. Положим, что 
- остаток 
от деления на . На языке теории колец это означает, что 
обратим и 
- обратный. Тогда представляется в виде 
.
