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

Эта статья написана для:

📐 Старшеклассников (9–11 классы), готовящихся к ЕГЭ, олимпиадам и углублённым задачам по математике
📚 Учащихся 7–8 классов, изучающих модульную арифметику и интересующихся дополнительными задачами
👨‍👩‍👧 Родителей школьников, помогающих детям с математикой и выбирающих учебные материалы или репетиторов
🏫 Учителей и репетиторов, подбирающих наглядные объяснения, примеры и задачи для уроков и занятий
🎓 Студентов и выпускников математических и технических специальностей
🔐 Интересующихся криптографией и её математическими основами

Ключевые выводы из статьи:

✅ Китайская теорема об остатках (КТО) гарантирует единственное решение системы сравнений по модулю при условии, что модули попарно взаимно просты — проверяйте это условие до начала вычислений.
✅ Для практических вычислений в Python с 2025 года используйте встроенную функцию pow(a, -1, m) вместо ручной реализации расширенного алгоритма Евклида — это сокращает код и снижает риск ошибок.
✅ В задачах олимпиадного программирования и криптографии RSA всегда применяйте алгоритм Гарнера: он позволяет избежать целочисленного переполнения при работе с большими числами.
✅ Если модули не взаимно просты, решение существует тогда и только тогда, когда выполнено условие совместимости для каждой пары: aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)).

💡 Если вы или ваш ребёнок готовитесь к ЕГЭ и хотите не просто заучить формулы, но и научиться применять теорию чисел на практике — ознакомьтесь с материалами по подготовке к ЕГЭ по математике: там вы найдёте структурированные учебные планы, разборы сложных тем и интерактивные задания, которые помогут систематизировать знания и уверенно сдать экзамен.

Формулировка теоремы

Пусть m₁, m₂, ..., mₖ — попарно взаимно простые числа. Тогда для любых целых a₁, a₂, ..., aₖ существует число x, такое что:

x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂) ⋮ x ≡ aₖ (mod mₖ)

Более того, решение x определено однозначно по модулю M, где M = m₁ · m₂ · ... · mₖ.

Условия применимости: взаимная простота модулей

Китайская теорема об остатках применима тогда и только тогда, когда модули m₁, m₂, ..., mₖ являются попарно взаимно простыми: для каждой пары i ≠ j выполняется НОД(mᵢ, mⱼ) = 1. Это не просто техническое условие — оно напрямую определяет, существует ли вообще однозначное решение системы.

Исторически теорема восходит к китайскому трактату Сунь-цзы «Сунь-цзы суань цзин» (III–V вв. н.э.), где описывалась задача нахождения числа по его остаткам от деления. Математически строгая формулировка была дана Карлом Фридрихом Гауссом в «Disquisitiones Arithmeticae» (1801).

Важно понимать: система линейных сравнений вида x ≡ aᵢ (mod mᵢ) — это в точности система линейных диофантовых уравнений, то есть система уравнений вида x = aᵢ + mᵢ·kᵢ, где kᵢ — целое. КТО утверждает, что при взаимно простых модулях такая система имеет ровно одно решение в каждом полном наборе остатков по произведению M.

Утверждение о существовании и единственности решения

При выполнении условия взаимной простоты модулей данная система имеет единственное решение по модулю M, где M = m₁ · m₂ · ... · mₖ. Это означает: среди всех целых чисел существует ровно одно число x в диапазоне 0 ≤ x < M, удовлетворяющее всем сравнениям одновременно. Любое другое решение отличается от него на кратное M.

Числовой пример «с первых строк»

Рассмотрим систему:

x ≡ 2 (mod 3) x ≡ 3 (mod 5)

Проверяем: НОД(3, 5) = 1 — условие выполнено. M = 3 · 5 = 15.

Перебор: числа, дающие остаток 2 при делении на 3: 2, 5, 8, 11, 14, ... Из них остаток 3 при делении на 5 даёт число 8.

Ответ: x ≡ 8 (mod 15). Проверка: 8 = 2·3 + 2 ✓; 8 = 1·5 + 3 ✓.

Доказательство

Представьте, что каждое из условий системы «фильтрует» числа по своему критерию. Поскольку модули не делят друг друга (попарно взаимно просты), их «фильтры» абсолютно независимы. Именно эта независимость позволяет «собрать» решение из независимых частей — и гарантирует, что такое решение ровно одно в пределах M.

Для простоты начнём с системы из двух уравнений:

x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂)

