Обратный по любому модулю в 2 строчки

Реализация

Сначала приведем реализацию, а потом уже поймем, почему она работает:

1 def rev(a, m):
2     if a == 1: return 1
3     return (1 - rev(m % a, a) * m) / a + m

Идея

Первый случай очевиден. Во втором случае проверим правильность формулы: $1 - rev(m \% a, a) \cdot m$ делится на $a$, так как $rev(m \% a, a)$ — обратный к $m$ по модулю $a$. При этом $\frac{rev(m \% a, a) \cdot m}{a}$ делится на $m$, так что итоговое выражение сравнимо с $\frac{1}{a}$ по модулю $m$. Почему ответ всегда будет получаться именно в диапазоне от $0$ до $m - 1$, мы оставим читателю в качестве упражнения.

Асимптотика алгоритма $O(\log m)$, потому что он эквивалентен Алгоритму Евклида по вызовам рекурсии.

Автор конспекта: Егор Горбачев

По всем вопросам пишите в telegram @Peltorator