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

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

История

Первое известное изложение теоремы содержится в трактате «Сунь-цзы Суаньцзин» («Математический канон Сунь-цзы»), написанном китайским математиком Сунь-цзы (III–V века н. э.). В задаче 26 книги III рассматривается следующий вопрос: «Найти число, которое при делении на 3 даёт остаток 2, при делении на 5 — остаток 3, а при делении на 7 — остаток 2». Сунь-цзы предложил метод решения, основанный на подборе множителей, и дал ответ: 23. Это считается первым известным примером применения китайской теоремы об остатках.

В Европе теорема была переоткрыта в XIII веке Леонардо Фибоначчи в его «Книге абака». В 1801 году Карл Фридрих Гаусс в монографии «Арифметические исследования» (лат. «Disquisitiones Arithmeticae») дал полное и строгое доказательство теоремы, а также сформулировал её в современном виде. Гаусс использовал теорему для решения систем сравнений и для доказательства других результатов теории чисел. Название «китайская теорема об остатках» закрепилось в западной математической литературе в XIX веке благодаря работам таких математиков, как Джеймс Джозеф Сильвестр и Годфри Харолд Харди.

Формулировка

Пусть \( n_1, n_2, \ldots, n_k \) — попарно взаимно простые натуральные числа (то есть \(\gcd(n_i, n_j) = 1\) для всех \( i \neq j \)). Пусть \( a_1, a_2, \ldots, a_k \) — произвольные целые числа. Тогда система сравнений:

\[ \begin{cases} x \equiv a_1 \pmod{n_1}, \\ x \equiv a_2 \pmod{n_2}, \\ \vdots \\ x \equiv a_k \pmod{n_k} \end{cases} \]

имеет единственное решение по модулю \( N = n_1 \cdot n_2 \cdot \ldots \cdot n_k \). Иными словами, существует такое целое число \( x \), что все сравнения выполняются, и любые два решения отличаются на число, кратное \( N \).

Доказательство (конструктивное)

Существование решения доказывается построением. Для каждого \( i \) определим \( N_i = N / n_i \). Поскольку \( n_i \) и \( N_i \) взаимно просты, существует обратный элемент \( y_i \) по модулю \( n_i \), то есть \( N_i \cdot y_i \equiv 1 \pmod{n_i} \). Тогда искомое число \( x \) можно записать в виде:

\[ x = \sum_{i=1}^k a_i \cdot N_i \cdot y_i \pmod{N}. \]

Проверка: при подстановке в \( i \)-е сравнение все слагаемые, кроме \( a_i \cdot N_i \cdot y_i \), делятся на \( n_i \), а \( N_i \cdot y_i \equiv 1 \pmod{n_i} \), поэтому \( x \equiv a_i \pmod{n_i} \). Единственность следует из того, что если два решения \( x_1 \) и \( x_2 \) удовлетворяют системе, то их разность делится на каждое \( n_i \), а значит, и на их произведение \( N \).

Примеры

Классическая задача Сунь-цзы

Найти число \( x \), такое что: \[ x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 2 \pmod{7}. \] Здесь \( n_1 = 3, n_2 = 5, n_3 = 7 \), \( N = 105 \). Вычисляем:

• \( N_1 = 35 \), обратный элемент \( y_1 = 2 \), так как \( 35 \cdot 2 = 70 \equiv 1 \pmod{3} \).
• \( N_2 = 21 \), обратный элемент \( y_2 = 1 \), так как \( 21 \cdot 1 = 21 \equiv 1 \pmod{5} \).
• \( N_3 = 15 \), обратный элемент \( y_3 = 1 \), так как \( 15 \cdot 1 = 15 \equiv 1 \pmod{7} \).

Тогда \( x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \equiv 23 \pmod{105} \). Ответ: 23.

Система с двумя модулями

Решить систему: \[ x \equiv 1 \pmod{4}, \quad x \equiv 3 \pmod{7}. \] \( N = 28 \), \( N_1 = 7 \), \( y_1 = 3 \) (так как \( 7 \cdot 3 = 21 \equiv 1 \pmod{4} \)), \( N_2 = 4 \), \( y_2 = 2 \) (так как \( 4 \cdot 2 = 8 \equiv 1 \pmod{7} \)). Получаем \( x = 1 \cdot 7 \cdot 3 + 3 \cdot 4 \cdot 2 = 21 + 24 = 45 \equiv 17 \pmod{28} \). Проверка: 17 mod 4 = 1, 17 mod 7 = 3.

Обобщения

Версия для колец

Китайская теорема об остатках может быть сформулирована в терминах абстрактной алгебры. Если \( R \) — коммутативное кольцо с единицей, а \( I_1, I_2, \ldots, I_k \) — попарно взаимно простые идеалы (то есть \( I_i + I_j = R \) для всех \( i \neq j \)), то отображение \[ R / (I_1 \cap I_2 \cap \ldots \cap I_k) \to R/I_1 \times R/I_2 \times \ldots \times R/I_k \] является изоморфизмом колец. В частном случае \( R = \mathbb{Z} \) и \( I_i = (n_i) \) получается классическая теорема.

Для не взаимно простых модулей

Если модули не являются попарно взаимно простыми, система может быть несовместной. Необходимое и достаточное условие существования решения: для любых \( i, j \) должно выполняться \( a_i \equiv a_j \pmod{\gcd(n_i, n_j)} \). В этом случае решение существует и единственно по модулю \( \text{НОК}(n_1, \ldots, n_k) \).

Применение

Криптография

Китайская теорема об остатках используется в криптосистеме RSA для ускорения вычислений. При расшифровании или подписании сообщения владелец секретного ключа знает разложение модуля \( N = p \cdot q \) на простые множители. Вместо возведения в степень по модулю \( N \) можно выполнить вычисления по модулям \( p \) и \( q \) отдельно, а затем объединить результаты с помощью теоремы. Это сокращает время вычислений примерно в 4 раза.

Вычислительная математика

Теорема применяется для представления больших целых чисел в виде набора остатков по взаимно простым модулям (система остаточных классов). Это позволяет выполнять сложение, вычитание и умножение параллельно, без переносов между разрядами, что ускоряет арифметические операции в специализированных вычислительных устройствах.

Решение диофантовых уравнений

С помощью китайской теоремы об остатках можно сводить задачи о целых числах к задачам по модулям простых чисел, что упрощает анализ. Например, в комбинаторике и теории кодирования она используется для построения кодов, исправляющих ошибки.

Календарные расчёты

Теорема лежит в основе вычисления дат в различных календарных системах, например, для определения дня недели по заданной дате или для согласования лунного и солнечного календарей.

Интересные факты

• В китайской математической традиции метод решения таких задач назывался «тай-янь» (великое расширение) и был подробно описан в XIII веке математиком Цинь Цзюшао в трактате «Математический трактат в девяти книгах» (1247 год).
• Китайская теорема об остатках является частным случаем более общей теоремы о китайском остатке для колец главных идеалов.
• В современной теории чисел теорема используется для доказательства мультипликативности функции Эйлера: если \( m \) и \( n \) взаимно просты, то \( \varphi(mn) = \varphi(m) \cdot \varphi(n) \).