Поскольку m₁ и m₂ взаимно просты, существуют такие числа y₁ и y₂, что:

y₁·m₁ + y₂·m₂ = 1

Это следует из тождества Безу. Теперь определим число x:

x = a₁·y₂·m₂ + a₂·y₁·m₁

Проверим, удовлетворяет ли это число уравнениям:

По модулю m₁: x ≡ a₁·y₂·m₂ + a₂·y₁·m₁ ≡ a₁·(1 − y₁·m₁) + 0 ≡ a₁ (mod m₁)
По модулю m₂: x ≡ a₁·y₂·m₂ + a₂·y₁·m₁ ≡ 0 + a₂·(1 − y₂·m₂) ≡ a₂ (mod m₂)

Таким образом, x удовлетворяет обоим уравнениям. Подобные рассуждения обобщаются на систему из k уравнений.

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

Доказательство единственности

Предположим, что x и y — два решения системы. Тогда для каждого i: (x − y) ≡ 0 (mod mᵢ). Поскольку все mᵢ попарно взаимно просты, их произведение M делит (x − y). Значит, x ≡ y (mod M) — решение единственно по модулю M.

Разбор числового примера через шаги доказательства

Система: x ≡ 2 (mod 3), x ≡ 3 (mod 5). M = 15.

M₁ = 15/3 = 5; нужно 5⁻¹ mod 3: 5·2 = 10 ≡ 1 (mod 3), значит M₁⁻¹ = 2
M₂ = 15/5 = 3; нужно 3⁻¹ mod 5: 3·2 = 6 ≡ 1 (mod 5), значит M₂⁻¹ = 2
x = (2·5·2 + 3·3·2) mod 15 = (20 + 18) mod 15 = 38 mod 15 = 8 ✓

Конструктивный алгоритм восстановления числа (классический CRT)

Пошаговое описание алгоритма

Убедитесь, что все пары модулей взаимно просты: НОД(mᵢ, mⱼ) = 1 для всех i ≠ j.
Вычислите полное произведение: M = m₁ · m₂ · ... · mₖ.
Для каждого i вычислите частичное произведение: Mᵢ = M / mᵢ.
Для каждого i найдите обратный элемент: yᵢ = Mᵢ⁻¹ mod mᵢ (через расширенный алгоритм Евклида или pow(Mᵢ, -1, mᵢ) в Python).
Вычислите сумму: x = Σ (aᵢ · Mᵢ · yᵢ).
Редуцируйте результат: x = x mod M.
Проверьте: подставьте x в каждое сравнение исходной системы.

Пример с тремя модулями (ручное вычисление)

Система:

x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7)

Шаги:

Проверка: НОД(3,5) = НОД(3,7) = НОД(5,7) = 1 ✓
M = 3·5·7 = 105
M₁ = 35, M₂ = 21, M₃ = 15
y₁ = 35⁻¹ mod 3: 35 mod 3 = 2; 2⁻¹ mod 3 = 2 (т.к. 2·2 = 4 ≡ 1 mod 3)
y₂ = 21⁻¹ mod 5: 21 mod 5 = 1; 1⁻¹ mod 5 = 1
y₃ = 15⁻¹ mod 7: 15 mod 7 = 1; 1⁻¹ mod 7 = 1
x = (2·35·2 + 3·21·1 + 2·15·1) = 140 + 63 + 30 = 233
x = 233 mod 105 = 23

Проверка: 23 = 7·3 + 2 ✓; 23 = 4·5 + 3 ✓; 23 = 3·7 + 2 ✓.

Анализ временной сложности

Алгоритм классического CRT выполняется за O(k · log M), где k — количество сравнений, log M — оценка стоимости вычислений с числами порядка M. Основная стоимость — нахождение обратных элементов через алгоритм Евклида.

💬 Совет эксперта: При первом знакомстве с КТО не пытайтесь сразу заучивать формулу. Воспроизведите конструктивное доказательство вручную для системы из двух уравнений три раза подряд — это важнее, чем запомнить символы. Структура алгоритма станет интуитивно понятной, и вы сможете восстановить её на экзамене без опоры на память.

Расширенный алгоритм Евклида

Зачем нужен расширенный алгоритм Евклида

Ключевой шаг КТО — нахождение обратного элемента Mᵢ⁻¹ по модулю mᵢ. Это задача решения уравнения вида a·x ≡ 1 (mod m), что эквивалентно линейному диофантову уравнению a·x + m·y = 1. Расширенный алгоритм Евклида даёт коэффициенты Безу x и y за O(log(min(a, m))) шагов.

