vault

Modular Inverse

24 min read

Modular Inverse

The modular multiplicative inverse of an integer a modulo a positive integer m is the integer a⁻¹ (also written a^(-1) mod m) in the range [0, m) such that a · a⁻¹ ≡ 1 (mod m). It exists if and only if a and m are coprime — gcd(a, m) = 1. Two algorithms compute it: the extended Euclidean algorithm, which produces Bézout coefficients (s, t) with s · a + t · m = 1 so that s mod m = a⁻¹, working for any modulus where the inverse exists; and Fermat’s little theorem, which says that for prime p and a not divisible by p, a^(p-2) ≡ a⁻¹ (mod p), computed via Fast Exponentiation in O(log p) modular multiplications. Modular inverses are the foundation of every operation that “divides” under Modular Arithmetic — RSA decryption (the private exponent is the inverse of the public exponent modulo Euler’s totient), Diffie-Hellman computations, the Chinese Remainder Theorem reconstruction, binomial coefficients nCr mod p via precomputed inverse factorials, and rational-number arithmetic over a prime field. This note works through both algorithms with proofs, traces concrete numbers step by step, compares the two methods (when each is preferred), and catalogs the pitfalls — most prominently, that the inverse simply does not exist when gcd(a, m) > 1, which surprisingly often surfaces as a silent bug.

1. Intuition — “Undoing” Multiplication in a Wrap-Around World

In ordinary arithmetic, dividing by a is the same as multiplying by 1/a. The problem with modular arithmetic is that 1/a is generally not an integer — 1/3 is not in ℤ — so we cannot just divide. Instead, we ask: is there an integer x in [0, m) such that multiplying by x “undoes” multiplication by a, modulo m? That is, a · x ≡ 1 (mod m). If yes, that x is the modular inverse. Multiplying by x plays the role of dividing by a in the modular world.

A clock-arithmetic analogy: on a 7-hour clock, “tripling” is one mapping (hour → 3 · hour mod 7). Is there a “third-ing” that reverses it? Try hour → 5 · hour mod 7. Tripling 2 gives 6 (6 mod 7), and “third-ing” 6 gives 5 · 6 = 30 ≡ 2 (mod 7). So 5 is the modular inverse of 3 modulo 7. The pair (3, 5) “cancels” mod 7 because 3 · 5 = 15 = 2·7 + 1 ≡ 1 (mod 7).

The key structural fact: when m is prime, every nonzero integer has an inverse — the integers mod a prime form a field (the Galois field GF(p)), where division (other than by zero) is always well-defined. When m is composite, only the integers coprime to m have inverses; the others are “zero divisors” in the ring ℤ/mℤ. For example, mod 6, the element 2 has no inverse: try 2·1 = 2, 2·2 = 4, 2·3 = 0, 2·4 = 2, 2·5 = 4 — none of these is 1. The reason is that gcd(2, 6) = 2 ≠ 1; any product 2x mod 6 is even, never 1.

2. Existence — gcd(a, m) = 1 Is Necessary and Sufficient

Theorem. The modular inverse a⁻¹ mod m exists if and only if gcd(a, m) = 1.

Proof.

(⇐ existence when coprime) Suppose gcd(a, m) = 1. By Bézout’s identity (see GCD and Extended Euclidean §7), there exist integers s, t with s · a + t · m = 1. Reducing both sides modulo m: s · a + 0 ≡ 1 (mod m), i.e., s · a ≡ 1 (mod m). So s mod m is an inverse.

(⇒ no inverse when not coprime) Suppose gcd(a, m) = g > 1. For any integer x, the product a · x is a multiple of g (since g | a). Reducing mod m, the residue a · x mod m is also a multiple of g (since g | m). But 1 is not a multiple of g (because g > 1), so a · x ≢ 1 (mod m) for any x. No inverse exists.

The converse direction is what makes “modular inverse” subtle: many off-the-cuff implementations simply return some number when the inverse doesn’t exist, instead of erroring. Always check, or use a library that errors (Python’s pow(a, -1, m) raises ValueError since 3.8).

