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:

Therefore,

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:

Therefore,

Since we are working modulo mod, the value mod is congruent to 0, so:

Now multiply both sides by $$$inv(mod\%x)$$$ $$$\big($$$ We know that $$$(mod \% x) * inv(mod \% x) \equiv 1 \pmod{mod}\big)$$$:

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:

But $$$x^{-1}$$$ is exactly the modular inverse of x, so this gives us:

Of course we want a non-negative value, so instead of returning the negative number directly, we add 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 inv(1) = 1.

The complexity is $$$O(\log mod)$$$, similar to the first solution, but the implementation is much shorter than binary exponentiation.