Алгоритм и коэффициенты Безу

Стандартный алгоритм Евклида находит НОД(a, m). Расширенная версия дополнительно отслеживает представление НОД в виде линейной комбинации:

gcd(a, m) = a·x + m·y

Если НОД(a, m) = 1, то a·x ≡ 1 (mod m), откуда a⁻¹ mod m = x mod m.

Числовой пример

Найдём 35⁻¹ mod 3:

35 = 11·3 + 2; 3 = 1·2 + 1; 2 = 2·1 + 0
Обратный ход: 1 = 3 − 1·2 = 3 − 1·(35 − 11·3) = 12·3 − 1·35
Значит, x = −1, то есть 35⁻¹ mod 3 = −1 mod 3 = 2

Граничный случай: НОД(a, m) ≠ 1

Если НОД(a, m) = d > 1, то уравнение a·x ≡ 1 (mod m) не имеет решений — обратный элемент не существует. В контексте КТО это означает нарушение условия попарной взаимной простоты модулей. Алгоритм должен возвращать ошибку или None.

Актуальная заметка (2026): В современном Python для нахождения обратного элемента рекомендуется встроенная функция pow(a, -1, m). Она автоматически вызывает исключение ValueError, если обратного не существует, что удобно для обработки граничных случаев.

Поиск обратного элемента: метод подходящих дробей

Что такое непрерывные дроби и подходящие дроби

Любое рациональное число a/m можно представить в виде непрерывной (цепной) дроби:

a/m = q₀ + 1 / (q₁ + 1 / (q₂ + 1 / (... + 1/qₙ)))

где коэффициенты q₀, q₁, q₂, ... находятся последовательным применением деления с остатком (ровно теми же шагами, что и алгоритм Евклида). Подходящие дроби — последовательные «приближения» к a/m, получаемые обрывом разложения на каждом шаге. Числители pᵢ и знаменатели qᵢ вычисляются по рекуррентным формулам:

p₋₁ = 1, p₀ = q₀, pᵢ = qᵢ · pᵢ₋₁ + pᵢ₋₂ q₋₁ = 0, q₀ = 1, qᵢ = qᵢ · qᵢ₋₁ + qᵢ₋₂

Теорема о связи подходящих дробей с обратным элементом

Пусть требуется найти a⁻¹ mod m. Рассмотрим разложение m/a в непрерывную дробь с подходящими дробями p₀/q₀, ..., pₙ/qₙ. Тогда выполняется тождество Безу:

a · qₙ₋₁ − m · pₙ₋₁ = (−1)ⁿ

Предпоследний знаменатель qₙ₋₁ даёт обратный элемент. При чётном n: a⁻¹ = qₙ₋₁. При нечётном n: a⁻¹ = m − qₙ₋₁.

Числовой пример: 35⁻¹ mod 3 через подходящие дроби

35 = 11·3 + 2 → q₀ = 11 3 = 1·2 + 1 → q₁ = 1 2 = 2·1 + 0 → q₂ = 2

1 = 3 − 1·2 = 3 − 1·(35 − 11·3) = 12·3 − 1·35 → 35·(−1) ≡ 1 (mod 3) → 35⁻¹ mod 3 = −1 mod 3 = 2

Итог: 35⁻¹ mod 3 = 2 — совпадает с результатом классического алгоритма Евклида. ✓

Числовой пример: 7⁻¹ mod 11 через подходящие дроби

11 = 1·7 + 4 → q₀ = 1 7 = 1·4 + 3 → q₁ = 1 4 = 1·3 + 1 → q₂ = 1 3 = 3·1 + 0 → q₃ = 3

q₋₁ = 0 q₀ = 1 q₁ = 1·1 + 0 = 1 q₂ = 1·1 + 1 = 2 q₃ = 3·2 + 1 = 7 (= m)

Предпоследний знаменатель q₂ = 2. n = 3 (нечётное) → a⁻¹ = 11 − 2 = 9. Проверка: 7·9 = 63 ≡ 8·7+7 → 7·9 mod 11 = 63 mod 11 = 8+1=1 ✓.

Метод подходящих дробей эквивалентен расширенному алгоритму Евклида по числу шагов, но даёт более наглядную таблицу для ручного счёта на экзамене или олимпиаде. Для программной реализации предпочтительнее pow(a, -1, m).

