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

Обновлено: 3 октября, 2026

Решает систему сравнений с помощью китайской теоремы об остатках. Введите остатки и попарно взаимно простые модули, чтобы получить наименьшее неотрицательное решение.

Решение по китайской теореме об остатках

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

Формула

\[ x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \\[1.5em] N = n_1 \cdot n_2 \cdots n_k, \quad N_i = \frac{N}{n_i}, \quad y_i \equiv N_i^{-1} \pmod{n_i} \\[1.5em] x \equiv \sum_{i=1}^{k} a_i \, N_i \, y_i \pmod{N} \]

Где:

\(a_i\) — остатки (значения, которым должно быть сравнимо \(x\))
\(n_i\) — модули; они должны быть попарно взаимно простыми (их наибольший общий делитель равен 1 для любой пары)
\(N\) — произведение всех модулей; при взаимно простых модулях оно равно их наименьшему общему кратному
\(N_i\) — произведение всех модулей, кроме \(n_i\)
\(y_i\) — обратный элемент к \(N_i\) по модулю \(n_i\), то есть число, для которого \(N_i y_i \equiv 1 \pmod{n_i}\)
\(x\) — единственное решение по модулю \(N\)

Теорема утверждает, что если модули попарно взаимно просты, система имеет ровно одно решение в диапазоне \(0 \le x < N\). Формула строит это решение, комбинируя каждый остаток с обратным элементом соответствующего частичного произведения.

Китайская теорема об остатках — пример вычисления

Пример: найти \(x\), такое что \(x \equiv 2 \pmod{3}\) и \(x \equiv 3 \pmod{5}\) — это значения по умолчанию в калькуляторе.

\[ N = 3 \times 5 = 15 \]

\[ N_1 = \frac{15}{3} = 5, \quad y_1 = 2 \; (\text{так как } 5 \cdot 2 = 10 \equiv 1 \pmod{3}) \]

\[ N_2 = \frac{15}{5} = 3, \quad y_2 = 2 \; (\text{так как } 3 \cdot 2 = 6 \equiv 1 \pmod{5}) \]

\[ x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15} \equiv 20 + 18 = 38 \equiv 8 \pmod{15} \]

Результат: \(x = 8\) по модулю \(15\). Действительно, \(8 \div 3 = 2\) с остатком \(2\) и \(8 \div 5 = 1\) с остатком \(3\), так что оба сравнения выполняются. Следующее решение — \(8 + 15 = 23\), затем \(38\) и так далее.

Как пользоваться калькулятором

Введите количество сравнений (не менее 2). Дополнительные пары «остаток — модуль» появятся автоматически.
Для первого сравнения введите остаток в поле остаток 1 (\(a_1\)), а модуль — в поле модуль 1 (\(n_1\)).
Повторите то же для остатка 2 / модуля 2 и любых дополнительных пар.
Прочитайте наименьшее неотрицательное решение \(x\) и модуль (НОК модулей) \(N\). Каждое число вида \(x + kN\) (\(k = 0, 1, 2, \dots\)) также удовлетворяет системе.

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

Китайская теорема об остатках (КТО) — классический результат теории чисел, впервые описанный китайским математиком Сунь-цзы примерно в III–V веках н. э. Она отвечает на вопрос: если известны несколько делителей и остатки от деления неизвестного числа на каждый из них, можно ли восстановить это число? Теорема утверждает, что да — при условии, что модули попарно взаимно просты, — и что ответ единственен в диапазоне длиной, равной произведению всех модулей.

Наглядный пример: если в корзине \(x\) яиц, и при счёте по 3 остаётся 2, а при счёте по 5 остаётся 3, то \(x \equiv 2 \pmod{3}\) и \(x \equiv 3 \pmod{5}\). КТО однозначно определяет \(x\) по модулю 15 — в данном случае \(x = 8, 23, 38, \dots\)

Теорема важна потому, что показывает: система из многих небольших сравнений эквивалентна одному сравнению с большим модулем. Это позволяет заменить арифметику с огромным модулем параллельной арифметикой с несколькими малыми удобными модулями, а затем объединить результаты. Шаг объединения использует обратные элементы по модулю, которые можно вычислить отдельно с помощью калькулятора «Обратный элемент по модулю»; обратные элементы такого рода связаны также с малой теоремой Ферма и теоремой Эйлера.

Интерпретация результата

Калькулятор возвращает наименьшее неотрицательное решение \(x\) и объединённый модуль \(N\). Полное множество решений — это \(x, x + N, x + 2N, \dots\), а если в вашей задаче допустимы отрицательные ответы, подойдут и \(x - N\), и ещё меньшие значения. Поскольку решение единственно по модулю \(N\), два разных набора входных данных, дающих одинаковое \(x \pmod{N}\), описывают одну и ту же систему.

Допущения и ограничения

