Китайская теорема об остатках

Кита́йская теоре́ма об оста́тках (КТО), утверждение, позволяющее по известным остаткам от деления неотрицательного целого числа ${\displaystyle x}$ на несколько взаимно простых натуральных чисел однозначно определить остаток от деления ${\displaystyle x}$ на наименьшее общее кратное этих чисел. Представление чисел остатками от деления на другие числа характерно для непозиционной системы остаточных классов (СОК), являющейся основным практическим приложением КТО.

В СОК с модулями ${\displaystyle \left\{m_{1},\ m_{2},\ \ldots ,\ m_{n}\right\}}$ целое ${\displaystyle x\geq 0}$ представляется в виде набора остатков от деления ${\displaystyle (x_{1},\ x_{2},\ \ldots ,\ x_{n})}$, где ${\displaystyle x_{i}=x\mod m_{i}}$. Обратное преобразование числа в классическую позиционную десятичную систему счисления, можно осуществить, решив следующую систему сравнений относительно ${\displaystyle x:}$

${\displaystyle {\begin{cases}x_{1}\equiv x\mod m_{1}\,x_{2}\equiv x\mod m_{2}\\\dots \\x_{n}\equiv x\mod m_{n}\end{cases}}}$.

Система сравнений будет иметь единственное решение при условии ${\displaystyle x<m}$. Вычислить решение системы сравнений (найти ${\displaystyle x}$) можно методами теории чисел, вместе с тем КТО предоставляет компактные и удобные формулы для обратного преобразования. Например:</m<></math>

${\displaystyle x=\left(\sum _{i=1}^{n}{\mid M_{i}^{-1}\mid _{m_{i}}\cdot M_{i}\cdot x_{i}}\right)\mod M}$,

где ${\displaystyle M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n}}$ – диапазон СОК, ${\displaystyle M_{i}=M/{m_{i}}}$, ${\displaystyle \left|M_{i}^{-1}\right|_{m_{i}}}$ является решением сравнения ${\displaystyle \alpha M_{i}\equiv 1\mod \ m_{i}}$ относительно ${\displaystyle \alpha }$ (^[1]).

Первое упоминание КТО принадлежит китайскому математику Сунь Цзы в 3 в. н. э. С тех пор разработано множество вариантов КТО, такие, например, как новая КТО (^[2]), новая КТО I и II (^[3]) и ещё больше различных аппаратных реализаций. Даже по сравнению с современными алгоритмами, аппаратные реализации обратного преобразования из СОК в позиционную систему счисления на основе классической КТО характеризуются хорошей сбалансированностью аппаратных затрат и скорости выполнения (^[4]).