Китайская теорема об остатках: расширенный Евклид, обратный элемент и сборка решения

Китайская теорема об остатках на примерах: расширенный алгоритм Евклида, обратный по модулю, сборка решения системы сравнений, некопростые модули и алгоритм Гарнера. Код на Python.

11 мин чтенияалгоритмы · математика · теория чисел · python

Коротко

ВопросОтвет
Что решаетНаходит xx по остаткам от деления на несколько модулей
Когда решение одноМодули попарно взаимно просты — тогда xx единственен по модулю M=m1m2…mkM = m_1 m_2 \dots m_k
Главный инструментРасширенный алгоритм Евклида → обратный элемент по модулю
СложностьO(klog⁡M)O(k \log M) операций над числами (длинная арифметика — отдельный разговор)
Некопростые модулиРешение есть не всегда; сливаем уравнения попарно через НОД и НОК

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

Задача

Классическая формулировка из трактата Сунь-цзы (примерно III–V век): найти число, которое при делении на 3 даёт остаток 2, при делении на 5 — остаток 3, а при делении на 7 — снова 2. В современной записи это система сравнений:

{x≡2(mod3)x≡3(mod5)x≡2(mod7)\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{cases}

Ответ — 23. И 128, и 233, и любое 23+105t23 + 105t: все решения отличаются на 105=3⋅5⋅7105 = 3 \cdot 5 \cdot 7.

Теорема. Если модули m1,…,mkm_1, \dots, m_k попарно взаимно просты, то для любых остатков a1,…,aka_1, \dots, a_k система x≡ai(modmi)x \equiv a_i \pmod{m_i} имеет ровно одно решение на отрезке [0,M)[0, M), где M=m1m2⋯mkM = m_1 m_2 \cdots m_k.

Интуиция такая: остатков по модулю MM ровно MM штук, и наборов (a1,…,ak)(a_1, \dots, a_k) тоже m1⋯mk=Mm_1 \cdots m_k = M. Отображение «число → набор остатков» инъективно: если два числа дают одинаковые остатки, их разность делится на каждый mim_i, а значит, и на их произведение (модули взаимно просты). Инъекция между множествами одного размера — это биекция, значит каждому набору соответствует ровно одно число.

Обратите внимание: теорема говорит, что решение существует, но не говорит, как его найти. Этим и займёмся.

Наивное решение: перебор

Самое прямолинейное — перебрать все xx от 0 до M−1M - 1 и проверить остатки:

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

Работает за O(M⋅k)O(M \cdot k). Для модулей вроде 109+710^9 + 7 и 998244353998244353 произведение порядка 101810^{18} — перебор безнадёжен. Нужен способ строить ответ напрямую, и для этого понадобится обратный элемент.

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

Обычный алгоритм Евклида находит gcd⁡(a,b)\gcd(a, b). Расширенный дополнительно возвращает коэффициенты x,yx, y, для которых выполняется соотношение Безу:

ax+by=gcd⁡(a,b)a x + b y = \gcd(a, b)

Как это работает

Будем вести не только остатки rir_i, но и для каждого остатка — коэффициенты xi,yix_i, y_i, которые выражают его через исходные числа: ri=axi+byir_i = a x_i + b y_i.

Стартуем с r0=ar_0 = a (x=1,y=0x = 1, y = 0) и r1=br_1 = b (x=0,y=1x = 0, y = 1). Каждый следующий остаток получается как ri+1=ri−1−q⋅rir_{i+1} = r_{i-1} - q \cdot r_i, где q=⌊ri−1/ri⌋q = \lfloor r_{i-1} / r_i \rfloor. Раз остатки комбинируются линейно, коэффициенты комбинируются точно так же: xi+1=xi−1−q⋅xix_{i+1} = x_{i-1} - q \cdot x_i, и аналогично для yy. Инвариант ri=axi+byir_i = a x_i + b y_i сохраняется на каждом шаге.

Разберём a=240a = 240, b=46b = 46:

rrqqxxyyПроверка 240x+46y240x + 46y
24010240
460146
1051−5240 − 230 = 10
64−421−960 + 966 = 6
415−261200 − 1196 = 4
21−947−2160 + 2162 = 2
02стоп

Последний ненулевой остаток — 2, это и есть НОД, а коэффициенты: 240⋅(−9)+46⋅47=2240 \cdot (-9) + 46 \cdot 47 = 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)

