Сравнения и китайская теорема

Запись $x \equiv y \pmod m$ читается «$x$ сравнимо с $y$ по модулю $m$» и означает, что $x - y$ делится на $m$. Со сравнениями можно обращаться почти как с равенствами: складывать, вычитать, умножать. Проблемы начинаются на делении — и вот с них всё интересное и начинается.

Линейное сравнение

Задача: найти все $x$, для которых

$$a x \equiv b \pmod m$$

Это в точности диофантово уравнение $a x - m y = b$, только записанное короче. Значит, работает расширенный Евклид, и сразу известен критерий:

Решение существует тогда и только тогда, когда $b$ делится на $g = \gcd(a, m)$.

Дальше — то, чего в обычном уравнении не было. Решений не одно, а ровно $g$ штук по модулю $m$, и идут они с шагом $m/g$:

$$x_k = x_0 + k \cdot \frac{m}{g}, \qquad k = 0, 1, \dots, g-1$$

// все решения a*x = b (mod m); пустой вектор, если решений нет
vector<long long> solveCongruence(long long a, long long b, long long m) {
    long long x, y;
    long long g = gcdExt(((a % m) + m) % m, m, x, y);
    if (b % g != 0) return {};
    long long x0 = ((__int128)x * (b / g)) % m;
    x0 = ((x0 % m) + m) % m;
    vector<long long> answer;
    for (long long k = 0; k < g; k++) answer.push_back((x0 + k * (m / g)) % m);
    return answer;
}

Два места, где легко ошибиться. Первое — __int128 при домножении: $x$ может быть порядка $m$, и произведение с $b/g$ переполнит long long. Второе — двойная нормализация ((x % m) + m) % m: остаток от отрицательного числа в C++ отрицателен, а нам нужен представитель из $[0, m)$.

Частный случай $g = 1$ — это ровно обратный элемент: решение единственно и равно $b \cdot a^{-1}$.

Система сравнений

Теперь несколько условий сразу:

$$x \equiv r_1 \pmod{m_1}, \qquad x \equiv r_2 \pmod{m_2}$$

Классическая формулировка — «число при делении на 3 даёт остаток 2, при делении на 5 — остаток 3; найдите его». Ответ: система либо не имеет решений, либо её решения образуют один класс вычетов по модулю $\mathrm{lcm}(m_1, m_2)$.

Критерий разрешимости: $r_1 \equiv r_2 \pmod{\gcd(m_1, m_2)}$.

Логика простая. Ищем $x$ в виде $x = r_1 + t \cdot m_1$. Подставляем во второе условие: $r_1 + t m_1 \equiv r_2 \pmod{m_2}$, то есть $t m_1 \equiv r_2 - r_1 \pmod{m_2}$. Это опять линейное сравнение — и оно разрешимо ровно тогда, когда $r_2 - r_1$ делится на $\gcd(m_1, m_2)$.

// x = r1 (mod m1), x = r2 (mod m2)  ->  x = r (mod m)
bool crt(long long r1, long long m1, long long r2, long long m2,
         long long &r, long long &m) {
    long long p, q;
    long long g = gcdExt(m1, m2, p, q);
    if ((r2 - r1) % g != 0) return false;
    m = m1 / g * m2;                          // это lcm(m1, m2)
    __int128 t = (__int128)((r2 - r1) / g) * p % (m2 / g);
    __int128 value = r1 + t * m1;
    r = (long long)(((value % m) + m) % m);
    return true;
}

Больше двух сравнений склеиваются по очереди: свернули первые два в одно, к результату приклеили третье, и так далее. Если на каком-то шаге вернулся false — вся система несовместна.

flowchart LR
    A["x = 2 (mod 3)"] --> M1{"склейка"}
    B["x = 3 (mod 5)"] --> M1
    M1 --> C["x = 8 (mod 15)"]
    C --> M2{"склейка"}
    D["x = 2 (mod 7)"] --> M2
    M2 --> E["x = 23 (mod 105)"]

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

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

Пусть $m = m_1 m_2 \dots m_k$, модули попарно взаимно просты. Тогда отображение

$$x \;\longmapsto\; (x \bmod m_1,\; x \bmod m_2,\; \dots,\; x \bmod m_k)$$

является взаимно однозначным между $\{0, 1, \dots, m-1\}$ и наборами остатков. Иначе говоря, число до $m$ полностью определяется своими остатками — и любой набор остатков достижим.

Считать это можно тем же склеиванием, а можно прямой формулой: $x = \sum r_i \cdot M_i \cdot M_i^{-1} \bmod m$, где $M_i = m / m_i$, а обратный берётся по модулю $m_i$. На практике склеивание удобнее — оно не требует взаимной простоты и не переполняется так легко.

Зачем это нужно

Обход переполнения. Задача просит ответ по модулю $10^{18}$, а промежуточные произведения не помещаются даже в __int128. Считаем ответ по нескольким простым модулям около $10^9$ и склеиваем — на каждом шаге умножение честно влезает в 64 бита.

Хеширование строк. Один модуль ломается подобранным тестом. Два независимых модуля через КТО эквивалентны одному модулю порядка их произведения — вероятность коллизии падает до квадрата.

Периодичность. «Событие A происходит раз в $m_1$ дней, событие B — раз в $m_2$; когда они совпадут» — это система сравнений, и ответ живёт с периодом $\mathrm{lcm}$.

Разложение задачи по простым. Уравнение по составному модулю $m = p_1^{a_1} \dots p_k^{a_k}$ решается отдельно по каждому $p_i^{a_i}$, а решения потом склеиваются. Число решений при этом перемножается.

Про малую теорему Ферма и Эйлера

Рядом стоят два факта, которые постоянно нужны вместе со сравнениями.

Малая теорема Ферма: если $p$ простое и $a$ не делится на $p$, то $a^{p-1} \equiv 1 \pmod p$. Отсюда обратный элемент как $a^{p-2}$.

Теорема Эйлера обобщает: если $\gcd(a, m) = 1$, то $a^{\varphi(m)} \equiv 1 \pmod m$.

Практическое следствие — понижение показателя. Считая $a^{n}$ по модулю $m$ при гигантском $n$ (например, заданном строкой из миллиона цифр), показатель берут по модулю $\varphi(m)$, а не по модулю $m$. Брать показатель по модулю $m$ — распространённая и молчаливая ошибка: формула выглядит симметрично, но она неверна.