Как решить систему сравнений: китайская теорема об остатках

Дано: система из трёх сравнений $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$. Найти: наименьшее натуральное решение и общий вид всех решений.

Модули 3, 5 и 7 попарно взаимно просты, поэтому работает китайская теорема об остатках: решение существует при любых остатках и единственно по модулю произведения $M = 105$. Ответ: $x \equiv 23 \pmod{105}$, наименьшее натуральное решение равно 23. Калькулятор сверху собирает такое же решение для любых остатков и модулей и показывает на числовой оси, где ряды сравнений пересекаются.

Решение по шагам

Дано. Остатки $r_1 = 2$, $r_2 = 3$, $r_3 = 2$ по модулям $m_1 = 3$, $m_2 = 5$, $m_3 = 7$.

Найти. Все целые $x$, дающие эти остатки одновременно.

Шаг 1. Проверяем взаимную простоту модулей. Условие теоремы: модули взаимно просты попарно, то есть у каждой пары НОД равен единице. Считаем все три пары: $\gcd(3, 5) = 1$, $\gcd(3, 7) = 1$, $\gcd(5, 7) = 1$. Условие выполнено, значит решение заведомо существует, и остаётся его собрать. Если НОД пары считается не в уме, подойдёт лестница Евклида из задачи как найти НОД двух чисел.

Шаг 2. Считаем произведение модулей. Это модуль будущего ответа:

$$M = m_1 m_2 m_3 = 3 \cdot 5 \cdot 7 = 105.$$

Шаг 3. Для каждого сравнения берём частное произведение. Частное произведение $M_i$ получается вычёркиванием своего модуля: оно делится на все остальные модули и не делится только на свой.

$$M_1 = \frac{105}{3} = 35, \qquad M_2 = \frac{105}{5} = 21, \qquad M_3 = \frac{105}{7} = 15.$$

Шаг 4. Ищем обратные элементы. Для каждого $i$ нужен такой множитель $y_i$, что $M_i y_i \equiv 1 \pmod{m_i}$. Сначала приводим $M_i$ по своему модулю, потом решаем маленькое сравнение. Здесь $35 \equiv 2 \pmod 3$, и сравнение $2y \equiv 1 \pmod 3$ даёт $y_1 = 2$; далее $21 \equiv 1 \pmod 5$ и $15 \equiv 1 \pmod 7$, поэтому $y_2 = y_3 = 1$. Для модулей побольше этот шаг делается расширенным алгоритмом Евклида, он разобран в задаче как найти обратное по модулю.

Все заготовки удобно свести в таблицу и дальше просто перемножать по строкам:

Шаг 5. Складываем слагаемые. Каждое слагаемое отвечает ровно за своё сравнение и не мешает остальным:

$$x_0 = 140 + 63 + 30 = 233.$$

Шаг 6. Сокращаем сумму по модулю $M$. Сумма 233 больше 105, поэтому её приводят к промежутку от 0 до 104: $233 = 2 \cdot 105 + 23$, остаток равен 23. Получаем $x \equiv 23 \pmod{105}$, то есть $x = 23 + 105k$, а наименьшее натуральное решение равно 23.

Проверка. Подставляем 23 в каждое сравнение: $23 = 3 \cdot 7 + 2$, остаток 2; $23 = 5 \cdot 4 + 3$, остаток 3; $23 = 7 \cdot 3 + 2$, остаток 2. Все три условия выполнены. Следующие решения получаются прибавлением периода: 128, 233, 338.

Формула и откуда она берётся

Общая запись китайской теоремы об остатках для попарно взаимно простых модулей выглядит так:

$$x \equiv \sum_{i=1}^{n} r_i M_i y_i \pmod{M}, \qquad M = \prod_{i=1}^{n} m_i, \qquad M_i = \frac{M}{m_i}, \qquad M_i y_i \equiv 1 \pmod{m_i}.$$

Смысл конструкции проще, чем запись. Слагаемое $r_i M_i y_i$ работает как выключатель: по всем чужим модулям оно равно нулю, потому что $M_i$ делится на каждый из них, а по своему модулю $m_i$ произведение $M_i y_i$ равно единице, и остаётся ровно нужный остаток $r_i$. Сумма таких слагаемых по модулю $m_1$ даёт $r_1$, по модулю $m_2$ даёт $r_2$ и так далее.

Обратный элемент $y_i$ существует именно потому, что модули взаимно просты: $M_i$ составлено из чужих модулей, каждый из которых не имеет с $m_i$ общих делителей, значит и $\gcd(M_i, m_i) = 1$. Это та же ситуация, что в обычном линейном сравнении с единичным НОД, разобранном в задаче как решить сравнение по модулю.

Единственность ответа по модулю $M$ доказывается в одну строку. Если два числа $x$ и $x'$ дают одинаковые остатки по всем модулям, их разность делится на каждый $m_i$, а для попарно взаимно простых модулей это значит, что разность делится на их произведение. Поэтому решений ровно один класс вычетов по модулю 105, а не три отдельных числа.

Второй способ: последовательная подстановка

