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

Введение и историческая справка

Китайская теорема об остатках — одно из фундаментальных утверждений теории чисел, которое описывает способ одновременного решения нескольких сравнений по модулю. Зародившись в древнем Китае (работа, приписываемая Сунь-цзы), теорема получила современное строгое формулирование в работах европейских математиков и стала базовым инструментом в теории вычетов.

Простейший иллюстративный пример выглядит так: $x\equiv 2 \pmod{3},\; x\equiv 3 \pmod{5}$. Этот пример показывает идею: для некоторых наборов модулей и остатков можно найти целое число, дающее заданные остатки при делении на эти модули.

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

Сравнение по модулю - выражение вида $a\equiv b \pmod{n}$, которое говорит, что числа a и b дают одинаковый остаток при делении на n.

Модуль - положительное целое число n, относительно которого определяется сравнение по модулю; модуль задаёт класс эквивалентности для целых чисел.

Независимые (взаимно простые) модули - два модуля m и n называются взаимно простыми, если $\gcd(m,n)=1$.

Класс вычетов - множество чисел, дающих при делении на модуль одинаковый остаток; обычно обозначается через остаток a и модуль n.

Формулировка теоремы

Рассмотрим систему сравнений вида $x\equiv a_i \pmod{m_i},\quad i=1,\dots,k$. Китайская теорема об остатках в классическом виде утверждает следующее: если модули попарно взаимно просты, т.е. выполняется условие $\gcd(m_i,m_j)=1\quad\text{для }i\ne j$, то система имеет решение, и это решение единственно с точностью до модуля $M=\prod_{i=1}^k m_i$.

Более конструктивная форма теоремы даёт явную формулу решения. Обозначим $M=\prod_{i=1}^k m_i$ и далее положим $x\equiv \sum_{i=1}^k a_i M_i y_i \pmod{M}$, где {FORMULA_7} удовлетворяют условию $M_i y_i\equiv 1 \pmod{m_i}$. Тогда любое число x, вычисленное по формуле $x\equiv \sum_{i=1}^k a_i M_i y_i \pmod{M}$, является решением системы и любые два решения совпадают по модулю $M=\prod_{i=1}^k m_i$.

Если модули не являются попарно взаимно простыми, то существует обобщённый критерий совместимости: система $x\equiv a_i \pmod{m_i},\quad i=1,\dots,k$ разрешима тогда и только тогда, когда для всех i,j выполняется условие $a_i\equiv a_j \pmod{\gcd(m_i,m_j)}$. В этом случае класс решений описывается модулем, равным наименьшему общному кратному модулов исходной системы.

Конструктивное доказательство и алгоритм

Доказательство для попарно взаимно простых модулей обычно даётся конструктивно. Для двух сравнений приводят уравнение $x\equiv a \pmod{m},\qquad x\equiv b \pmod{n}$. Так как модули взаимно просты, существуют s и t, такие что $s m + t n = 1$. Используя эти коэффициенты, можно построить решение по формуле $x\equiv a t n + b s m \pmod{mn}$.

В общем случае для k сравнений берут произведение модулей $M=\prod_{i=1}^k m_i$ и для каждого i вводят {FORMULA_7}. Затем нужно найти обратный элемент y_i по модулю m_i, т.е. решение сравнения $M_i y_i\equiv 1 \pmod{m_i}$. Такие обратные можно найти с помощью расширенного алгоритма Евклида, который для пар (a,m) даёт целые s,t с свойством $s m + t n = 1$ и позволяет извлечь обратный элемент, если $\gcd(m,n)=1$.

Алгоритм для практического вычисления сводится к последовательному применению расширенного алгоритма Евклида, вычислению M и всех M_i, вычислению обратных и суммированию по формуле $x\equiv \sum_{i=1}^k a_i M_i y_i \pmod{M}$. После этого результат обычно приводят к каноническому представлению остатка в интервале от 0 до M-1.

Примеры

Применения и замечания

Китайская теорема об остатках активно используется в задачах восстановления целого числа по его остаткам (например, в сборе «остаточных» измерений), в алгоритмах криптографии (например, при работе с большими модулями в RSA и его модификациях), а также в вычислительной математике при распараллеливании вычислений по модулю.

Практически важно помнить два аспекта: во-первых, удобство использования явной формулы $x\equiv \sum_{i=1}^k a_i M_i y_i \pmod{M}$ при попарно взаимно простых модулях; во-вторых, необходимость проверки условий совместимости $a_i\equiv a_j \pmod{\gcd(m_i,m_j)}$ в общем случае. Для вычислений с большими числами часто используют представление по модулю произведения, что позволяет работать с несколькими меньшими словами процессора параллельно.

Визуально алгоритм можно представить диаграммой процессов: сначала сбор модулей и остатков, затем вычисление M и всех M_i, параллельное нахождение обратных по модулям, суммирование и приведение остатка. (Схема процесса показана на рисунке {IMAGE_0}.) Для пояснения шагов расширенного алгоритма Евклида может быть полезна отдельная иллюстрация {IMAGE_1}.

Задачи для самостоятельного решения

1) Решите систему $x\equiv 2 \pmod{3},\; x\equiv 3 \pmod{5},\; x\equiv 2 \pmod{7}$ (повторить пример 1 самому).

2) Проверьте совместимость и при необходимости найдите решение для системы $a x\equiv 1 \pmod{m}\iff \gcd(a,m)=1$ и для системы $\gcd(4,8)=4$.

3) Составьте алгоритм на псевдокоде, реализующий конструктивный метод с использованием расширенного алгоритма Евклида и протестируйте его на случайных наборах попарно взаимно простых модулей.