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

Система остаточных классов используется для представления больших чисел 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})$.