Система остаточных классов — различия между версиями

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

Версия 03:16, 26 января 2013

Система остаточных классов используется для представления больших чисел N, обеспечивая таким образом более эффективные вычисления. В основе данного представления лежит изоморфизм \mathbb{Z}/m_1\cdot\ldots\cdot m_n\mathbb{Z}\cong\mathbb{Z}/m_1\times\ldots\times\mathbb{Z}/m_n , который доставляет китайская теорема об остатках.

Основные определения

Системой остаточных классов называют произвольное конечное множество \{m_1,\ldots ,m_n\}\subset\mathbb{N}, такое что \gcd\limits_{i\ne j}(m_i,m_j)=1, где n\in\mathbb{N}. Пусть задана произвольная система остаточных классов \{m_1,\ldots ,m_n\} и положим, что M=\prod\limits_{i=1}^{n}m_i. Тогда имеем эпиморфизм колец \varphi: \mathbb{Z}\to\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}, т.ч. \operatorname{Ker}\varphi=M\mathbb{Z}, который индуцирует канонический изоморфизм \mathbb{Z}/M\mathbb{Z}\to\prod\limits_{i=1}^{n}\mathbb{Z}/m_i\mathbb{Z}.


Выполнение арифметических операций

С использованием системы остаточных классов можно выполнять основные арифметические операции.

Сложение и вычитание

Пусть A,B- произвольные натуральные числа. Положим, что A,B представляются в виде системы остаточных классов как (a_1,\ldots ,a_n) и (b_1,\ldots b_n) соответственно. Формально, \varphi^{-1}(a_1,\ldots ,a_n)=A, \varphi^{-1}(b_1,\ldots b_n)=B. В силу того, что \varphi- изоморфизм, то \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). Обозначим через C остаток A+B от деления на M. Тогда C представляется в виде системы остаточных классов как (a_1+b_1,\ldots ,a_n+b_n).

Умножение

$D$- остаток от деления A\cdot B на M. Тогда D представляется в виде системы остаточных классов в виде (a_1b_1,\ldots ,a_nb_n).

Деление

Деление A на B с использованием системы остаточных классов можно выполнять не всегда. Положим, что E- остаток AB^{-1} от деления на M. На языке теории колец это означает, что b_i,1\le i\le n обратим и b_i^{-1}- обратный. Тогда AB^{-1} представляется в виде (a_1b_1^{-1},\ldots ,a_nb_n^{-1}).

Источник — «https://vscripts.ru/w/index.php?title=Система_остаточных_классов&oldid=80»