Modular Inverse
Undo multiplication modulo m when the gcd condition allows it, and choose the right inverse routine for the modulus.
Modular Inverse
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
A modular inverse is the number that undoes multiplication modulo \(m\). It appears everywhere once modular arithmetic stops being a toy: dividing by factorials, normalizing transitions, solving congruences, and implementing formulas that look rational but are really modular.
When to Use It
Use a modular inverse when:
a formula under modulo arithmetic needs division,
you need to solve \(ax \equiv b \pmod m\),
factorial inverses or combinatorics tables are involved.
Core Idea
The inverse of \(a\) modulo \(m\) is a value \(a^{-1}\) such that \[ a \cdot a^{-1} \equiv 1 \pmod m. \] It exists iff \(\gcd(a, m) = 1\).
There are two common ways to compute it:
extended Euclid for a general modulus,
fast exponentiation \(a^{m-2}\) when \(m\) is prime.
Key Insight
``Division modulo \(m\)'' is not automatic. It is multiplication by an inverse, and that only makes sense when the number is coprime with the modulus.
Operations / Main Technique
inverse by extended Euclid for arbitrary coprime \((a, m)\),
inverse by Fermat's little theorem for prime \(m\),
batch inverse tables when many inverses under one prime modulus are needed.
Worked example.
Modulo \(11\), the inverse of \(3\) is \(4\) because \(3 \cdot 4 = 12 \equiv 1 \pmod{11}\).
Correctness Intuition
Extended Euclid returns coefficients \(x, y\) such that \[ ax + my = \gcd(a, m). \] When the gcd is \(1\), reducing modulo \(m\) gives \(ax \equiv 1 \pmod m\), so \(x\) is the inverse.
For prime moduli, Fermat gives \(a^{m-1} \equiv 1\), so \(a^{m-2}\) is the inverse.
Complexity Analysis
inverse by extended Euclid: \(O(\log m)\),
inverse by fast power: \(O(\log m)\),
build inverse table \(1 \ldots n\) under prime modulus: \(O(n)\).
Implementation
The code includes both the general and prime-modulus versions. I prefer keeping both because contest moduli vary, and assuming primality when it is not given is a common bug.
Common Pitfalls
Trying to invert a value that is not coprime to the modulus.
Using \(a^{m-2}\) when the modulus is not prime.
Forgetting to normalize the extended-Euclid result into \([0, m-1]\).
Dividing under modulo arithmetic before taking the modulo safely.
Variants / Extensions
Precompute factorials and inverse factorials.
Solve linear congruences and CRT systems.
Inverse tables for repeated combinatorics queries.
Practice Problems
Compute binomial coefficients modulo a prime.
Solve \(ax \equiv b \pmod m\).
Evaluate rational-looking formulas modulo a large prime.
References
Code
Contest-ready reference implementation for the idea explained above.
long long mod_pow(long long a, long long e, long long mod) {
long long result = 1 % mod;
a %= mod;
while (e > 0) {
if (e & 1) {
result = (__int128)result * a % mod;
}
a = (__int128)a * a % mod;
e >>= 1;
}
return result;
}
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
long long mod_inverse_general(long long a, long long mod) {
long long x, y;
long long g = ext_gcd(a, mod, x, y);
if (g != 1) {
return -1;
}
x %= mod;
if (x < 0) x += mod;
return x;
}
long long mod_inverse_prime(long long a, long long mod) {
return mod_pow(a, mod - 2, mod);
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.