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

Обратным по модулю для числа $x$ по модулю $p$ называется такое число $x^{-1}$, что

$$x \cdot x^{-1} \equiv 1 \pmod {p}$$

Фактическая польза от обратного по модулю в том, что он заменяет деление. А именно, если нам в рамках вычислений хочется найти значение $\frac{A}{B} \pmod {p}$, то мы считаем это значение эквивалентным значению $A \cdot B^{-1} \pmod{p}$.

Чтобы найти обратное по модулю, есть несколько разных техник, но самая популярная --- теорема Эйлера:

Теорема Эйлера

$$a^{\phi(p) - 1} \equiv 1 \pmod{p}$$

Или это же выражение для простого модуля $p$ называется малой теоремой Ферма:

$$a^{p - 1} \equiv 1 \pmod{p}$$

Малую теорему Ферма можно достаточно просто доказать комбинаторно. Поставим другую задачу --- подсчет числа способов раскрасить $p$-угольник в $a$ цветов. Раскрасим каждую вершину в какой-то цвет. Всего таких раскрасок $a^p$. Заметим, что поскольку $p$ простое, то у всех раскрасок, кроме тех, где все раскрашено в один цвет поворотом получается ровно $p$ раскрасок. Значит всего различных раскрасок $\frac{a^p - a}{p} + a$. Это число должно быть целым, а значит $a^p - a$ делится на $p$, откуда $a^{p - 1} - 1 \equiv 0 \pmod {p}$.

Как теперь научиться делить? Все просто:

$$a^{p - 2} \equiv a^{p - 1} \cdot a^{-1} \equiv a^{-1} \pmod {p}$$

Значит, для простых $p$ достаточно посчитать $a^{p-2}$ с помощью быстрого возведения в степень

Диофантово уравнение

Альтернативный вариант --- свести уравнение $ax \equiv 1 \pmod{p}$ к диофантову уравнению $$ ax + py = 1$$

А дальше решить как диофантово уравнение.