An Easy Way to Find Modular InversesЛегкий способ находить Обратное число по модулю
Difference between en1 and ru1, changed 2349 character(s)
Maybe you are still using Fermat's Little Theorem to find inverses modulo a prime numberВозможно, вы всё ещё используете малую теорему Ферма, чтобы находить обратные элементы по модулю простого числа $p$.↵
==================↵
↵
IfЕсли `p` is prime and `x` is not divisible by `p`, then by Fermat's Little Theorem: — простое число и `x` не делится на `p`, то по малой теореме Ферма:↵
↵
$$x^{p-1}\equiv 1\pmod p$$↵
↵
Therefore, Следовательно,↵
↵
$$x^{p-2}\equiv x^{-1}\pmod p$$↵
↵
So the usual way to find the modular inverse is to use binary exponentiationПоэтому стандартный способ найти обратный элемент — использовать бинарное возведение в степень:↵
 ↵
~~~~~↵
int binpow(int a, int n) {↵
    int res = 1;↵
    while (n) {↵
        if (n&1) res = 1LL * res * a % mod;↵
        a = 1LL * a * a % mod;↵
        n >>= 1;↵
    }↵
    return res;↵
}↵
int inv(int x) {↵
    return binpow(x, mod - 2);↵
}↵
~~~~~↵
This works perfectly fine. But for such a common operation, it is nice to have something shorter.↵
==================↵
↵
For example, we can write the modular inverse like this↵
Этот способ отлично работает. Но для такой частой операции хочется иметь что-то короче.↵
==================↵
↵
Например, обратный элемент можно записать так:↵
↵
~~~~~↵
int inv(int x) {↵
    return x == 1 ? 1 : mod - 1LL * (mod / x) * inv(mod % x) % mod;↵
}↵
~~~~~↵
↵
Now let's prove why this formula works.↵
↵
First, write `mod` using division with remainderТеперь докажем, почему эта формула работает.↵
↵
Сначала запишем `mod` через деление с остатком:↵
↵
$$mod = (mod / x) * x + mod \% x$$↵
↵
ThereforeСледовательно,↵
↵
$$mod \% x = mod - (mod / x) * x$$↵
↵
Since we are working modulo `mod`, the value `mod` is congruent to `0`, soТак как мы работаем по модулю `mod`, значение `mod` сравнимо с `0`, поэтому:↵
↵
$$mod \% x\equiv -(mod/x) * x \pmod{mod}$$↵
↵
Now multiply both sides byТеперь умножим обе части на $inv(mod\%x)$ $\big($ We know thatмы знаем, что $(mod \% x) * inv(mod \% x) \equiv 1 \pmod{mod}\big)$:↵
↵
$$1\equiv -(mod / x) * x * inv(mod \% x) \pmod{mod}$$↵
↵
Since `mod` is prime and `x` is not divisible by `mod`, division by `x` is valid modulo `mod`.↵
↵
Dividing both sides by `x`, we getТак как `mod` — простое число и `x` не делится на `mod`, то деление на `x` корректно по модулю `mod`.↵
↵
Разделив обе части на `x`, получаем:↵
↵
$$x^{-1} \equiv -(mod / x) * inv(mod \% x) \pmod{mod}$$↵
↵
ButНо $x^{-1}$ is exactly the modular inverse of `x`, so this gives us— это обратный элемент к `x`, поэтому:↵
↵
$$inv(x) \equiv -(mod / x) * inv(mod \% x) \pmod{mod}$$↵
↵
Of course we want a non-negative value, so instead of returning the negative number directly, we addКонечно, мы хотим получить неотрицательное значение, поэтому вместо того, чтобы возвращать отрицательное число напрямую, добавим `mod`: ↵
↵
$$inv(x) \equiv mod - (mod / x) * inv(mod \% x) \pmod{mod}$$↵
↵
So we have derived the recursive formulaТак мы получили рекурсивную формулу:↵
↵
~~~~~↵
int inv(int x) {↵
    return x == 1 ? 1 : mod - 1LL * (mod / x) * inv(mod % x) % mod;↵
}↵
~~~~~↵
↵
The recursion stops at `x = 1` becauseРекурсия останавливается при `x = 1`, потому что `inv(1) = 1`.↵
↵
The complexity is $O(\log mod)$, similar to the first solution, but the implementation is much shorter than binary exponentiationСложность — $O(\log mod)$, как и в первом решении, но реализация получается гораздо короче, чем бинарное возведение в степень.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian Forestmy17 2026-04-28 22:40:00 2 Мелкая правка: '%x)$ $\big($мы знаем, ' -> '%x)$ $\big ($ мы знаем, '
ru1 Russian Forestmy17 2026-04-28 22:38:24 2349 Первая редакция перевода на Русский
en1 English Forestmy17 2026-04-28 22:31:56 2269 Initial revision (published)