Задания № 25, 26 · ЕГЭ

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

Как решить систему сравнений с попарно взаимно простыми модулями

3 мин чтенияСложность: Обновлено 29 сентября 2026

Китайская теорема об остатках утверждает: если модули системы сравнений попарно взаимно просты, то система имеет решение, причём все решения дают один и тот же остаток по модулю произведения модулей.

Теорема о системе сравнений \(x \equiv a_1 \pmod{m_1},\ x \equiv a_2 \pmod{m_2},\ldots,\ x \equiv a_k \pmod{m_k}\), где любые два модуля взаимно просты: \(\operatorname{НОД}(m_i,m_j)=1\) при \(i\ne j\). Такая система имеет единственное решение по модулю \(M=m_1m_2\cdots m_k\).

Формула решения

Для вычисления решения положим \(M=m_1m_2\cdots m_k\) и \(M_i=\frac{M}{m_i}\). Для каждого \(i\) найдём число \(y_i\), обратное к \(M_i\) по модулю \(m_i\): \(M_i y_i\equiv1\pmod{m_i}\). Тогда решение имеет вид:

\[x\equiv\sum_{i=1}^{k} a_i M_i y_i\pmod{M}\]

Обратное число можно найти с помощью расширенного алгоритма Евклида. Для понимания самих сравнений сначала полезно повторить арифметику по модулю, а условие взаимной простоты проверять через наибольший общий делитель.

№

Пример

Решим систему \(x\equiv2\pmod3\), \(x\equiv3\pmod5\). Здесь \(M=15\), \(M_1=5\), \(M_2=3\). Обратное к \(5\) по модулю \(3\) равно \(2\), а обратное к \(3\) по модулю \(5\) равно \(2\). Поэтому \(x\equiv2\cdot5\cdot2+3\cdot3\cdot2=38\equiv8\pmod{15}\). Ответ: \(x=8+15t\), где \(t\) — целое число.

Не путайте

Попарная взаимная простота означает, что НОД каждой пары модулей равен \(1\). Если модули не взаимно просты, решение может отсутствовать или быть не единственным по модулю их произведения; тогда применяют обобщённую теорему и проверяют совместимость остатков.

Проверь себя

Каков общий модуль решений системы \(x\equiv1\pmod4\) и \(x\equiv2\pmod7\)?

Главное за минуту

Главное

При попарно взаимно простых модулях система сравнений всегда разрешима.
Все решения отличаются на произведение модулей \(M\).
Для вычисления ответа используют обратные элементы, которые можно найти расширенным алгоритмом Евклида.