Китайская Теорема об Остатках (Chinese Remainder Theorem)
В древнем Китае военачальники якобы действовали так: отдавали несколько последовательных команд вроде «В колонну по 7 становись!», «В колонну по 11 становись!» и т. д., и в каждом случае смотрели, сколько воинов оказалось в последнем ряду. После этого — только по найденным остаткам — вычисляли общее число солдат.
Алгоритм решения подобных задач в математической литературе называется «китайская теорема об остатках» (Chinese Remainder Theorem). Часто пишут кратко: КТО.
Смысл теоремы очень красив: она позволяет восстановить целое число по набору его остатков при делении на несколько чисел, если эти числа попарно взаимно просты. Это один из классических результатов теории чисел, который давно вышел за пределы «чистой математики» и нашёл применение в компьютерной алгебре и криптографии.
Историческая справка
В арифметической форме эта идея описана в трактате, известном как «Сунь-цзы суаньцзин» (Sunzi Suanjing), который традиционно относят к ранней эпохе (обычно упоминают III век н. э.). В XIII веке китайский математик Цинь Цзюшао существенно обобщил эти методы в книге «Математические рассуждения в девяти главах» (1247), где дал уже систематический алгоритм решения подобных задач.
Задача из книги Сунь Цзы
«Предположим, что имеется неизвестное количество объектов. Разбив их на тройки, получаем в остатке 2; разбив на пятёрки — 3; разбив на семёрки — 2. Сколько имеется объектов?»
После решения этой конкретной задачи в тексте приводится алгоритм для общего случая (при произвольных остатках):
«Умножь число остатков при делении на тройки на 70, добавь к полученному произведение числа остатков при делении на пятёрки на 21, и затем добавь произведение числа остатков при делении на семёрки на 15. Если результат равен 106 или более — вычти кратное 105».
2⋅70 + 3⋅21 + 2⋅15 = 233 = 105⋅2 + 23
Значит, наименьшее решение — 23.
Почему здесь появляются числа 70, 21 и 15? Это не магия: на современном языке математики это частичные произведения и обратные к ним по модулю — они и есть те «кирпичики», из которых строится общий алгоритм.
Два элементарных объяснения
1 способ (комбинаторный)
Выпишем множества решений трёх отдельных условий (достаточно смотреть числа до 3⋅5⋅7 = 105):
x ≡ 2 (mod 3): {2, 5, 8, 11, 14, 17, 20, 23, 26, …}
x ≡ 3 (mod 5): {3, 8, 13, 18, 23, 28, …}
x ≡ 2 (mod 7): {2, 9, 16, 23, 30, …}
Ответ должен лежать в пересечении трёх множеств. В нашем случае наименьшим общим числом оказывается 23 (дальше будут 128, 233 и т. д., то есть все решения вида 23 + 105k).
2 способ (алгебраический)
Запишем условия как равенства с целыми параметрами:
x = 2 + 3q
x = 3 + 5p
x = 2 + 7t
Дальше последовательно «согласуем» первые два равенства, затем полученное — с третьим:
2 + 3q = 3 + 5p
q = (5p + 1)/3 = p + (2p + 1)/3
2p + 1 = 3u
p = (3u − 1)/2 = u + (u − 1)/2
u − 1 = 2v
u = 2v + 1
x = 3 + 5p = 3 + 5(u + v) = 3 + 5(2v + 1 + v) = 8 + 15v
8 + 15v = 2 + 7t
t = (15 v + 6)/7 = 2v + (v + 6)/7
v + 6 = 7w
v = 7w − 6
t = 2(7w − 6) + w = 15w − 12
x = 2 + 7(15w − 12) = 105w − 82 = 105(w − 1) + 23
В результате выходит: x = 105(w − 1) + 23. Это значит, что наименьшее решение равно 23, а остальные получаются добавлением 105.
(Здесь подразумевается, что параметры q, p, t, u, v, w — целые числа.)
Общая формулировка и алгоритм
В теории чисел теорему формулируют на языке систем линейных сравнений.
Пусть m₁, m₂, …, mₖ — натуральные числа, попарно взаимно простые (то есть НОД(mᵢ, mⱼ) = 1 для любых i ≠ j).
Пусть r₁, r₂, …, rₖ — произвольные целые числа (обычно rᵢ — остаток от деления на mᵢ). Тогда система сравнений:
имеет решение, и все решения сравнимы по модулю M = m₁⋅m₂⋅…⋅mₖ.
Один из стандартных алгоритмов таков (известны различные доказательства):
- Вычислить общий модуль:
M = m₁⋅m₂⋅…⋅mₖ - Вычислить частичные произведения для каждого i:
Mᵢ = M/mᵢ - Найти обратные элементы:
для каждого i найти число yᵢ такое, что Mᵢ⋅yᵢ ≡ 1 (mod mᵢ)
(Например, используя расширенный алгоритм Евклида.) - Найти решение:
x = (r₁⋅M₁⋅y₁ + r₂⋅M₂⋅y₂ + … + rₖ⋅Mₖ⋅yₖ) (mod M)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
M₁⋅y₁ ≡ 1 (mod 3)
35⋅y₁ ≡ 1 (mod 3)
y₁ = 2
M₂⋅y₂ ≡ 1 (mod 5)
21⋅y₂ ≡ 1 (mod 5)
y₂ = 1
M₃⋅y₃ ≡ 1 (mod 7)
15⋅y₃ ≡ 1 (mod 7)
y₃ = 1
Тогда: x ≡ 233 (mod 105), 233 = 105⋅2 + 23, значит x ≡ 23 (mod 105).
Как видите, все способы приводят к одному и тому же результату — просто разными траекториями.