Таблица с обратными элементами нужна не всегда. Систему можно решать по одному сравнению, подставляя общий вид решения в следующее. Начинаем с первого: $x = 2 + 3t$, где $t$ целое.

Подставляем во второе сравнение: $2 + 3t \equiv 3 \pmod 5$, то есть $3t \equiv 1 \pmod 5$. Обратный к тройке по модулю 5 равен двойке, поэтому $t \equiv 2 \pmod 5$ и $t = 2 + 5s$. Отсюда $x = 2 + 3(2 + 5s) = 8 + 15s$: два первых сравнения уже свёрнуты в одно по модулю 15.

Подставляем в третье: $8 + 15s \equiv 2 \pmod 7$. По модулю семь $8 \equiv 1$ и $15 \equiv 1$, значит $1 + s \equiv 2 \pmod 7$, откуда $s \equiv 1 \pmod 7$ и $s = 1 + 7u$. Итог: $x = 8 + 15(1 + 7u) = 23 + 105u$, тот же ответ.

Какой способ выбрать, зависит от задачи. Формула КТО удобна, когда одна и та же система решается многократно с разными остатками: частные произведения и обратные элементы считаются один раз. Последовательная подстановка выгоднее при решении руками и при большом числе сравнений, потому что все промежуточные числа остаются маленькими.

Когда модули не взаимно просты

Условие попарной взаимной простоты в теореме не формальность, но и не приговор. Если у пары модулей есть общий делитель $d = \gcd(m_i, m_j)$, система разрешима тогда и только тогда, когда остатки согласованы по этому делителю: $r_i \equiv r_j \pmod d$. Проверять надо каждую пару.

Пример согласованной системы: $x \equiv 1 \pmod 4$ и $x \equiv 3 \pmod 6$. Здесь $d = \gcd(4, 6) = 2$, оба остатка нечётны, то есть дают по модулю 2 одно и то же. Решение существует и равно $x \equiv 9 \pmod{12}$, причём модуль ответа - это НОК модулей 12, а не их произведение 24.

Пример противоречивой системы: $x \equiv 1 \pmod 4$ и $x \equiv 2 \pmod 6$. Первое требует нечётного $x$, второе чётного, согласования по двойке нет, решений не существует. В калькуляторе сверху такая система видна сразу: ряды на числовой оси не пересекаются ни в одной вертикали, а поле с ответом показывает прочерк.

Частые ошибки

• Проверять взаимную простоту всех модулей сразу вместо попарной. У тройки 6, 10, 15 общий делитель равен единице, но попарно они не взаимно просты, и классическая формула КТО к ним неприменима.
• Искать обратный элемент не по тому модулю. Нужен обратный к $M_i$ по модулю $m_i$, а не по модулю $M$: по модулю 105 у числа 35 обратного вообще нет, ведь $\gcd(35, 105) = 35$.
• Забыть сократить сумму. Число 233 - верное решение, но не ответ: в ответе стоит наименьший неотрицательный вычет 23 либо общий вид $23 + 105k$.
• Перепутать остатки со своими частными произведениями. Каждое $r_i$ умножается только на своё $M_i$ и своё $y_i$; сдвиг на строку в таблице даёт правдоподобное, но неверное число.
• Написать ответ одним числом. Решение системы - это класс вычетов, и в нём бесконечно много чисел: 23, 128, 233 и так далее, а также отрицательные $-82$ и далее.
• Считать произведение модулей периодом, когда модули не взаимно просты. Период всегда равен НОК модулей: для 4 и 6 это 12, а не 24.

FAQ

Почему решение единственно по модулю произведения, а не по какому-то другому модулю? Разность двух решений делится на каждый модуль системы. Для попарно взаимно простых модулей отсюда следует делимость на произведение, поэтому все решения отличаются на кратное $M$ и образуют один класс вычетов.

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

Можно ли решить систему перебором? Да, и для маленьких модулей это законный способ: берём наибольший модуль, выписываем числа вида $2 + 7k$ и отбираем первое, подходящее остальным сравнениям. Перебор укладывается в $M / m_{\max}$ проверок, то есть в 15 штук для нашей системы, но при модулях в сотни тысяч он уже бесполезен.

Где китайская теорема об остатках применяется на практике? Главное применение - ускорение вычислений по составному модулю: расчёт по $m = pq$ разбивают на два расчёта по меньшим модулям и собирают обратно. Так устроена быстрая расшифровка в RSA, подробности - в задачах как сгенерировать ключи RSA и как быстро возвести в степень.

Коротко

1. Проверь попарную взаимную простоту модулей: $\gcd(3, 5) = \gcd(3, 7) = \gcd(5, 7) = 1$, условие теоремы выполнено.
2. Посчитай произведение $M = 105$ и частные произведения $M_1 = 35$, $M_2 = 21$, $M_3 = 15$.
3. Найди обратные элементы по своим модулям: $y_1 = 2$, $y_2 = 1$, $y_3 = 1$.
4. Сложи слагаемые $r_i M_i y_i$: $140 + 63 + 30 = 233$, и сократи сумму по модулю 105.
5. Ответ: $x \equiv 23 \pmod{105}$, наименьшее натуральное решение 23, общий вид $x = 23 + 105k$.