Алгоритм Гарнера

В чём отличие от классического CRT

Классический CRT требует вычисления полного произведения M = m₁·...·mₖ, которое при большом k или больших mᵢ становится гигантским числом. Алгоритм Гарнера использует смешанное радиксное представление, позволяя работать только с числами порядка mᵢ на каждом шаге, что полностью исключает целочисленное переполнение.

Формула Гарнера: построение коэффициентов

Число x представляется в виде:

x = r₁ + r₂·m₁ + r₃·m₁·m₂ + ... + rₖ·m₁·m₂·...·mₖ₋₁

Коэффициенты rᵢ находятся итеративно:

r₁ = a₁
r₂ = (a₂ − r₁) · m₁⁻¹ mod m₂
r₃ = ((a₃ − r₁) · m₁⁻¹ − r₂) · m₂⁻¹ mod m₃
и так далее...

Пример через алгоритм Гарнера (та же система)

Система: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).

r = [2, 3, 2] (начальные остатки) i=1: r[1] = (3 - 2) * (3⁻¹ mod 5) mod 5 3⁻¹ mod 5 = 2 (т.к. 3·2=6≡1 mod 5) r[1] = 1 * 2 mod 5 = 2 i=2: j=0: r[2] = (2 - 2) * (3⁻¹ mod 7) mod 7 = 0 j=1: r[2] = (0 - 2) * (5⁻¹ mod 7) mod 7 5⁻¹ mod 7 = 3 (т.к. 5·3=15≡1 mod 7) r[2] = (-2) * 3 mod 7 = -6 mod 7 = 1 Восстановление: x = 2 + 2·3 + 1·3·5 = 2 + 6 + 15 = 23 ✓

Когда предпочтителен алгоритм Гарнера

Большое количество модулей k (например, k ≥ 5)
Ограниченная разрядность регистров (64-битные целые)
Вычисления в задачах олимпиадного программирования и RSA
Работа с длинной арифметикой (BigInt)

Работа с отрицательными числами в алгоритме Гарнера

В спортивном программировании и криптографии ответ нередко является отрицательным целым числом. Алгоритм Гарнера в базовом варианте всегда возвращает x ∈ [0, M − 1]. Чтобы восстановить отрицательное значение, применяется следующее правило:

📐 Правило восстановления знака

Если результат x, полученный алгоритмом Гарнера, удовлетворяет условию x > M / 2, то истинное значение числа равно x − M (отрицательное). В противном случае x уже является правильным неотрицательным значением.

if x > M // 2: x = x - M # восстанавливаем отрицательное значение

Практический пример: восстановление x = −7

Возьмём модули 3, 5, 7 (M = 105). Остатки числа −7:

−7 mod 3 = 2 (т.к. −7 = −3·3 + 2) −7 mod 5 = 3 (т.к. −7 = −2·5 + 3) −7 mod 7 = 0 (т.к. −7 = −1·7 + 0)

Алгоритм Гарнера вернёт x = 98. Проверка: 98 > 105/2 = 52,5 → x = 98 − 105 = −7 ✓.

Сравнительная таблица: классический CRT vs. алгоритм Гарнера

Критерий	Классический CRT	Алгоритм Гарнера
Промежуточные числа	Порядка M (гигантские)	Порядка mᵢ (малые)
Риск переполнения	Высокий при больших k	Минимальный
Скорость (малые числа)	Быстро	Сопоставимо
Применимость в RSA	Требует BigInt	Предпочтителен
Олимпиадное программирование	Подходит для малых k	Стандарт для больших k
Отрицательные числа	Нормализация mod M	Сравнение с M/2
Простота реализации	Выше	Чуть сложнее

Реализация алгоритма Гарнера

Классический CRT на Python

