Что такое китайская теорема об остатках?
Китайская теорема об остатках (КТО) — это классический результат теории чисел. Она утверждает: если задана система сравнений \(x \equiv a_1 \pmod{m_1}\), \(x \equiv a_2 \pmod{m_2}\), … и все модули попарно взаимно просты (не имеют общих делителей), то существует единственное решение \(x\) по модулю \(M = m_1 \cdot m_2 \cdot \ldots\). Этот калькулятор находит наименьшее неотрицательное такое решение.
Как пользоваться калькулятором
Введите каждый остаток \(a_i\) вместе с его модулем \(m_i\). Можно решить систему из двух или трёх сравнений — если вам нужны только два, оставьте третий модуль пустым. Калькулятор проверяет, что модули попарно взаимно просты, а затем выдаёт \(x\) и общий модуль \(M\). Любое значение вида \(x + Mk\) (для любого целого \(k\)) также является решением.
Разбор формулы
Пусть \(M = \prod m_i\). Для каждого сравнения определим \(M_i = M / m_i\) и \(y_i = M_i^{-1} \bmod m_i\) (обратный элемент по модулю, который вычисляется расширенным алгоритмом Евклида). Тогда решение — это взвешенная сумма $$x \equiv \sum_{i} a_i\,M_i\,y_i \pmod{M}.$$ Поскольку \(M_i\) делится на все модули, кроме \(m_i\), каждое слагаемое даёт нужный остаток только для своего сравнения.
Разбор примера
Решим \(x \equiv 2 \pmod{3}\) и \(x \equiv 1 \pmod{4}\). Здесь \(M = 3 \cdot 4 = 12\). \(M_1 = 4\), и \(4 \equiv 1 \pmod{3}\), поэтому \(y_1 = 1\); \(M_2 = 3\), и \(3 \equiv 3 \pmod{4}\), поэтому \(y_2 = 3\) (так как \(3 \cdot 3 = 9 \equiv 1\)). Тогда $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}.$$ 5 (mod 12). Проверка: \(5 \bmod 3 = 2\) ✓ и \(5 \bmod 4 = 1\) ✓.
Частые вопросы
Почему модули должны быть взаимно простыми? Если у двух модулей есть общий делитель, система может вообще не иметь решений или иметь несколько решений по модулю их НОК, и тогда стандартная формула КТО уже не работает.
Что значит «наименьшее неотрицательное решение»? Все решения отличаются на кратные \(M\); калькулятор показывает то из них, которое лежит в диапазоне от 0 до \(M-1\).
Можно ли вводить отрицательные остатки? Да. Перед решением они приводятся по каждому модулю \(m_i\) к диапазону от 0 до \(m_i-1\).
