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

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

Ближайшие к «оригинальным» источникам:

1. «Сунь Цзы Суань Цзин» (孙子算经) — «Математический трактат мастера Суня» (3-5 века н.э.): Этот текст содержит самую раннюю известную задачу, решение которой приводит к китайской теореме об остатках. В нем ставится задача о нахождении числа, которое дает остаток 2 при делении на 3, остаток 3 при делении на 5 и остаток 2 при делении на 7. Хотя в книге не дается общего решения в виде теоремы, представлен алгоритм для решения конкретной задачи, который содержит основные идеи теоремы.
2. «Шу Шу Цзю Чжан» (数书九章) — «Математическая книга в девяти разделах» Цинь Цзюшао (秦九韶) (1247 г.): Цинь Цзюшао дал первое известное общее решение для системы линейных сравнений, используя метод, который он назвал «Модульной арифметикой». Этот метод, по сути, и является алгоритмом, который мы сегодня называем китайской теоремой об остатках. Он описывает алгоритм построения решения системы сравнений с попарно взаимно простыми модулями. Цинь Цзюшао применял этот метод для решения астрономических задач, связанных с календарными расчетами.

Формулировка Китайской теоремы об остатках

Пусть n₁, n₂, …, n_k — попарно взаимно простые положительные целые числа, то есть НОД(n_i, n_j) = 1 для всех i ≠ j. Тогда для любых целых чисел a₁, a₂, …, a_k существует целое число x, являющееся решением системы линейных сравнений:

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
…
x ≡ a_k (mod n_k)

Более того, это решение единственно по модулю N = n₁ × n₂ × … × n_k. Другими словами, существует единственное решение x такое, что 0 ≤ x < N.

Формулировка простыми словами:

Если вам заданы остатки числа x при делении на несколько попарно взаимно простых чисел, то можно однозначно определить остаток числа x при делении на произведение этих чисел.

Пример:

Найти число x, такое что:

• x ≡ 2 (mod 3)
• x ≡ 3 (mod 5)
• x ≡ 2 (mod 7)

Тогда, по китайской теореме об остатках, существует единственное решение x по модулю 3 × 5 × 7 = 105.

Алгоритм решения (один из вариантов):

1. Вычислить N: N = n₁ × n₂ × … × n_k
2. Вычислить N_i для каждого i: N_i = N / n_i (то есть, произведение всех модулей, кроме n_i)
3. Найти обратное число N_i по модулю n_i: Найти x_i такое, что N_i × x_i ≡ 1 (mod n_i). Это можно сделать с помощью расширенного алгоритма Евклида.
4. Вычислить решение: x = (a₁ × N₁ × x₁ + a₂ × N₂ × x₂ + … + a_k × N_k × x_k) mod N
5. Привести к диапазону [0, N-1]: Если x < 0, то x = x + N (повторить несколько раз, если x очень маленькое).

Применим алгоритм к примеру выше:

1. N = 3 × 5 × 7 = 105
2. N₁ = 105 / 3 = 35
   N₂ = 105 / 5 = 21
   N₃ = 105 / 7 = 15
3. Найти обратные числа:
   • 35 × x₁ ≡ 1 (mod 3) => 2 × x₁ ≡ 1 (mod 3) => x₁ = 2 (потому что 2 × 2 = 4 ≡ 1 (mod 3))
   • 21 × x₂ ≡ 1 (mod 5) => 1 × x₂ ≡ 1 (mod 5) => x₂ = 1
   • 15 × x₃ ≡ 1 (mod 7) => 1 × x₃ ≡ 1 (mod 7) => x₃ = 1
4. Вычислить решение:
   x = (2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1) mod 105
   x = (140 + 63 + 30) mod 105
   x = 233 mod 105
   x = 23 (остаток)
5. Решение: x = 23. Проверим:
   • 23 ≡ 2 (mod 3) (23 = 7 × 3 + 2)
   • 23 ≡ 3 (mod 5) (23 = 4 × 5 + 3)
   • 23 ≡ 2 (mod 7) (23 = 3 × 7 + 2)