Число итераций — O(log⁡min⁡(a,b))O(\log \min(a, b)), как у обычного Евклида: худший случай дают соседние числа Фибоначчи.

Обратный элемент по модулю

Обратный к aa по модулю mm — такое число a−1a^{-1}, что a⋅a−1≡1(modm)a \cdot a^{-1} \equiv 1 \pmod m. Он существует тогда и только тогда, когда gcd⁡(a,m)=1\gcd(a, m) = 1.

Связь с расширенным Евклидом прямая. Если gcd⁡(a,m)=1\gcd(a, m) = 1, то алгоритм вернёт x,yx, y с ax+my=1a x + m y = 1. Возьмём это равенство по модулю mm: слагаемое mym y исчезнет, останется ax≡1(modm)a x \equiv 1 \pmod m. Значит, xx — искомый обратный (его остаётся только привести в диапазон [0,m)[0, m)).

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+

В статье про модульную арифметику обратный элемент искали через малую теорему Ферма: a−1=am−2 mod ma^{-1} = a^{m-2} \bmod m с помощью быстрого возведения в степень. Это короче в коде, но работает только для простого mm. В китайской теореме модули обычно произвольные — 3,5,73, 5, 7, или 88 и 99, или 10610^6, — поэтому здесь нужен именно расширенный Евклид.

Сборка решения

Теперь соберём ответ. Обозначим M=m1⋯mkM = m_1 \cdots m_k и Mi=M/miM_i = M / m_i — произведение всех модулей, кроме ii-го.

Ключевое наблюдение: MiM_i делится на все mjm_j при j≠ij \ne i, то есть даёт по ним остаток 0. А по модулю mim_i число MiM_i взаимно просто с mim_i и потому обратимо. Пусть yi=Mi−1 mod miy_i = M_i^{-1} \bmod m_i. Тогда слагаемое

ei=Mi⋅yie_i = M_i \cdot y_i

даёт остаток 1 по модулю mim_i и остаток 0 по всем остальным. Это «единичный вектор» в мире остатков. Дальше всё как в линейной алгебре — складываем базисные векторы с нужными коэффициентами:

x=∑i=1kai⋅Mi⋅yi(modM)x = \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i \pmod M

По модулю mim_i все слагаемые, кроме ii-го, обнуляются, а ii-е даёт ai⋅1=aia_i \cdot 1 = a_i. Ровно то, что требуется.

Разбор на примере

Система x≡2(mod3)x \equiv 2 \pmod 3, x≡3(mod5)x \equiv 3 \pmod 5, x≡2(mod7)x \equiv 2 \pmod 7, M=105M = 105:

iimim_iaia_iMiM_iMi mod miM_i \bmod m_iyiy_iaiMiyia_i M_i y_i
1323522140
253211163
372151130

Сумма 140+63+30=233140 + 63 + 30 = 233, и 233 mod 105=23233 \bmod 105 = 23. Проверка: 23=7⋅3+2=4⋅5+3=3⋅7+223 = 7 \cdot 3 + 2 = 4 \cdot 5 + 3 = 3 \cdot 7 + 2.

Код

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

Последний пример показывает практический смысл: число до ≈1018\approx 10^{18} можно хранить и обрабатывать как пару остатков по двум простым модулям, а в конце восстановить целиком.

Формула красивая, но у неё есть неудобство: промежуточные MiM_i и сумма имеют размер порядка MM. В Python это не проблема, а в C++ или Java при M>263M > 2^{63} уже нужна длинная арифметика или аккуратное умножение по модулю. Об обходе этого — ниже, в разделе про Гарнера.

Слияние уравнений по два

На практике удобнее решать систему не формулой целиком, а пошагово: слить первые два сравнения в одно, затем результат — с третьим, и так далее. Этот подход заодно работает для модулей, которые не взаимно просты.

