Китайская теорема об остатках: расширенный Евклид, обратный элемент и сборка решения
Китайская теорема об остатках на примерах: расширенный алгоритм Евклида, обратный по модулю, сборка решения системы сравнений, некопростые модули и алгоритм Гарнера. Код на Python.
Коротко
| Вопрос | Ответ |
|---|---|
| Что решает | Находит по остаткам от деления на несколько модулей |
| Когда решение одно | Модули попарно взаимно просты — тогда единственен по модулю |
| Главный инструмент | Расширенный алгоритм Евклида → обратный элемент по модулю |
| Сложность | операций над числами (длинная арифметика — отдельный разговор) |
| Некопростые модули | Решение есть не всегда; сливаем уравнения попарно через НОД и НОК |
Главная идея: систему сравнений можно решать по одному уравнению за раз, а каждый шаг сводится к поиску обратного элемента.
Задача
Классическая формулировка из трактата Сунь-цзы (примерно III–V век): найти число, которое при делении на 3 даёт остаток 2, при делении на 5 — остаток 3, а при делении на 7 — снова 2. В современной записи это система сравнений:
Ответ — 23. И 128, и 233, и любое : все решения отличаются на .
Теорема. Если модули попарно взаимно просты, то для любых остатков система имеет ровно одно решение на отрезке , где .
Интуиция такая: остатков по модулю ровно штук, и наборов тоже . Отображение «число → набор остатков» инъективно: если два числа дают одинаковые остатки, их разность делится на каждый , а значит, и на их произведение (модули взаимно просты). Инъекция между множествами одного размера — это биекция, значит каждому набору соответствует ровно одно число.
Обратите внимание: теорема говорит, что решение существует, но не говорит, как его найти. Этим и займёмся.
Наивное решение: перебор
Самое прямолинейное — перебрать все от 0 до и проверить остатки:
def brute(rems, mods): M = 1 for m in mods: M *= m for x in range(M): if all(x % m == a for a, m in zip(rems, mods)): return x return None print(brute([2, 3, 2], [3, 5, 7])) # 23
Работает за . Для модулей вроде и произведение порядка — перебор безнадёжен. Нужен способ строить ответ напрямую, и для этого понадобится обратный элемент.
Расширенный алгоритм Евклида
Обычный алгоритм Евклида находит . Расширенный дополнительно возвращает коэффициенты , для которых выполняется соотношение Безу:
Как это работает
Будем вести не только остатки , но и для каждого остатка — коэффициенты , которые выражают его через исходные числа: .
Стартуем с () и (). Каждый следующий остаток получается как , где . Раз остатки комбинируются линейно, коэффициенты комбинируются точно так же: , и аналогично для . Инвариант сохраняется на каждом шаге.
Разберём , :
| Проверка | ||||
|---|---|---|---|---|
| 240 | 1 | 0 | 240 | |
| 46 | 0 | 1 | 46 | |
| 10 | 5 | 1 | −5 | 240 − 230 = 10 |
| 6 | 4 | −4 | 21 | −960 + 966 = 6 |
| 4 | 1 | 5 | −26 | 1200 − 1196 = 4 |
| 2 | 1 | −9 | 47 | −2160 + 2162 = 2 |
| 0 | 2 | стоп |
Последний ненулевой остаток — 2, это и есть НОД, а коэффициенты: .
Код
Итеративная версия не упирается в лимит рекурсии и легко переносится на другие языки:
def ext_gcd(a, b): """Возвращает (g, x, y), где a*x + b*y = g = gcd(a, b).""" x0, y0, x1, y1 = 1, 0, 0, 1 while b: q = a // b a, b = b, a - q * b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return a, x0, y0 print(ext_gcd(240, 46)) # (2, -9, 47)
Число итераций — , как у обычного Евклида: худший случай дают соседние числа Фибоначчи.
Обратный элемент по модулю
Обратный к по модулю — такое число , что . Он существует тогда и только тогда, когда .
Связь с расширенным Евклидом прямая. Если , то алгоритм вернёт с . Возьмём это равенство по модулю : слагаемое исчезнет, останется . Значит, — искомый обратный (его остаётся только привести в диапазон ).
def mod_inverse(a, m): g, x, _ = ext_gcd(a % m, m) if g != 1: raise ValueError(f"{a} не обратимо по модулю {m}") return x % m print(mod_inverse(3, 7)) # 5, потому что 3 * 5 = 15 = 2*7 + 1 print(mod_inverse(17, 3120)) # 2753 — тот самый d из учебного примера RSA print(pow(17, -1, 3120)) # 2753, встроенный способ в Python 3.8+
В статье про модульную арифметику обратный элемент искали через малую теорему Ферма: с помощью быстрого возведения в степень. Это короче в коде, но работает только для простого . В китайской теореме модули обычно произвольные — , или и , или , — поэтому здесь нужен именно расширенный Евклид.
Сборка решения
Теперь соберём ответ. Обозначим и — произведение всех модулей, кроме -го.
Ключевое наблюдение: делится на все при , то есть даёт по ним остаток 0. А по модулю число взаимно просто с и потому обратимо. Пусть . Тогда слагаемое
даёт остаток 1 по модулю и остаток 0 по всем остальным. Это «единичный вектор» в мире остатков. Дальше всё как в линейной алгебре — складываем базисные векторы с нужными коэффициентами:
По модулю все слагаемые, кроме -го, обнуляются, а -е даёт . Ровно то, что требуется.
Разбор на примере
Система , , , :
| 1 | 3 | 2 | 35 | 2 | 2 | 140 |
| 2 | 5 | 3 | 21 | 1 | 1 | 63 |
| 3 | 7 | 2 | 15 | 1 | 1 | 30 |
Сумма , и . Проверка: .
Код
def crt(rems, mods): """Модули попарно взаимно просты. Возвращает x из [0, M).""" M = 1 for m in mods: M *= m x = 0 for a, m in zip(rems, mods): Mi = M // m x += a * Mi * mod_inverse(Mi, m) return x % M print(crt([2, 3, 2], [3, 5, 7])) # 23 MOD1, MOD2 = 10**9 + 7, 998244353 v = 123456789012345678 print(crt([v % MOD1, v % MOD2], [MOD1, MOD2]) == v) # True
Последний пример показывает практический смысл: число до можно хранить и обрабатывать как пару остатков по двум простым модулям, а в конце восстановить целиком.
Формула красивая, но у неё есть неудобство: промежуточные и сумма имеют размер порядка . В Python это не проблема, а в C++ или Java при уже нужна длинная арифметика или аккуратное умножение по модулю. Об обходе этого — ниже, в разделе про Гарнера.
Слияние уравнений по два
На практике удобнее решать систему не формулой целиком, а пошагово: слить первые два сравнения в одно, затем результат — с третьим, и так далее. Этот подход заодно работает для модулей, которые не взаимно просты.
Пусть есть и . Из первого для некоторого целого . Подставим во второе:
Пусть . Левая часть делится на , модуль тоже, значит, решение есть только если делится на . Если делится — сокращаем всё на :
Теперь и взаимно просты, и обратный к даёт тот же расширенный Евклид: из после деления на получаем . Отсюда , а итоговый модуль — .
def crt_merge(r1, m1, r2, m2): """Сливает x ≡ r1 (mod m1) и x ≡ r2 (mod m2). Возвращает (r, lcm) или None.""" g, p, _ = ext_gcd(m1, m2) if (r2 - r1) % g: return None # система несовместна lcm = m1 // g * m2 k = (r2 - r1) // g * p % (m2 // g) return (r1 + m1 * k) % lcm, lcm def crt_general(rems, mods): r, m = 0, 1 # x ≡ 0 (mod 1) — любое число for a, mi in zip(rems, mods): res = crt_merge(r, m, a % mi, mi) if res is None: return None r, m = res return r, m print(crt_general([2, 3, 2], [3, 5, 7])) # (23, 105) print(crt_general([3, 5], [6, 8])) # (21, 24) print(crt_general([3, 4], [6, 8])) # None
Разберём два последних случая. Модули 6 и 8 не взаимно просты: .
- , : разность делится на 2, решение есть. Ответ 21 по модулю . Проверка: .
- , : первое требует нечётного , второе — чётного. Разность на 2 не делится — противоречие, и функция честно возвращает
None.
Важно: при некопростых модулях ответ единственен по модулю НОК, а не произведения. Это частая ошибка — вернуть остаток по и получить лишние «решения».
Классическая задача про корзину яиц хорошо иллюстрирует общий случай: при раскладке по 2, 3, 4, 5 и 6 остаётся одно яйцо, а по 7 — ничего не остаётся. Модули тут сильно пересекаются, но слияние справляется:
print(crt_general([1, 1, 1, 1, 1, 0], [2, 3, 4, 5, 6, 7])) # (301, 420)
Наименьший ответ — 301 яйцо, следующий — 721.
Ещё один способ справиться с некопростыми модулями — разложить каждый модуль на простые множители и перейти к системе по степеням простых: эквивалентно паре , . После этого для каждого простого оставляем сравнение по наибольшей степени, проверив согласованность остальных. Слияние через НОД короче в коде, поэтому на практике пользуются им.
Алгоритм Гарнера (кратко)
Формула из раздела «Сборка решения» оперирует числами размера . Если огромно — например, три модуля около дают , — хочется работать только с маленькими числами. Это и делает алгоритм Гарнера.
Идея: записать ответ в смешанной системе счисления
Возьмём это по модулю — получим . По модулю : , откуда . И так далее: каждая следующая «цифра» находится по уже известным, причём все вычисления идут по модулю — маленькие числа.
def garner(rems, mods): """Цифры x в смешанной системе: x = c0 + c1*m0 + c2*m0*m1 + ...""" k = len(mods) c = [0] * k for i in range(k): c[i] = rems[i] for j in range(i): c[i] = (c[i] - c[j]) * pow(mods[j], -1, mods[i]) % mods[i] x, base = 0, 1 for i in range(k): x += c[i] * base base *= mods[i] return c, x print(garner([2, 3, 2], [3, 5, 7])) # ([2, 2, 1], 23): 2 + 2*3 + 1*15 = 23
Сложность — обращений, а обратные можно предпосчитать один раз. Главный плюс: если нужен не сам , а для какого-то третьего модуля , последнюю свёртку можно вести по модулю и вообще не выходить за 64 бита. Так собирают результат быстрого преобразования Фурье по нескольким простым модулям (NTT), когда коэффициенты не помещаются в один модуль.
Сложность
| Шаг | Время | Числа |
|---|---|---|
| Расширенный Евклид для | порядка | |
| Формула со сборкой через | порядка | |
| Попарное слияние (любые модули) | порядка НОК | |
| Гарнер | + обратные | порядка |
Для двух-трёх модулей разница между подходами несущественна, выбирайте тот, который проще написать без ошибок. Для многих модулей и языков с фиксированной разрядностью — Гарнер.
Типичные ошибки
Обратный через Ферма для составного модуля. pow(a, m - 2, m) для или возвращает мусор. Для произвольного модуля — только расширенный Евклид или pow(a, -1, m).
Отрицательный результат. Расширенный Евклид часто возвращает отрицательные коэффициенты (в примере выше ). Не забывайте % m. В C++ и Java оператор % от отрицательного числа даёт отрицательный результат, нужно ((x % m) + m) % m.
Переполнение. Произведение при модулях около легко выходит за . В C++ используйте __int128 или умножение по модулю, в Java — BigInteger или Гарнера.
Модули не проверены на взаимную простоту. Формула молча ломается, если какие-то имеют общий делитель: обратного к просто не существует. Если входные модули произвольные — сразу пишите слияние через НОД.
Ответ по произведению вместо НОК. При некопростых модулях период решения — , а не .
Остатки вне диапазона. Если во входе может быть отрицательным или больше , нормализуйте: a % m. В crt_general это уже сделано.
Где это встречается
- Олимпиады и Codeforces. Задачи на системы сравнений, восстановление числа по остаткам, подсчёт по составному модулю. Например, биномиальный коэффициент по модулю : раскладываем модуль на , считаем по каждой степени простого отдельно и склеиваем китайской теоремой.
- Advent of Code 2020, день 13. Задача про расписание автобусов, вторая часть которой — ровно система сравнений с большими модулями. Перебор там не проходит.
- Криптография. В RSA расшифровку обычно ускоряют через китайскую теорему: вместо возведения в степень по модулю считают по и по отдельно и склеивают. Выигрыш — в несколько раз.
- Хеширование и длинная арифметика. Вычисления по нескольким простым модулям вместо одного огромного, NTT с последующей сборкой Гарнером.
На обычных собеседованиях в продуктовые компании китайская теорема встречается редко. Но расширенный Евклид и обратный по модулю — частый follow-up к задачам «посчитайте ответ по модулю », а система двух сравнений — хороший способ проверить, понимает ли кандидат, откуда берётся обратный элемент.
Что запомнить
- Расширенный Евклид даёт с ; при число — обратный к по модулю .
- При попарно взаимно простых модулях: .
- Для произвольных модулей сливайте уравнения по два: решение есть, только если делится на , а ответ живёт по модулю НОК.
- Если числа не влезают в машинное слово — алгоритм Гарнера, он работает только с маленькими остатками.
- Обратный через Ферма — только для простого модуля.