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

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

Пусть 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)