def extended_gcd(a, b): """Расширенный алгоритм Евклида. Возвращает (gcd, x, y) такие что a*x + b*y = gcd(a,b).""" if b == 0: return a, 1, 0 g, x1, y1 = extended_gcd(b, a % b) return g, y1, x1 - (a // b) * y1 def mod_inverse(a, m): """Обратный элемент a^(-1) mod m через расширенный алгоритм Евклида.""" g, x, _ = extended_gcd(a % m, m) if g != 1: raise ValueError(f"Обратного элемента не существует: gcd({a},{m})={g}") return x % m def crt_classic(remainders, moduli): """ Классический алгоритм КТО. remainders[i] -- остаток по moduli[i]. Возвращает минимальное неотрицательное решение. """ M = 1 for m in moduli: M *= m x = 0 for a, m in zip(remainders, moduli): Mi = M // m yi = mod_inverse(Mi, m) x += a * Mi * yi return x % M # Пример использования remainders = [2, 3, 2] moduli = [3, 5, 7] result = crt_classic(remainders, moduli) print(f"x = {result}") # Ожидается: x = 23 # Проверка for a, m in zip(remainders, moduli): assert result % m == a, f"Ошибка: {result} % {m} != {a}" print("Все проверки пройдены.")

Алгоритм Гарнера на Python

def garner(remainders, moduli): """ Алгоритм Гарнера для решения системы линейных сравнений. remainders: список остатков [a1, a2, ..., ak] moduli: список попарно взаимно простых модулей [m1, m2, ..., mk] Возвращает минимальное неотрицательное решение x. """ k = len(moduli) combined = [[0] * k for _ in range(k)] for i in range(k): for j in range(i): combined[i][j] = pow(moduli[j], -1, moduli[i]) r = list(remainders) for i in range(1, k): for j in range(i): r[i] = (r[i] - r[j]) * combined[i][j] % moduli[i] x = r[0] prefix_product = 1 for i in range(1, k): prefix_product *= moduli[i - 1] x += r[i] * prefix_product M = 1 for m in moduli: M *= m return x % M def garner_signed(remainders, moduli): """ Алгоритм Гарнера с поддержкой отрицательных чисел. Если результат x > M/2, возвращает x - M (отрицательное значение). """ M = 1 for m in moduli: M *= m x = garner(remainders, moduli) if x > M // 2: x -= M return x # --- Пример использования --- remainders = [2, 3, 2] moduli = [3, 5, 7] result = garner(remainders, moduli) print(f"x = {result}") # Ожидается: x = 23 # Пример с отрицательным числом: x = -1 # x = -1 ≡ 2 (mod 3), ≡ 4 (mod 5), ≡ 6 (mod 7) neg_remainders = [2, 4, 6] neg_result = garner_signed(neg_remainders, moduli) print(f"x (signed) = {neg_result}") # Ожидается: -1 # --- Проверка корректности --- for a, m in zip(remainders, moduli): assert result % m == a, f"Ошибка: {result} % {m} != {a}" print("Все проверки пройдены.")

Реализация на C++

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll extgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll x1, y1; ll g = extgcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return g; } ll modinv(ll a, ll m) { ll x, y; ll g = extgcd(a % m, m, x, y); if (g != 1) throw runtime_error("Обратного не существует"); return (x % m + m) % m; } ll garner(vector<ll> remainders, vector<ll> moduli) { int k = moduli.size(); vector<ll> r(remainders); for (int i = 1; i < k; i++) { for (int j = 0; j < i; j++) { r[i] = (r[i] - r[j]) % moduli[i]; r[i] = (r[i] * modinv(moduli[j], moduli[i])) % moduli[i]; if (r[i] < 0) r[i] += moduli[i]; } } ll x = r[0]; ll prefix = 1; for (int i = 1; i < k; i++) { prefix *= moduli[i - 1]; x += r[i] * prefix; } return x; } ll garner_signed(vector<ll> remainders, vector<ll> moduli) { ll M = 1; for (ll m : moduli) M *= m; ll x = garner(remainders, moduli); if (x > M / 2) x -= M; return x; } int main() { vector<ll> remainders = {2, 3, 2}; vector<ll> moduli = {3, 5, 7}; ll result = garner(remainders, moduli); cout << "x = " << result << endl; // Ожидается: 23 vector<ll> neg_rem = {2, 4, 6}; ll neg_result = garner_signed(neg_rem, moduli); cout << "x (signed) = " << neg_result << endl; // Ожидается: -1 for (int i = 0; i < (int)moduli.size(); i++) { assert(result % moduli[i] == remainders[i]); } cout << "Все проверки пройдены." << endl; return 0; }

Длинная арифметика: Java BigInteger

В Java, в отличие от Python, встроенные целые числа ограничены 64 битами. Для работы с произведением M = m₁·...·mₖ, которое может превышать Long.MAX_VALUE, используется класс BigInteger.

import java.math.BigInteger; import java.util.List; public class CRT { public static BigInteger crt(List<BigInteger> remainders, List<BigInteger> moduli) { BigInteger M = BigInteger.ONE; for (BigInteger m : moduli) M = M.multiply(m); BigInteger x = BigInteger.ZERO; for (int i = 0; i < moduli.size(); i++) { BigInteger Mi = M.divide(moduli.get(i)); BigInteger inv = Mi.modInverse(moduli.get(i)); x = x.add(remainders.get(i).multiply(Mi).multiply(inv)); } return x.mod(M); } public static BigInteger crtSigned(List<BigInteger> remainders, List<BigInteger> moduli) { BigInteger M = BigInteger.ONE; for (BigInteger m : moduli) M = M.multiply(m); BigInteger x = crt(remainders, moduli); if (x.compareTo(M.divide(BigInteger.TWO)) > 0) { x = x.subtract(M); } return x; } public static void main(String[] args) { List<BigInteger> rem = List.of( BigInteger.valueOf(2), BigInteger.valueOf(3), BigInteger.valueOf(2) ); List<BigInteger> mod = List.of( BigInteger.valueOf(3), BigInteger.valueOf(5), BigInteger.valueOf(7) ); System.out.println("x = " + crt(rem, mod)); // Ожидается: 23 System.out.println("x (signed) = " + crtSigned(rem, mod)); } }

Зачем использовать BigInteger в Java? Метод BigInteger.modInverse(m) автоматически реализует расширенный алгоритм Евклида и бросает ArithmeticException, если обратного не существует — аналогично pow(a, -1, m) в Python. Это делает код лаконичным и безопасным при работе с RSA-ключами размером 2048+ бит.

Обработка граничных случаев

Несовместимые остатки: при несовместимой системе функция modinv вернёт корректное значение, но итоговый x не пройдёт проверку. Всегда выполняйте обратную подстановку.
Модуль равен 1: любое целое число ≡ 0 (mod 1) — такое сравнение не несёт информации и может быть отброшено.
k = 1: единственное сравнение x ≡ a₁ (mod m₁) — решение тривиально: x = a₁.
Отрицательные остатки в C++: операция % может давать отрицательный результат. Нормализуйте: r = ((r % m) + m) % m.

Когда модули не взаимно просты: обобщение и обработка конфликтов

Условие совместимости при НОД(mᵢ, mⱼ) > 1

Если НОД(mᵢ, mⱼ) = d > 1, система может быть совместима только при выполнении условия:

aᵢ ≡ aⱼ (mod d)

Если это условие нарушено хотя бы для одной пары, система не имеет решений.

Алгоритм сведения к взаимно простому случаю

Начать с первого уравнения системы.
Для каждого следующего уравнения x ≡ aᵢ (mod mᵢ) «слить» его с текущим x ≡ a (mod m).
Вычислить d = НОД(m, mᵢ). Проверить: (aᵢ − a) делится на d. Если нет — система несовместима.
Новый модуль: lcm(m, mᵢ) = m·mᵢ / d. Новый остаток вычисляется через решение уравнения слияния.
Повторить для всех уравнений.

Пример совместимой системы с не взаимно простыми модулями

x ≡ 2 (mod 4) x ≡ 6 (mod 10)

НОД(4, 10) = 2. Проверка: 6 − 2 = 4, делится на 2 ✓. Система совместима. Решение: x ≡ 6 (mod 20). Проверка: 6 mod 4 = 2 ✓; 6 mod 10 = 6 ✓.

Пример несовместимой системы

x ≡ 1 (mod 4) x ≡ 4 (mod 6)

НОД(4, 6) = 2. Проверка: 4 − 1 = 3, не делится на 2 ✗. Система не имеет решений.

В коде это обнаруживается на этапе проверки делимости при итеративном слиянии — функция должна возвращать None или бросать исключение.

💬 Совет эксперта: На олимпиадах задачи с невзаимно простыми модулями встречаются именно как «ловушки». Первым делом проверяйте попарное НОД всех модулей — это занимает O(k²·log(max m)) и спасает от неверного ответа. Автоматизируйте эту проверку в своём шаблонном коде.

Разбор нестандартных задач: диофантовы уравнения и ребусы

Как связаны системы линейных диофантовых уравнений и КТО

Система линейных сравнений x ≡ aᵢ (mod mᵢ) в точности эквивалентна системе линейных диофантовых уравнений:

x = a₁ + m₁·k₁ x = a₂ + m₂·k₂ ⋮ x = aₖ + mₖ·kₖ

где k₁, k₂, ..., kₖ — неизвестные целые числа. Из первых двух уравнений: m₁·k₁ − m₂·k₂ = a₂ − a₁ — это линейное диофантово уравнение. КТО гарантирует, что при взаимно простых mᵢ вся система имеет решение, и даёт явный алгоритм его построения.

Вывод для школьников: любая задача на «найти число по остаткам от деления» — это система диофантовых уравнений, решаемая по формуле КТО. Не нужно угадывать число перебором — достаточно применить алгоритм из раздела 3.

Задача-ребус 1: классическая задача Сунь-цзы

🧩 Задача (историческая)

«Есть число, которое при делении на 3 даёт остаток 2, при делении на 5 даёт остаток 3, при делении на 7 даёт остаток 2. Найдите наименьшее такое число.»

Источник: «Сунь-цзы суань цзин», задача XXVI.

Решение по КТО:

Система: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) M = 3·5·7 = 105 M₁ = 35, y₁ = 35⁻¹ mod 3 = 2 M₂ = 21, y₂ = 21⁻¹ mod 5 = 1 M₃ = 15, y₃ = 15⁻¹ mod 7 = 1 x = (2·35·2 + 3·21·1 + 2·15·1) mod 105 = (140 + 63 + 30) mod 105 = 233 mod 105 = 23

Ответ: наименьшее такое число равно 23. Проверка: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓.

Задача-ребус 2: восстановление трёхзначного числа

🧩 Задача (олимпиадная)

Трёхзначное число при делении на 8 даёт остаток 3, при делении на 9 даёт остаток 5, при делении на 11 даёт остаток 2. Найдите это число.

Шаг 1. Проверяем взаимную простоту: НОД(8,9) = НОД(8,11) = НОД(9,11) = 1 ✓.

Шаг 2. M = 8·9·11 = 792. Частичные произведения: M₁ = 99, M₂ = 88, M₃ = 72.

Шаг 3. Обратные элементы:

99⁻¹ mod 8: 99 mod 8 = 3; 3·3 = 9 ≡ 1 (mod 8) → y₁ = 3 88⁻¹ mod 9: 88 mod 9 = 7; 7·4 = 28 ≡ 1 (mod 9) → y₂ = 4 72⁻¹ mod 11: 72 mod 11 = 6; 6·2 = 12 ≡ 1 (mod 11) → y₃ = 2

Шаг 4. x = (3·99·3 + 5·88·4 + 2·72·2) mod 792 = (891 + 1760 + 288) mod 792 = 2939 mod 792 = 563.

Ответ: 563. Проверка: 563 mod 8 = 3 ✓, 563 mod 9 = 5 ✓, 563 mod 11 = 2 ✓.

Применение КТО в криптографии RSA Новый раздел

Одно из важнейших практических применений КТО — ускорение операции расшифрования в криптосистеме RSA. В стандартном RSA расшифрование — это вычисление m = c^d mod n, где n = p·q — произведение двух больших простых чисел.

КТО-ускорение расшифрования RSA (алгоритм Гарнера для RSA)

Так как n = p·q и НОД(p, q) = 1, по КТО вычисление c^d mod n эквивалентно паре вычислений:

m_p = c^(d mod (p−1)) mod p m_q = c^(d mod (q−1)) mod q

а затем восстановлению m из пары (m_p, m_q) по КТО. Поскольку p и q примерно вдвое меньше n, возведение в степень по каждому из них примерно в 4 раза быстрее. Итоговое ускорение — примерно в 4 раза по сравнению с прямым вычислением.

Параметры CRT в стандарте PKCS#1

Параметр	Обозначение	Формула
CRT-экспонента 1	d_p	d mod (p−1)
CRT-экспонента 2	d_q	d mod (q−1)
CRT-коэффициент	q_inv	q⁻¹ mod p

Расшифрование с CRT:

mp = pow(c, dp, p) # c^dp mod p mq = pow(c, dq, q) # c^dq mod q h = qinv * (mp - mq) % p # CRT-восстановление m = mq + h * q # итоговое сообщение

Применения КТО в олимпиадных задачах

Типовые паттерны использования КТО на олимпиадах

Паттерн	Описание	Пример
Восстановление числа по остаткам	Напрямую применяется классический CRT	«Найти наименьшее натуральное число, дающее остатки 2, 3, 2 при делении на 3, 5, 7»
Большие степени по составному модулю	Разбиваем модуль на простые степени, применяем CRT	aⁿ mod (p·q) при взаимно простых p, q
Подсчёт решений системы	КТО гарантирует ровно одно решение в [0, M)	Задачи на комбинаторику с делимостью
Параллельные вычисления	Разложение задачи по независимым модулям	Многопоточное возведение в степень

Типичная задача ЕГЭ / олимпиады с применением КТО

📝 Задача

Найти наименьшее натуральное число x, которое при делении на 3 даёт остаток 1, при делении на 5 даёт остаток 2, при делении на 7 даёт остаток 3.

Решение: Система: x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7). M = 105, M₁ = 35, M₂ = 21, M₃ = 15.

35⁻¹ mod 3 = 2 (т.к. 35 ≡ 2 (mod 3), 2·2 = 4 ≡ 1)
21⁻¹ mod 5 = 1 (т.к. 21 ≡ 1 (mod 5))
15⁻¹ mod 7 = 1 (т.к. 15 ≡ 1 (mod 7))

x = (1·35·2 + 2·21·1 + 3·15·1) mod 105 = (70 + 42 + 45) mod 105 = 157 mod 105 = 52

Проверка: 52 = 17·3 + 1 ✓; 52 = 10·5 + 2 ✓; 52 = 7·7 + 3 ✓.

Частые ошибки и как их избежать

Ошибка	Пример	Как избежать
Не проверена взаимная простота модулей	Применение классического CRT к модулям 6 и 10	Всегда вычисляйте НОД(mᵢ, mⱼ) для всех пар перед началом
Отрицательный обратный элемент в C++	`x % m` возвращает отрицательное значение	Нормализуйте: `((x % m) + m) % m`
Переполнение при вычислении M	Произведение 10 модулей по 10⁹ превышает 64 бита	Используйте алгоритм Гарнера или BigInteger
Забыта финальная проверка	Вычисленный x не подставлен в исходные сравнения	Всегда проверяйте: `assert x % m == a` для каждой пары
Остатки больше модуля	Передан остаток aᵢ = 7 при модуле mᵢ = 5	Нормализуйте входные данные: `a = a % m`

Итоговая таблица методов и чек-лист

Ситуация	Рекомендуемый метод	Ключевая особенность
Модули взаимно просты, малые числа, ручной счёт	Классический CRT	Прямая формула с Mᵢ и обратными элементами
Большие числа, олимпиадное программирование	Алгоритм Гарнера	Нет переполнения, смешанная система счисления
Ответ может быть отрицательным	Гарнер signed	Если x > M/2, то x ← x − M
Модули не взаимно просты	Последовательное объединение пар	Проверять (aᵢ − aⱼ) mod НОД(mᵢ, mⱼ) = 0
Криптография RSA	CRT-расшифрование (алгоритм Гарнера)	Ускорение в ~4 раза через d_p, d_q, q_inv
Поиск обратного элемента	Расш. алгоритм Евклида или `pow(a,-1,m)`	В Python 3.8+ встроенная функция

✅ Чек-лист перед решением задачи с КТО:

Проверены ли попарные НОД модулей (равны ли 1)?
Если нет — проверено ли условие совместимости (aᵢ − aⱼ) mod НОД(mᵢ, mⱼ) = 0?
Вычислено ли M = m₁ · ... · mₖ?
Для каждого i найдены ли Mᵢ и Mᵢ⁻¹ mod mᵢ?
Выполнена ли проверка подстановкой x в каждое исходное сравнение?
Если ответ может быть отрицательным — применено ли знаковое восстановление?
При работе в C++ — нормализованы ли отрицательные промежуточные остатки?

Литература и полезные ссылки

📚 Учебная литература:

Гаусс К.Ф. «Арифметические исследования» (Disquisitiones Arithmeticae, 1801) — классический источник строгого доказательства КТО.
Ирландия К., Розен М. «Классическое введение в современную теорию чисел» — подробное изложение КТО в алгебраическом контексте.
Кнут Д.Э. «Искусство программирования», том 2 — алгоритмы модульной арифметики, алгоритм Гарнера.
Шень А., Верещагин Н. «Начала теории множеств» — вводный курс, включающий модульную арифметику.

🔗 Онлайн-ресурсы:

cp-algorithms.com — Chinese Remainder Theorem (алгоритм Гарнера с кодом на C++)
e-maxx.ru — Китайская теорема об остатках (русскоязычное изложение с примерами)
Подготовка к ЕГЭ по математике на Skysmart

Помогите ребёнку поверить
в себя и получить знания
для успешного будущего

Заполните заявку
и получите программу
обучения для вашего ребёнка