Китайская теорема об остатках
Содержание
Теорема
Утверждение: (Китайская теорема об остатках)
Для любого набора взаимно простых натуральных чисел $a_1, a_2, \ldots, a_n$ и целых неотрицательных чисел $r_1, r_2, \ldots, r_n$, таких что $r_i < a_i$, существует ровно одно целое число $x$, такое что $x \equiv r_1 \pmod{a_1},\ x\equiv r_2 \pmod{a_2},\ \ldots,\ x \equiv r_n \pmod{a_n}$ и $0 \le x < a_1 \cdot a_2 \cdot \ldots \cdot a_n$.
Единственность
Пусть числа $x_1$ и $x_2$ удовлетворяют китайской теореме об остатках. Тогда т.к. $x_1 \equiv r_1 \pmod{a_1}$ и $x_2 \equiv r_1 \pmod{a_1}$, то $x_1 - y_2$ делится на $a_1$. Аналогично $x_1 - y_2$ делится на $a_2$, $a_3$ и так далее до $a_n$. Но так как все $a_i$ взаимно просты, то значит $x_1 - y_1$ делится на их произведение. Но тогда или $x_1$, или $x_2$ не будет лежать в полуинтервале от 0 до $a_1 \cdot a_2 \cdot \ldots \cdot a_n$. Противоречие.
Существование
Заметим, что $r_1$ лежит в полуинтервале от 0 до $a_1$, $r_2$ — в полуинтервале от 0 до $a_2$ и так далее. Значит всего количество различных наборов чисел $r_1, r_2, \ldots r_n$ ровно $a_1 \cdot a_2 \cdot \ldots \cdot a_n$. Удивительно, но возможных значений $x$ тоже $a_1 \cdot a_2 \cdot \ldots \cdot a_n$. Причём для каждого $x$ есть не более одного набора остатков $r_1, r_2, \ldots r_n$, для которого выполнено условие китайской теоремы об остатках, а так же для каждого набора остатков есть не более одного $x$. А это значит, что есть взаимно однозначное соответствие между набором остатков и возможными значениями $x$, а значит китайская теорема об остатках доказана.
Алгоритм
Иногда бывает полезным для готового набора чисел $a_i$ и $r_i$ найти такой $x$, что он удовлетворяет условию китайской теоремы об остатках. Приведём алгоритм как это делать.
Алгоритм будет чем-то напоминать математическую индукцию — сначала мы научимся решать задачу для $n=2$, а потом научимся сводить большие $n$ к меньшим.
При $n=2$ нам надо найти такое число $x$, что $x \equiv r_1 \pmod{a_1}$ и $x \equiv r_2 \pmod{a_2}$. Другими словами это можно записать так: существуют такие натуральные числа $c_1$ и $c_2$, что $x = a_1 \cdot c_1 + r_1$ и $x = a_2 \cdot c_2 + r_2$. Тогда $a_1 \cdot c_2 - a_2 \cdot c_2 = r_2 - r_1$. Так как $gcd(a_1, a_2) = 1$, то мы можем применить Расширенный алгоритм Евклида и найти числа $c_1$ и $c_2$, такие что равенство выполнено. А с помощью этого можно найти число $x$.
При больших $n$ мы можем сделать следующее. Возьмём числа $a_1$ и $a_2$ и для них найдём такое число $y$, что $y \equiv r_1 \pmod{a_1}$ и $y \equiv r_2 \pmod{a_2}$ c помощью алгоритмы описанного в предыдущем абзаце. Теперь решим такую-же задачу, но $a_1$ и $a_2$ заменим на $a_1 \cdot a_2$, и $r_1$ и $r_2$ заменим на $y$. Другими словами, найдём такой $x$, что $x \equiv y \pmod{a_1 \cdot a_2}$, $x \equiv r_3 \pmod{a_3}$, $x \equiv r_4 \pmod{a_4}$ и т.д. (теперь сравнений на одно меньше). Заметим, что ответ на такую задачу подойдёт как ответ на начальную задачу, потому что для $i > 2$ $x \equiv r_i \pmod{a_i}$ по определению, а так как $x \equiv y \pmod{a_1 \cdot a_2}$, $y \equiv r_1 \pmod{a_1}$ и $y \equiv r_2 \pmod{a_2}$, то $x \equiv r_1 \pmod{a_1}$ и $x \equiv r_2 \pmod{a_2}$. Так мы научились сводить задачу к меньшей.
Утверждение:
Время работы описанного выше алгоритма составляет $O(n \log C)$, где $C$ — ограничение на произведение всех $a_i$.
Доказательство остаётся читателю в качестве упражнения
Автор конспекта: Филипп Грибов
По всем вопросам пишите в telegram @grphil