Пусть есть x≡r1(modm1)x \equiv r_1 \pmod{m_1} и x≡r2(modm2)x \equiv r_2 \pmod{m_2}. Из первого x=r1+m1kx = r_1 + m_1 k для некоторого целого kk. Подставим во второе:

m1k≡r2−r1(modm2)m_1 k \equiv r_2 - r_1 \pmod{m_2}

Пусть g=gcd⁡(m1,m2)g = \gcd(m_1, m_2). Левая часть делится на gg, модуль тоже, значит, решение есть только если r2−r1r_2 - r_1 делится на gg. Если делится — сокращаем всё на gg:

m1gk≡r2−r1g(modm2g)\frac{m_1}{g} k \equiv \frac{r_2 - r_1}{g} \pmod{\frac{m_2}{g}}

Теперь m1/gm_1 / g и m2/gm_2 / g взаимно просты, и обратный к m1/gm_1 / g даёт тот же расширенный Евклид: из m1p+m2q=gm_1 p + m_2 q = g после деления на gg получаем m1gp≡1(modm2g)\frac{m_1}{g} p \equiv 1 \pmod{\frac{m_2}{g}}. Отсюда kk, а итоговый модуль — lcm⁡(m1,m2)=m1m2/g\operatorname{lcm}(m_1, m_2) = m_1 m_2 / g.

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 не взаимно просты: g=2g = 2.

  • x≡3(mod6)x \equiv 3 \pmod 6, x≡5(mod8)x \equiv 5 \pmod 8: разность 5−3=25 - 3 = 2 делится на 2, решение есть. Ответ 21 по модулю lcm⁡(6,8)=24\operatorname{lcm}(6, 8) = 24. Проверка: 21=3⋅6+3=2⋅8+521 = 3 \cdot 6 + 3 = 2 \cdot 8 + 5.
  • x≡3(mod6)x \equiv 3 \pmod 6, x≡4(mod8)x \equiv 4 \pmod 8: первое требует нечётного xx, второе — чётного. Разность 11 на 2 не делится — противоречие, и функция честно возвращает None.

Важно: при некопростых модулях ответ единственен по модулю НОК, а не произведения. Это частая ошибка — вернуть остаток по m1m2m_1 m_2 и получить лишние «решения».

Классическая задача про корзину яиц хорошо иллюстрирует общий случай: при раскладке по 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.

Ещё один способ справиться с некопростыми модулями — разложить каждый модуль на простые множители и перейти к системе по степеням простых: x≡a(mod12)x \equiv a \pmod{12} эквивалентно паре x≡a(mod4)x \equiv a \pmod 4, x≡a(mod3)x \equiv a \pmod 3. После этого для каждого простого оставляем сравнение по наибольшей степени, проверив согласованность остальных. Слияние через НОД короче в коде, поэтому на практике пользуются им.

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

Формула из раздела «Сборка решения» оперирует числами размера MM. Если MM огромно — например, три модуля около 10910^9 дают M≈1027M \approx 10^{27}, — хочется работать только с маленькими числами. Это и делает алгоритм Гарнера.

Идея: записать ответ в смешанной системе счисления

x=c0+c1m0+c2m0m1+⋯+ck−1m0m1⋯mk−2,0≤ci<mix = c_0 + c_1 m_0 + c_2 m_0 m_1 + \dots + c_{k-1} m_0 m_1 \cdots m_{k-2}, \quad 0 \le c_i < m_i

Возьмём это по модулю m0m_0 — получим c0=a0c_0 = a_0. По модулю m1m_1: a1≡c0+c1m0a_1 \equiv c_0 + c_1 m_0, откуда c1=(a1−c0)⋅m0−1 mod m1c_1 = (a_1 - c_0) \cdot m_0^{-1} \bmod m_1. И так далее: каждая следующая «цифра» находится по уже известным, причём все вычисления идут по модулю mim_i — маленькие числа.

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

Сложность — O(k2)O(k^2) обращений, а обратные mj−1 mod mim_j^{-1} \bmod m_i можно предпосчитать один раз. Главный плюс: если нужен не сам xx, а x mod Px \bmod P для какого-то третьего модуля PP, последнюю свёртку можно вести по модулю PP и вообще не выходить за 64 бита. Так собирают результат быстрого преобразования Фурье по нескольким простым модулям (NTT), когда коэффициенты не помещаются в один модуль.

