Modular Inverse

$a^{-1}\mathrm{mod}m$ is the value $x$ with $ax\equiv 1(\mathrm{mod}m)$. It exists iff $\gcd (a,m)=1$.

The three methods

1. Fermat’s little theorem — $m$ prime

$a^{-1}\equiv a^{m-2}(\mathrm{mod}m).$

long long inv(long long a, long long m) { return powmod(a % m, m - 2, m); }

$O(\log m)$. The default when the modulus is a prime like $10^9+7$ or $998244353$.

2. Extended Euclid — any coprime $m$

$ax+my=1⟹x\equiv a^{-1}.$

long long inv(long long a, long long m) {
    long long x, y;
    if (extgcd(a, m, x, y) != 1) return -1;      // no inverse
    return (x % m + m) % m;
}

$O(\log m)$, works for composite $m$, and is slightly faster than modpow. See Extended Euclidean.

3. Euler’s theorem — any coprime $m$

$a^{-1}\equiv a^{\phi (m)-1}(\mathrm{mod}m).$

Requires factoring $m$ to compute $\varphi(m)$, so use extended Euclid instead unless $\phi (m)$ is already known.

Batch computation

All inverses $\mathrm{1..}n$ modulo a prime — $O(n)$

$\mathrm{inv}[i]=-\lfloor \frac{m}{i}\rfloor \cdot \mathrm{inv}[m\mathrm{mod}i]\mathrm{mod}m.$

vector<long long> inv(n + 1);
inv[1] = 1;
for (int i = 2; i <= n; i++)
    inv[i] = (m - (m / i) * inv[m % i] % m) % m;

Derivation: write $m=qi+r$ with $q=\lfloor m/i\rfloor$, $r=m\mathrm{mod}i$. Then $qi+r\equiv 0$, so $i\equiv -r/q$, hence $i^{-1}\equiv -q{r}^{-1}$.

Essential for precomputing inverse factorials in $O(n)$ rather than $O(n\log m)$.

Inverses of $n$ arbitrary values — one modpow

Compute prefix products $p_i=a_1\cdots a_i$, invert only $p_n$, then walk backwards:

vector<long long> batchInverse(vector<long long>& a, long long m) {
    int n = a.size();
    vector<long long> pref(n + 1, 1), res(n);
    for (int i = 0; i < n; i++) pref[i+1] = pref[i] * a[i] % m;
    long long cur = powmod(pref[n], m - 2, m);
    for (int i = n - 1; i >= 0; i--) { res[i] = cur * pref[i] % m; cur = cur * a[i] % m; }
    return res;
}

$O(n+\log m)$ instead of $O(n\log m)$ — a genuinely useful trick when inverses appear inside a hot loop.

Inverse factorials

fact[0] = 1;
for (int i = 1; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
invFact[N] = powmod(fact[N], MOD - 2, MOD);
for (int i = N; i > 0; i--) invFact[i-1] = invFact[i] * i % MOD;   // one modpow total

Then $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\mathrm{fact}[n]\cdot \mathrm{invFact}[k]\cdot \mathrm{invFact}[n-k]$ in $O(1)$. See Combinatorics.

When the inverse does not exist

$\gcd (a,m)\ne 1$

Then $a$ has no inverse. Common causes: dividing by a multiple of the modulus, or a prime modulus with a numerator that happens to be a multiple of it (which makes the “fraction” genuinely $0$, not undefined).

Options when $\gcd (a,m)=g>1$:

• If $g\mid b$ in “solve $ax\equiv b$”, divide the whole congruence by $g$ (including the modulus) — see Linear Congruence.
• Factor out the shared primes and track their exponents separately. This is how $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathrm{mod}{p}^k$ and similar are computed.
• Use CRT to split a composite modulus into prime powers.

Division under a modulus, safely

$\frac{a}{b}\mathrm{mod}m=a\cdot b^{-1}\mathrm{mod}m,$
valid only when $\gcd (b,m)=1$. There is no “integer division” in modular arithmetic — $\lfloor a/b\rfloor \mathrm{mod}m$ is a completely different quantity and cannot be computed this way.

See also: Modular Arithmetic · Extended Euclidean · Linear Congruence