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

Обратный элемент и деление по модулю двумя способами, а также идея китайской теоремы об остатках.

Обратный элемент числа a по модулю m — это a⁻¹, для которого a · a⁻¹ ≡ 1 (mod m). Он существует тогда и только тогда, когда НОД(a, m) = 1.

Зачем это в олимпиадах

Числа сочетаний по модулю, вероятности в виде несократимых дробей p/q mod M, формулы с делением — всё это требует деления по модулю. А делить по модулю можно только умножая на обратный элемент. Без этого навыка задачи на комбинаторику по простому модулю просто не решаются. Китайская теорема об остатках (КТО) — следующий уровень: она склеивает ответы по нескольким модулям в один и применяется, когда нужный модуль составной или когда восстанавливают число по остаткам.

Почему деление — это умножение на обратный

В обычной арифметике a / b = a · b⁻¹, где b⁻¹ = 1/b. По модулю дробей нет, но есть аналог единицы: число b⁻¹, дающее b · b⁻¹ ≡ 1. Тогда «деление на b» — это умножение на b⁻¹. Существование обратного завязано на взаимную простоту: если НОД(b, m) = 1, по соотношению Безу найдутся x, y с b·x + m·y = 1, откуда b·x ≡ 1 (mod m) — значит x и есть обратный. Если же НОД(b, m) > 1, обратного не существует.

Способ 1: по малой теореме Ферма (модуль простой)

Когда модуль p — простое (а в задачах это почти всегда 10⁹+7 или 998244353), обратный считается одной строкой через быстрое возведение: a⁻¹ ≡ a^p−2 (mod p). Это прямое следствие a^p−1 ≡ 1.

MOD = 10**9 + 7   # простой модуль

def inverse_fermat(a, p):
    return pow(a, p - 2, p)

inv3 = inverse_fermat(3, MOD)
print(inv3)
print(3 * inv3 % MOD)        # проверка: должно быть 1

# деление по модулю: (a / b) mod p = a * b^(-1) mod p
a, b = 10, 4
print(a * inverse_fermat(b, MOD) % MOD)   # 10/4 = 2.5 -> представление дроби по модулю

Вывод:

333333336
1
500000006

Последнее число 500000006 — это «2.5 по модулю 10⁹+7»: такое x, что 4x ≡ 10 (mod p). Дробь 10/4 = 5/2 представляется целым остатком. Именно так выводят ответы-вероятности в формате «несократимая дробь по модулю».

Способ 2: через расширенный Евклид (модуль любой)

Если модуль не обязательно простой (но НОД(a, m) = 1), Ферма неприменим, а расширенный Евклид — работает всегда. Находим x в a·x + m·y = 1; тогда x mod m — обратный.

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def inverse_egcd(a, m):
    g, x, _ = ext_gcd(a, m)
    if g != 1:
        return None          # обратного не существует
    return x % m             # приводим к [0, m)

print(inverse_egcd(3, 11))       # обратный к 3 по модулю 11
print(3 * inverse_egcd(3, 11) % 11)
print(inverse_egcd(6, 9))        # НОД(6,9)=3 != 1 -> обратного нет
print(inverse_egcd(10, 17))      # составной a, простой m

Вывод:

4
1
None
12

Расширенный Евклид честно вернул None для пары (6, 9): их НОД равен 3, обратного нет. Этот способ универсальнее Ферма (работает для составного модуля), но Ферма короче, когда модуль точно простой. На практике держите в голове оба.

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

КТО: если модули m₁, …, mₖ попарно взаимно просты и M = m₁·…·mₖ, то система сравнений x ≡ aᵢ (mod mᵢ) имеет единственное решение по модулю M.

Интуиция: набор остатков (a₁, …, aₖ) по взаимно простым модулям — это уникальный «адрес» числа в диапазоне [0, M). Разные числа в этом диапазоне дают разные наборы остатков, и каждый набор кому-то соответствует. Конструктивная формула: x ≡ ∑ aᵢ · Mᵢ · Nᵢ (mod M), где Mᵢ = M / mᵢ, а Nᵢ = Mᵢ⁻¹ mod mᵢ. Каждое слагаемое равно aᵢ по своему модулю и нулю по остальным.

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def crt(remainders, moduli):
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for a_i, m_i in zip(remainders, moduli):
        Mi = M // m_i
        _, inv, _ = ext_gcd(Mi % m_i, m_i)
        x += a_i * Mi * (inv % m_i)
    return x % M, M

# x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
x, M = crt([2, 3, 2], [3, 5, 7])
print(x, M)
print(x % 3, x % 5, x % 7)   # проверка остатков

Вывод:

23 105
2 3 2

Классическая задача Сунь-цзы: число даёт остатки 2, 3, 2 по модулям 3, 5, 7 — это 23, и оно единственно в диапазоне [0, 105). КТО полезна, когда прямой модуль велик или составной: считают ответ по нескольким простым модулям и склеивают.

Разбор задачи: массовое обращение за один pow

Если нужно обратить много чисел по модулю (частая ситуация при подсчёте сочетаний для разных знаменателей), вызывать pow(a, p-2, p) для каждого — дорого. Есть приём «обращение пачкой» (batch inversion): через префиксные произведения он обращает n чисел всего одним возведением в степень и O(n) умножениями. Идея: посчитать произведение всех, обратить его один раз, а индивидуальные обратные «вытащить» обратным проходом — ровно как мы делали с обратными факториалами.

MOD = 10**9 + 7

def batch_inverse(nums, mod):
    n = len(nums)
    prefix = [1] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] * nums[i] % mod
    inv_total = pow(prefix[n], mod - 2, mod)   # единственный pow
    res = [0] * n
    for i in range(n - 1, -1, -1):
        res[i] = inv_total * prefix[i] % mod    # обратный к nums[i]
        inv_total = inv_total * nums[i] % mod
    return res

nums = [3, 7, 11, 13]
invs = batch_inverse(nums, MOD)
print([a * inv % MOD for a, inv in zip(nums, invs)])   # все должны быть 1
print(invs[0] == pow(3, MOD - 2, MOD))                  # совпадает с прямым

Вывод:

[1, 1, 1, 1]
True

Все произведения a·a⁻¹ равны 1 — обратные найдены верно, и первый совпал с прямым вычислением по Ферма. При этом возведение в степень выполнено один раз вместо четырёх. На больших наборах (десятки тысяч чисел) экономия колоссальна: O(n) умножений плюс один pow вместо n логарифмических возведений. Этот приём — стандарт в задачах, где знаменателей много.

Подводные камни

Обратного может не быть. Только при НОД(a, m) = 1. Ферма вдобавок требует простого m и a не кратного m.
Деление нуля. Если в дроби p/q знаменатель кратен модулю, обратного нет — задача требует иной модели.
КТО требует попарной взаимной простоты. Для не взаимно простых модулей формула не работает (нужна обобщённая версия с проверкой совместности).
Знак из Евклида. x бывает отрицательным; всегда берите x % m.

Итог

Деление по модулю = умножение на обратный; обратный существует при НОД(a, m) = 1.
Модуль простой → a⁻¹ = a^p−2 mod p (Ферма + быстрая степень).
Модуль любой (взаимно простой с a) → обратный через расширенный Евклид.
КТО: попарно взаимно простые модули задают число однозначно по модулю их произведения.