Сложность

ШагВремяЧисла
Расширенный Евклид для (a,m)(a, m)O(log⁡m)O(\log m)порядка mm
Формула со сборкой через MiM_iO(klog⁡M)O(k \log M)порядка MM
Попарное слияние (любые модули)O(klog⁡M)O(k \log M)порядка НОК
ГарнерO(k2)O(k^2) + обратныепорядка max⁡mi\max m_i

Для двух-трёх модулей разница между подходами несущественна, выбирайте тот, который проще написать без ошибок. Для многих модулей и языков с фиксированной разрядностью — Гарнер.

Типичные ошибки

Обратный через Ферма для составного модуля. pow(a, m - 2, m) для m=8m = 8 или m=10m = 10 возвращает мусор. Для произвольного модуля — только расширенный Евклид или pow(a, -1, m).

Отрицательный результат. Расширенный Евклид часто возвращает отрицательные коэффициенты (в примере выше x=−9x = -9). Не забывайте % m. В C++ и Java оператор % от отрицательного числа даёт отрицательный результат, нужно ((x % m) + m) % m.

Переполнение. Произведение ai⋅Mi⋅yia_i \cdot M_i \cdot y_i при модулях около 10910^9 легко выходит за 2632^{63}. В C++ используйте __int128 или умножение по модулю, в Java — BigInteger или Гарнера.

Модули не проверены на взаимную простоту. Формула ∑aiMiyi\sum a_i M_i y_i молча ломается, если какие-то mim_i имеют общий делитель: обратного к MiM_i просто не существует. Если входные модули произвольные — сразу пишите слияние через НОД.

Ответ по произведению вместо НОК. При некопростых модулях период решения — lcm⁡\operatorname{lcm}, а не ∏mi\prod m_i.

Остатки вне диапазона. Если во входе aia_i может быть отрицательным или больше mim_i, нормализуйте: a % m. В crt_general это уже сделано.

Где это встречается

  • Олимпиады и Codeforces. Задачи на системы сравнений, восстановление числа по остаткам, подсчёт по составному модулю. Например, биномиальный коэффициент по модулю 10610^6: раскладываем модуль на 26⋅562^6 \cdot 5^6, считаем по каждой степени простого отдельно и склеиваем китайской теоремой.
  • Advent of Code 2020, день 13. Задача про расписание автобусов, вторая часть которой — ровно система сравнений с большими модулями. Перебор там не проходит.
  • Криптография. В RSA расшифровку обычно ускоряют через китайскую теорему: вместо возведения в степень по модулю n=pqn = pq считают по pp и по qq отдельно и склеивают. Выигрыш — в несколько раз.
  • Хеширование и длинная арифметика. Вычисления по нескольким простым модулям вместо одного огромного, NTT с последующей сборкой Гарнером.

На обычных собеседованиях в продуктовые компании китайская теорема встречается редко. Но расширенный Евклид и обратный по модулю — частый follow-up к задачам «посчитайте ответ по модулю 109+710^9 + 7», а система двух сравнений — хороший способ проверить, понимает ли кандидат, откуда берётся обратный элемент.

Что запомнить

  • Расширенный Евклид даёт x,yx, y с ax+by=gcd⁡(a,b)ax + by = \gcd(a, b); при gcd⁡=1\gcd = 1 число xx — обратный к aa по модулю bb.
  • При попарно взаимно простых модулях: x=∑aiMi(Mi−1 mod mi) mod Mx = \sum a_i M_i (M_i^{-1} \bmod m_i) \bmod M.
  • Для произвольных модулей сливайте уравнения по два: решение есть, только если r2−r1r_2 - r_1 делится на gcd⁡(m1,m2)\gcd(m_1, m_2), а ответ живёт по модулю НОК.
  • Если числа не влезают в машинное слово — алгоритм Гарнера, он работает только с маленькими остатками.
  • Обратный через Ферма — только для простого модуля.

Потренироваться в спокойной обстановке

Все задачи