Uniqueness. When the inverse exists, it is unique in [0, m). If s · a ≡ 1 and s' · a ≡ 1, then (s - s') · a ≡ 0 (mod m), so m | (s - s') · a. Since gcd(a, m) = 1, m | (s - s') (Euclid’s lemma), so s ≡ s' (mod m).

3. Tiny Worked Example — 3⁻¹ mod 11

We want x ∈ [0, 11) with 3 · x ≡ 1 (mod 11).

Brute force. Try x = 1, 2, 3, …:

3·1 = 3   mod 11 = 3
3·2 = 6   mod 11 = 6
3·3 = 9   mod 11 = 9
3·4 = 12  mod 11 = 1   ← found

So 3⁻¹ mod 11 = 4. Verify: 3 · 4 = 12 = 11 + 1 ≡ 1 (mod 11). ✓

Brute force takes O(m) time. For m = 10⁹, this is infeasible. The two methods below run in O(log m).

Method 1 — Extended Euclidean. Find s, t with s · 3 + t · 11 = 1.

a = 3, b = 11
extended_gcd(3, 11):
  Step 0: q = 3 // 11 = 0,    a, b → 11, 3       old_s, s → 0, 1     old_t, t → 1, 0
  Step 1: q = 11 // 3 = 3,    a, b → 3, 2        old_s, s → 1, -3    old_t, t → 0, 1
  Step 2: q = 3 // 2 = 1,     a, b → 2, 1        old_s, s → -3, 4    old_t, t → 1, -1
  Step 3: q = 2 // 1 = 2,     a, b → 1, 0        old_s, s → 4, -11   old_t, t → -1, 3
  return (g=1, s=4, t=-1)

Check: 4 · 3 + (-1) · 11 = 12 - 11 = 1. ✓ The inverse is s mod 11 = 4 mod 11 = 4. ✓

Method 2 — Fermat’s Little Theorem. Since 11 is prime and gcd(3, 11) = 1, 3⁻¹ ≡ 3^(11-2) = 3⁹ (mod 11).

Compute 3⁹ mod 11 via repeated squaring (9 = 1001₂):

3¹  =  3
3²  =  9
3⁴  =  81  mod 11 = 4
3⁸  =  16  mod 11 = 5
3⁹ = 3⁸ · 3¹ = 5 · 3 = 15 mod 11 = 4

Same answer: 4. Both methods agree, as they must.

4. The Algorithm — Two Methods, Two Pseudocodes

4.1 Method 1 — Extended Euclidean

The extended Euclidean algorithm computes (g, s, t) with s · a + t · m = g = gcd(a, m). If g = 1, then s mod m is the inverse; otherwise no inverse exists.

modinv_extended(a, m):
    g, s, t := extended_gcd(a mod m, m)
    if g != 1:
        raise "no inverse: gcd(a, m) > 1"
    return s mod m

The recursive extended_gcd (covered in GCD and Extended Euclidean §3.3-3.4):

extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)             # base: gcd(a, 0) = a, with a*1 + 0*0 = a
    g, s1, t1 := extended_gcd(b, a mod b)
    return (g, t1, s1 - (a // b) * t1)

The iterative form (more common in production):

extended_gcd_iter(a, b):
    old_s, s := 1, 0
    old_t, t := 0, 1
    while b != 0:
        q := a // b
        a, b := b, a - q*b
        old_s, s := s, old_s - q*s
        old_t, t := t, old_t - q*t
    return (a, old_s, old_t)

4.2 Method 2 — Fermat’s Little Theorem (Prime Modulus Only)

Fermat’s Little Theorem (Pierre de Fermat, 1640, in a letter to Frénicle de Bessy). If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p).

A short proof: the integers {1, 2, …, p-1} form a group under multiplication mod p (the multiplicative group of GF(p)). Multiplying every element by a permutes this group (because a is invertible). So the product 1 · 2 · … · (p-1) equals (a · 1)(a · 2) … (a · (p-1)) = a^(p-1) · (p-1)! modulo p. Cancel (p-1)! (which is coprime to p by Wilson’s theorem, since each factor is coprime to p) to get 1 ≡ a^(p-1) (mod p).

Corollary. Multiplying both sides by a⁻¹: a^(p-2) ≡ a⁻¹ (mod p).

So when p is prime, the inverse is computed by modular exponentiation:

modinv_fermat(a, p):
    return pow(a, p-2, p)            # uses fast exponentiation

This is one line, but only valid for prime p (and a ≢ 0 (mod p)). For composite m, Euler’s theorem generalizes Fermat’s: if gcd(a, m) = 1, then a^(φ(m)) ≡ 1 (mod m), so a⁻¹ ≡ a^(φ(m) - 1) (mod m). The catch: computing the totient φ(m) requires factoring m. For m whose factorization is unknown (e.g., RSA modulus n = p·q), Euler is not useful — extended Euclidean wins.

5. Python Implementation

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Iterative extended Euclidean. Returns (gcd, s, t) with s*a + t*b = gcd."""
    old_s, s = 1, 0
    old_t, t = 0, 1
    while b != 0:
        q = a // b
        a, b = b, a - q * b
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    if a < 0:
        return (-a, -old_s, -old_t)
    return (a, old_s, old_t)
 
 
def modinv_extended(a: int, m: int) -> int:
    """Modular inverse via extended Euclidean. Works for any modulus where gcd(a, m) = 1."""
    a = a % m
    g, s, _ = extended_gcd(a, m)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {m} (gcd = {g})")
    return s % m
 
 
def modinv_fermat(a: int, p: int) -> int:
    """Modular inverse mod a prime p, via Fermat's little theorem.
 
    Caller is responsible for ensuring p is prime and a % p != 0.
    """
    if a % p == 0:
        raise ValueError(f"{a} ≡ 0 (mod {p}); no inverse")
    return pow(a, p - 2, p)
 
 
def modinv_builtin(a: int, m: int) -> int:
    """Python 3.8+ builtin: pow(a, -1, m). Raises ValueError if no inverse."""
    return pow(a, -1, m)
 
 
def precompute_inv_factorials(n_max: int, p: int) -> tuple[list[int], list[int]]:
    """For nCr mod prime queries: O(n_max) precompute; O(1) per query.
 
    Uses inv_fact[k] = inv_fact[k+1] * (k+1) mod p, propagating from the top.
    Only one Fermat inverse call is needed (at the top); the rest fall out by recurrence.
    """
    fact = [1] * (n_max + 1)
    for i in range(1, n_max + 1):
        fact[i] = (fact[i - 1] * i) % p
    inv_fact = [1] * (n_max + 1)
    inv_fact[n_max] = pow(fact[n_max], p - 2, p)        # Fermat once
    for i in range(n_max - 1, -1, -1):
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % p
    return fact, inv_fact
 
 
def binomial_mod(n: int, k: int, p: int, fact, inv_fact) -> int:
    """C(n, k) mod prime p, in O(1) given precomputed tables."""
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % p * inv_fact[n - k] % p
 
 
# Demonstrations
if __name__ == "__main__":
    assert modinv_extended(3, 11) == 4
    assert modinv_fermat(3, 11) == 4
    assert modinv_builtin(3, 11) == 4
    # Composite modulus: extended works, Fermat must not be used
    assert modinv_extended(7, 26) == 15        # 7*15 = 105 = 4*26 + 1
    # No inverse: gcd(6, 9) = 3
    try:
        modinv_extended(6, 9)
        assert False, "should have raised"
    except ValueError:
        pass
    # nCr precompute demo
    p = 10**9 + 7
    fact, inv_fact = precompute_inv_factorials(100, p)
    assert binomial_mod(10, 3, p, fact, inv_fact) == 120
    assert binomial_mod(20, 10, p, fact, inv_fact) == 184756

Python 3.8+ provides pow(a, -1, m) directly, implemented in C and using the binary extended Euclidean variant under the hood. It is the recommended one-liner unless you have a teaching or portability reason to write the algorithm explicitly.

6. Complexity

6.1 Extended Euclidean

extended_gcd(a, m) runs in O(log min(a, m)) iterations by Lamé’s theorem (1844) — the worst case is consecutive Fibonacci numbers. Each iteration does one division, one subtraction, and a few multiplications on the coefficient registers. For machine-word integers, the total cost is O(log m) arithmetic operations — typically a few dozen for 64-bit m. For arbitrary-precision integers of bit length b, each operation costs up to O(b²) (schoolbook) or O(b log b log log b) with FFT-based multiplication, giving total O(b² log b) or O(b · log² b · log log b). For RSA-scale moduli (~2048 bits), this is microseconds on modern hardware.

6.2 Fermat

pow(a, p-2, p) does O(log p) modular multiplications via Fast Exponentiation. Each modular multiplication is O((log p)²) bit operations with schoolbook arithmetic. Total: O((log p)³) bit operations. For machine-word p, that is hundreds of cycles.

6.3 Comparison — Which Is Faster?

In raw operation count, extended Euclidean is faster than Fermat by a factor of roughly log p — Fermat does Θ(log p) modular multiplications, each costing more than the divisions of Euclidean. Knuth TAOCP Vol. 2 §4.5.2 discusses this in detail. In practice on 64-bit hardware, both are sub-microsecond for typical moduli; the wall-clock difference is dwarfed by I/O. For RSA-scale moduli, Fermat is about 1.5–2× slower than extended Euclidean.

But Fermat has a simplicity advantage: it is one line of code, and reuses the modular-exponentiation primitive that you almost certainly already have. In competitive programming, where mod is almost always a fixed prime (10⁹ + 7), Fermat is the de-facto standard precisely for this brevity.

6.4 When to Use Which

SituationMethodWhy
Modulus is primeEither; Fermat is shorterOne line: pow(a, p-2, p)
Modulus is composite (and factorization unknown, e.g., RSA n = p·q)Extended EuclideanFermat doesn’t apply; Euler needs φ(m) which requires factoring
Modulus is composite (factorization known)Extended EuclideanFaster than Euler with φ(m)
Many inverses against one prime modulusPrecompute factorial inverses, propagate via recurrenceOne Fermat call total, then O(1) per query
Inverse of an arbitrary a against a small m, one-offpow(a, -1, m) builtinPython 3.8+, simplest
Very large modulus, performance criticalExtended Euclidean (binary GCD variant)Avoids modular multiplications; smaller constant

The takeaway: default to extended Euclidean for general code; reach for Fermat when the modulus is provably prime and you want a one-liner.

7. Why It Works — Two Proofs

7.1 Extended Euclidean Correctness

Extended Euclidean returns (g, s, t) with s · a + t · m = g. When g = 1, this means s · a + t · m = 1. Reducing modulo m: s · a ≡ 1 (mod m). So s mod m is an inverse of a. The complete proof of extended Euclidean’s invariant — that s · a₀ + t · m₀ = a and s' · a₀ + t' · m₀ = b are maintained at every step — is in GCD and Extended Euclidean §3.3.

7.2 Fermat’s Little Theorem Correctness

We sketched the proof in §4.2. A more detailed version: consider the multiplicative group (ℤ/pℤ)* = {1, 2, …, p-1} under multiplication mod p. This is a group of order p - 1. For any a ∈ (ℤ/pℤ)*, the order of a (the smallest k > 0 with a^k ≡ 1) divides p - 1 by Lagrange’s theorem on subgroups. So a^(p-1) ≡ 1 (mod p), hence a · a^(p-2) ≡ 1, so a^(p-2) is the inverse.

This is a special case of Euler’s theorem: for any modulus m and any a coprime to m, a^(φ(m)) ≡ 1 (mod m), where φ(m) is the count of integers in [1, m] coprime to m. When m = p is prime, φ(p) = p - 1, recovering Fermat. The proof for general m uses the same “permutation” argument applied to (ℤ/mℤ)* (the group of units mod m).

8. The Killer Applications

8.1 Binomial Coefficients nCr mod p

Computing nCr = n! / (r! · (n-r)!) mod p requires modular inverses of factorials. The standard idiom precomputes fact[i] = i! mod p and inv_fact[i] = (i!)⁻¹ mod p in O(n_max) time, then each nCr query is O(1):

nCr mod p = fact[n] · inv_fact[r] · inv_fact[n-r] mod p

The clever part: inv_fact[k] for all k need only one expensive inverse computation. Compute inv_fact[n_max] = pow(fact[n_max], p-2, p) (Fermat), then propagate downward via the identity:

inv_fact[k] = inv_fact[k+1] · (k+1) mod p

(because inv_fact[k+1] = 1 / (k+1)! = 1 / ((k+1) · k!) = (1/(k+1)) · (1/k!), so multiplying by (k+1) gives 1/k! = inv_fact[k]). This propagation is O(n_max) modular multiplications. Total preprocessing: O(n_max + log p), per query O(1). This is the workhorse of competitive-programming combinatorics.

8.2 RSA Decryption

In RSA (Rivest, Shamir, Adleman 1978), the public key is (n, e) where n = p · q for two large primes, and the private key is d = e⁻¹ mod φ(n), where φ(n) = (p-1)(q-1). Encryption: c = m^e mod n. Decryption: m = c^d mod n. The correctness depends on e · d ≡ 1 (mod φ(n)), computed via extended Euclidean during key generation.

The security depends on the difficulty of computing d without knowing the factorization n = p · q — which would let one compute φ(n) and invert e. Since factoring large n is believed to be hard (no known polynomial-time algorithm), d is hidden. Crucially, Fermat’s little theorem inverse does NOT work for RSA’s modulus because n is composite; extended Euclidean (with φ(n) known to the key-holder) is essential.

8.3 Chinese Remainder Theorem Reconstruction

To solve x ≡ aᵢ (mod mᵢ) for pairwise coprime mᵢ, the formula is x = Σ aᵢ · Mᵢ · yᵢ (mod M) where M = Π mᵢ, Mᵢ = M / mᵢ, and yᵢ = Mᵢ⁻¹ (mod mᵢ). The inverse yᵢ is computed via extended Euclidean. See Chinese Remainder Theorem.

8.4 Rational Numbers Modulo a Prime

In competitive programming, fractions like 1/3 cannot be represented as integers — but 1/3 mod p can: it is pow(3, p-2, p) = modinv(3, p). Adding/subtracting/multiplying fractions modulo a prime is just integer arithmetic on these inverse representations. This trick lets DP solutions compute “expected value mod p” for problems like LeetCode’s “Knight Probability in Chessboard” if the answer is required as a rational.

8.5 Diffie-Hellman and ElGamal

While these crypto protocols don’t directly use modular inverse for encryption, the decryption in ElGamal computes m = c₂ · (c₁^x)⁻¹ mod p, requiring an inverse. Diffie-Hellman key exchange and ElGamal both depend on the discrete-logarithm hardness and on the ability to invert efficiently when the secret is known.

9. Diagram — The Two Paths to a Modular Inverse

flowchart TD
  A["Want a⁻¹ mod m"] --> B{"gcd(a, m) = 1?"}
  B -->|no| Z["No inverse exists — raise error"]
  B -->|yes| C{"Is m prime?"}
  C -->|"yes (m = p prime)"| D["Method 2: Fermat\na⁻¹ ≡ a^(p-2) mod p\nvia fast exponentiation"]
  C -->|"no (m composite, or unknown)"| E["Method 1: Extended Euclidean\nFind s, t with s·a + t·m = 1\nReturn s mod m"]
  D --> F["Return result in [0, m)"]
  E --> F

What this diagram shows. The decision tree for choosing a modular-inverse algorithm. The first branch is existence: if gcd(a, m) ≠ 1, no inverse exists and we must error out. If the inverse exists, the second branch is modulus type: if m is prime, both methods work, and Fermat’s pow(a, p-2, p) is shorter to write; if m is composite or its primality is unknown, only extended Euclidean works (Fermat assumes a prime modulus). Both methods produce the same answer, in [0, m). The diagram makes explicit that Fermat is a strictly less general method — it requires both gcd = 1 and prime modulus, while extended Euclidean only requires gcd = 1. In practice the choice is often dictated by the problem: cryptography with composite moduli forces extended Euclidean; competitive programming with mod = 10⁹ + 7 makes Fermat ergonomic.

10. Variants

10.1 Modular Inverse via Binary GCD

Instead of using division (which is slow on some architectures), binary extended GCD uses subtraction and bit-shift only — see Stein’s algorithm (1967) extended with coefficient tracking. Faster on hardware lacking a fast divider; used in cryptographic libraries (OpenSSL’s BN_mod_inverse has both versions). Same asymptotic complexity, smaller constant.

10.2 Bulk Inverse — Montgomery’s Trick

To compute inverses of multiple integers a₁, a₂, …, aₙ against the same modulus, Montgomery’s trick computes them all using just one inverse and 3n multiplications, instead of n separate inverses. The idea: compute prefix products P_k = a₁ · a₂ · … · a_k mod m, take the inverse of P_n once, then back-propagate to recover each aᵢ⁻¹ via aᵢ⁻¹ = P_n⁻¹ · (Π_{j≠i} aⱼ). See batch inversion in elliptic-curve cryptography for the full method. A massive speedup in elliptic-curve double-and-add operations.

10.3 Modular Inverse Table for Small p

For prime p up to say 10⁶, precomputing inv[1..p-1] in O(p) time uses the recurrence

inv[i] = -(p / i) · inv[p mod i] mod p          (for i ≥ 2; inv[1] = 1)

This is faster than calling pow(i, p-2, p) for each i. The recurrence is derived from p = (p / i) · i + (p mod i) rearranged: (p mod i) = p - (p/i) · i, then take inverse: inv[p mod i] = -(p/i) · i⁻¹ mod p since p ≡ 0.

def precompute_inv(n_max: int, p: int) -> list[int]:
    """Compute inv[i] = i⁻¹ mod p for i in [1, n_max] in O(n_max) time."""
    inv = [0] * (n_max + 1)
    inv[1] = 1
    for i in range(2, n_max + 1):
        inv[i] = (-(p // i) * inv[p % i]) % p
    return inv

This is the fastest method when you need inverses of every small integer mod p.

10.4 Modular Inverse in Polynomial Rings

The same algorithm works for polynomials over a field: extended Euclidean on f(x), g(x) ∈ K[x] gives Bézout polynomials s(x) · f(x) + t(x) · g(x) = gcd(f, g). Used in Reed-Solomon decoding and in inverting elements of finite-field extensions GF(p^n).

11. Pitfalls

11.1 Inverse Doesn’t Exist When gcd(a, m) > 1

The most common bug. If you call pow(2, -1, 4) in Python, it raises ValueError: base is not invertible for the given modulus. Many homemade implementations don’t error; they return whatever extended Euclidean produces with g > 1, which is not an inverse. Always either trust the library to error, or check gcd(a, m) == 1 explicitly.

A common case where this surfaces: computing nCr mod m where m is composite (e.g., m = 10^9 + 1, not prime). The factorial r! may share factors with m, in which case (r!)⁻¹ doesn’t exist. The fix is Lucas’ theorem (for prime-power moduli) or splitting m into prime-power factors and using CRT — substantially more involved than the prime-modulus case.

11.2 Fermat Requires Prime Modulus AND a ≢ 0 (mod p)

a^(p-2) ≡ a⁻¹ (mod p) only when p is prime and a is not a multiple of p. If p is composite, the formula gives nonsense. If a ≡ 0 (mod p), a^(p-2) ≡ 0, which is not an inverse — 0 has no inverse, but the formula silently returns it. Always verify both preconditions in code that uses Fermat directly.

11.3 Off-By-One in Fermat Exponent

The exponent in Fermat’s formula is p - 2, not p - 1. Writing pow(a, p - 1, p) returns 1 (by Fermat’s theorem itself), not the inverse. Easy to mis-type at 3 a.m. of a contest.

11.4 Sign of the Bézout Coefficient

The extended Euclidean algorithm can return a negative s. To get a representative in [0, m), always do s % m at the end. In C-family languages, this requires the defensive form ((s % m) + m) % m (see Modular Arithmetic §6 on the negative-modulo divergence). Python’s % is already non-negative.

11.5 Confusing a⁻¹ with a⁻¹ mod m

The “modular inverse” is NOT the same as 1/a evaluated as a real number. 3⁻¹ mod 11 = 4 (an integer), not 0.333… (a real). Don’t write 1/a in code expecting modular semantics — use pow(a, -1, m) or extended Euclidean.

11.6 Inverse Modulo a Power of Two

For m = 2^k, the inverse of an odd integer a exists (since gcd(odd, 2^k) = 1) and can be computed in O(log k) Newton-iteration steps via the recurrence x ← x · (2 − a · x) mod 2^k. This is faster than extended Euclidean for very large k (e.g., 256-bit moduli 2^256) and is used in Montgomery multiplication. Pitfall: for even a, no inverse exists modulo any power of two.

11.7 Using pow(a, -1, m) Before Python 3.8

pow(a, -1, m) was added in Python 3.8. On older Pythons, you must implement extended Euclidean yourself, or use gmpy2.invert(a, m). Don’t assume the builtin is universally available.

11.8 Inverse of a Modular Exponentiation

(a^k)⁻¹ ≡ (a⁻¹)^k (mod m) — both forms are equal, but the second is sometimes written pow(a, -k, m) (Python 3.8+, where negative exponents are interpreted as inverse-then-power). Be aware of which form your problem expects; mathematically equivalent, computationally identical via Fermat or extended Euclidean.

11.9 Forgetting That the Inverse Is Not the Negation

a⁻¹ mod m is the multiplicative inverse, not the additive inverse. The additive inverse is (-a) mod m = m - a. Don’t confuse “negate” with “invert” — beginners sometimes write m - a and call it the modular inverse, which silently produces wrong answers.

12. Common Interview Problems

ProblemLeetCode # / SourceConnection
Modular inverse one-offwarm-upExtended Euclidean or Fermat
nCr mod p for many queriescompetitive standardPrecompute factorial + inverse-factorial tables
Number of Music PlaylistsLC 920Combinatorial DP with nCr mod p
Count Palindromic SubsequencesLC 730DP with answer mod 10⁹ + 7
RSA decryption / encryptioncrypto courseworkInverse of e mod φ(n) via extended Euclidean
Diffie-Hellman key exchangecrypto courseworkModular exponentiation; inverse on the receiving side
Solve a · x ≡ b (mod m)competitiveMultiply both sides by a⁻¹
Distribute Repeating IntegersLC 1655Bitmask DP with mod arithmetic
Count AnagramsLC 2514n! over factorials of letter counts, mod prime
New 21 GameLC 837DP with pow(p, n, mod)-style probabilities
Find Triangular Sum of an ArrayLC 2221Pascal’s-triangle reduction; equivalent to nCr mod 10
Knight ProbabilityLC 688Rational arithmetic mod prime via inverse
Ways to Make a Fair ArrayLC 1664nCr with parity constraint, mod prime

13. Open Questions

  • What is the practical cutoff where pow(a, -1, m) (binary extended Euclidean) outperforms Newton iteration for m = 2^k? For k below ~100, extended Euclidean is faster due to smaller constants; above that, Newton’s quadratic convergence dominates. Used in __gmpz_invert switching logic.
  • Is there a known sub-quadratic (in bit length) algorithm for modular inverse? Yes: the half-GCD algorithm reduces big-integer GCD to multiplication time, achieving O(M(n) log n) where M(n) is the cost of multiplication. Combined with extended GCD bookkeeping, the modular inverse for n-bit inputs is O(M(n) log n). This is theoretical; for practical sizes (RSA-2048), schoolbook extended Euclidean beats it.
  • How does modular inverse generalize to non-commutative rings (matrices)? The answer is “matrix inverse modulo m” — Gauss-Jordan elimination over ℤ/mℤ, which works iff the matrix’s determinant is coprime to m. Used in Hill cipher cryptanalysis and lattice-based cryptography.

14. See Also

Graph View

Backlinks