Требуются попарно взаимно простые модули. Каждая пара модулей не должна иметь общих делителей больше 1; иначе калькулятор сообщит об ошибке. Если, например, два модуля равны 4 и 6 (оба делятся на 2), система может вовсе не иметь решений или иметь несколько решений по модулю их НОК.
Согласованность системы. При взаимно простых модулях теорема всегда даёт решение — в этом и сила КТО. Конфликты между сравнениями могут возникнуть только при нарушении условия взаимной простоты.
Остатки могут превышать модуль. Ввод вроде \(a = 7, n = 5\) трактуется как \(7 \equiv 2 \pmod 5\); калькулятор автоматически приводит итоговый ответ по модулю \(N\).
Модули должны быть положительными целыми числами. Значения 0 и отрицательные числа отклоняются.
Большие системы. Поскольку \(N\) — произведение всех модулей, оно растёт очень быстро. При большом числе модулей задействованные числа могут выйти за пределы диапазона, где стандартная арифметика с плавающей запятой точна.

Где применяется КТО

За пределами чистой теории чисел КТО является рабочим инструментом во многих областях. В криптографии она ускоряет расшифровку RSA, вычисляя результат отдельно по каждому простому делителю и затем объединяя их; она также лежит в основе пороговых схем, таких как разделение секрета Шамира. В информатике она делает возможными системы остаточных классов, выполняющие сложение и умножение параллельно с малыми модулями, а также встречается в хешировании, планировании и календарных расчётах — в классических задачах «о подсчёте солдат по рядам», которые и породили работу Сунь-цзы.

Часто задаваемые вопросы

Как решить систему по КТО вручную без формулы?

Для двух сравнений можно использовать подстановку: возьмите первое, тогда x = a₁ + k·n₁ для целых \(k\). Подставьте во второе сравнение \(a_1 + k n_1 \equiv a_2 \pmod{n_2}\) и решите его относительно \(k\), найдя обратный элемент к \(n_1\) по модулю \(n_2\). Затем подставьте \(k\) обратно и получите \(x\), приведя результат по модулю \(n_1 n_2\). Этот метод последовательной подстановки работает для любого числа сравнений — они решаются по два за раз.

Что будет, если модули не попарно взаимно простые?

Когда два модуля имеют общий делитель, система может оказаться несовместной и не иметь решений вовсе. Решение существует, только если остатки согласованы: для каждой пары должно выполняться \(a_i \equiv a_j \pmod{\gcd(n_i, n_j)}\). Если они согласованы, решение по-прежнему единственно, но лишь по модулю наименьшего общего кратного модулей, а не их произведения. Требование взаимной простоты гарантирует, что решение существует всегда, — поэтому данный калькулятор отклоняет такие входные данные.

Почему решение единственно и как найти все остальные решения?

Единственность следует из того, что если два числа \(x\) и \(x'\) оба удовлетворяют системе, то их разность делится на каждый модуль, а значит, и на их произведение \(N\) (поскольку они взаимно просты). Поэтому \(x \equiv x' \pmod{N}\), то есть в диапазоне \(0 \le x < N\) существует ровно одно решение. Все остальные решения имеют вид \(x + kN\) для любого целого \(k\), включая отрицательные значения вроде \(x - N\), если ваша задача их допускает.

Могут ли остатки быть отрицательными или большими, чем модуль?

Да. Остаток, превышающий свой модуль, автоматически приводится — например, \(a = 7\) при \(n = 5\) — то же самое, что \(a = 2\). Работают и отрицательные остатки: \(x \equiv -1 \pmod{5}\) означает то же, что \(x \equiv 4 \pmod{5}\). Итоговый ответ всегда нормируется к наименьшему неотрицательному представителю в диапазоне \(0 \le x < N\).

Как найти обратный элемент по модулю вручную?

Используйте расширенный алгоритм Евклида: примените обычный алгоритм Евклида к \(N_i\) и \(n_i\), затем идите в обратном порядке, чтобы выразить \(\gcd = 1\) в виде \(uN_i + vn_i\). Коэффициент \(u\) удовлетворяет \(uN_i \equiv 1 \pmod{n_i}\), поэтому \(y_i = u \bmod n_i\). Для простого модуля \(p\) можно также воспользоваться малой теоремой Ферма: \(y_i \equiv N_i^{p-2} \pmod{p}\).

Какие типичные ошибки при использовании китайской теоремы об остатках?

Самые частые ошибки: использование модулей, не являющихся попарно взаимно простыми (например, 4 и 6, у которых общий делитель 2); перепутывание полей остатка и модуля при вводе данных; забывание о том, что ответ — это целый класс решений, а не одно число; ввод модуля 1, что формально допустимо, но не добавляет информации. Также проверяйте, что остатки соответствуют вашей задаче: \(x \equiv 2 \pmod{3}\) — это не то же самое, что \(x \equiv 3 \pmod{2}\).

Есть ли быстрый способ проверить ответ калькулятора?

Да — просто разделите ответ на каждый модуль и проверьте остатки. Если результат равен \(x\), убедитесь, что \(x \bmod n_i = a_i \bmod n_i\) для каждого сравнения в вашей системе. Вторая проверка: вычислите \(x \bmod N\) другим способом, например последовательной подстановкой, и убедитесь, что получается то же значение. Если обе проверки пройдены, решение верно, поскольку единственность по модулю \(N\) гарантирует, что в этом диапазоне другого ответа нет.