Обратный по модулю
Обратным по модулю для числа $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$$
А дальше решить как диофантово уравнение.