MathAlgorithmaka modular multiplicative inverse, Fermat inverse, inverse mod p

Modular Inverse

Find a^-1 mod m — the number that multiplies a to 1 — via Fermat's little theorem when m is prime or the extended Euclidean algorithm for any coprime m.

▶ VisualizePattern: Math & Number TheoryPractice (2)
Progress

Overview

The modular inverse of a modulo m is the residue x with a · x ≡ 1 (mod m). It exists iff gcd(a, m) = 1, and it is what "division" means in Modular Arithmetic: b / a ≡ b · a^-1. Example: 3 · 4 = 12 ≡ 1 (mod 11), so 3^-1 ≡ 4 (mod 11), and 5 / 3 ≡ 5 · 4 = 20 ≡ 9 (mod 11).

Two methods. Fermat (prime m only): by Fermat's little theorem a^(m-1) ≡ 1, so a^-1 ≡ a^(m-2), one call to Fast Exponentiation in O(log m). Extended Euclid (any m coprime to a): solve a·x + m·y = 1 with GCD (Euclidean Algorithm); then x mod m is the inverse. Euler's generalization a^(φ(m)-1) also works for composite m but needs φ(m), which requires factoring.

For many inverses at once, precompute: inverse factorials via invfact[n] = fact[n]^-1 and invfact[i-1] = invfact[i] · i (one exponentiation total), or all inverses 1..n via the recurrence inv[i] = -(m / i) · inv[m mod i] mod m in O(n) — the tools behind Combinatorics nCr tables.

modular inverseFermatextended Eucliddivision mod pO(log m)

Intuition

A mental model before the formal terms.

On a 7-hour clock, stepping by 3 hours repeatedly visits 3, 6, 2, 5, 1, 4, 0 — every hour, because 3 and 7 share no factor. The inverse of 3 is the number of steps to land on 1: five steps (3 · 5 = 15 ≡ 1). Multiplying by 5 "undoes" multiplying by 3. With step 2 on a 6-hour clock you only ever visit 2, 4, 0 and never reach 1 — no inverse, because gcd(2, 6) = 2.

How it works

  1. Check gcd(a, m) == 1; otherwise no inverse exists and the problem must be restructured.
  2. Fermat (prime m): inv = powMod(a, m - 2, m).
  3. Extended Euclid: (g, x, y) = extGcd(a, m); if g == 1, inv = ((x % m) + m) % m.
  4. Batch inverses 1..n mod prime p: inv[1] = 1; for i ≥ 2: inv[i] = (p - (p / i) · inv[p % i] % p) % p.
  5. Inverse factorials: compute fact[0..n], then invfact[n] = powMod(fact[n], p - 2), and walk down invfact[i - 1] = invfact[i] · i % p.

Why it works

Bezout: gcd(a, m) = 1 gives integers x, y with a·x + m·y = 1; reducing mod m kills the m·y term, leaving a·x ≡ 1. Conversely if a·x ≡ 1 then a·x - 1 is a multiple of m, so any common divisor of a and m divides 1.

Fermat: for prime p and p ∤ a, the map k ↦ a·k permutes the nonzero residues, so the product of all nonzero residues equals a^(p-1) times itself, giving a^(p-1) ≡ 1. Multiplying both sides by a^-1 yields a^(p-2) ≡ a^-1.

Batch recurrence: write p = q·i + r with q = p / i, r = p mod i. Then q·i + r ≡ 0, so i ≡ -r · q^-1, hence i^-1 ≡ -q · r^-1 and r < i is already known.

Recognition

How to tell a problem wants this.

  • A formula with division (n! / (k!(n-k)!), averages, probabilities as p/q) must be reported modulo a prime.
  • "Modulo 10^9 + 7" combined with binomial coefficients, harmonic-like sums, or geometric series formulas.
  • Solving linear congruences a·x ≡ b (mod m) or reconstructing values in the Chinese Remainder Theorem.
“modulo 10^9 + 7” → Math & Number Theory

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Fast Exponentiation visualization.

ee (binary)e & 1baseresult
131101·31
1/13Compute 3^13 mod 1000000007. Write the exponent in binary (1101): each 1-bit contributes base^(2^k), so we square the base once per bit instead of multiplying 13 times.
Current iterationBit is 1: multiply result by baseBit is 0: skip the multiplyFinished
PseudocodeLearn Fast Exponentiation →
1result = 1; base = base mod M
2while e > 0:
3  if e & 1: result = result · base mod M   # this bit is set
4  base = base · base mod M
5  e = e >> 1
6return result
Variables
base3
e13
result1
M1000000007
Complexity
best O(log n)
avg O(log n)
worst O(log n)
space O(1)
Speed

Pseudocode

1inverse_fermat(a, p):  return power(a, p - 2, p)     // p prime
2inverse_euclid(a, m):
3  (g, x, y) = ext_gcd(a, m)
4  if g != 1: no inverse
5  return (x mod m + m) mod m
6all_inverses(n, p):
7  inv[1] = 1
8  for i in 2..n: inv[i] = (p - (p / i) * inv[p mod i] mod p) mod p

Implementations

1from typing import Optional
2 
3# The modular inverse of a is the x with a*x = 1 (mod m). It exists iff
4# gcd(a, m) == 1. Two routes: extended Euclid (any m) and Fermat (prime m).
5 
6 
71 · Extended Euclid returns (g, x, y) with a*x + b*y == g == gcd(a, b)
8def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
9    old_r, r = a, b
10    old_s, s = 1, 0
11    old_t, t = 0, 1
12    while r != 0:
13        q = old_r // r
14        old_r, r = r, old_r - q * r
15        old_s, s = s, old_s - q * s
16        old_t, t = t, old_t - q * t
17    return old_r, old_s, old_t
18 
19 
202 · Inverse for any modulus: the Bezout coefficient x, normalised
21def inverse(a: int, m: int) -> Optional[int]:
22    g, x, _ = ext_gcd(a % m, m)
23    if g != 1:
24        return None  # no inverse when gcd(a, m) != 1
25    return x % m
26 
27 
283 · Prime modulus shortcut: Fermat gives a^(m-1) = 1, so a^(m-2) is a^-1
29def inverse_fermat(a: int, prime: int) -> int:
30    return pow(a, prime - 2, prime)  # built-in three-argument pow
31 
32 
334 · All inverses 1..n at once, in O(n) rather than n separate O(log m) calls
34def inverse_table(n: int, prime: int) -> list[int]:
35    inv = [1] * (n + 1)
36    for i in range(2, n + 1):
37        # inv[i] = -(prime // i) * inv[prime % i] mod prime
38        inv[i] = (prime - prime // i) * inv[prime % i] % prime
39    return inv
40 
41 
425 · Division becomes multiplication by the inverse
43def div_mod(a: int, b: int, prime: int) -> int:
44    return a * pow(b, -1, prime) % prime  # pow with -1 is the inverse (3.8+)
Walkthrough
  1. The simultaneous tuple assignment old_r, r = r, old_r - q * r is the cleanest expression of the Euclidean recurrence in any of the four languages — the right-hand side is fully evaluated before any binding changes.
  2. x % m needs no normalisation dance: Python % returns a non-negative result for a positive modulus even when x is negative.
  3. pow(a, prime - 2, prime) is the built-in three-argument modular exponentiation, implemented in C.
  4. pow(b, -1, prime) is the direct modular inverse, available since Python 3.8, and it raises ValueError when the inverse does not exist — better than returning a sentinel.
  5. inverse_table uses the O(n) recurrence, which matters when a combinatorics problem needs every inverse up to 10^6.
Complexity (this implementation)
time O(log m) for extended Euclid and for pow; O(n) for the whole table · space O(1) for a single inverse; O(n) for the table

The built-in pow(b, -1, m) is C-implemented and beats a hand-written extended Euclid in Python despite the worse constant in theory.

Language notes
  • pow(base, -1, mod) (Python 3.8+) is the modular inverse and raises ValueError when gcd(base, mod) != 1 — the clearest failure contract of the four languages.
  • math.gcd is built in; there is no standard extended version, so ext_gcd still has to be written for Bezout coefficients.
  • // floors, so old_r // r is correct for non-negative operands and differs from C/JS truncation for negatives — Euclid only ever sees non-negatives here.
  • Tuple assignment evaluates the entire right-hand side first, which is what makes the simultaneous update safe without temporaries.
Common mistakes in this language
  • Hand-writing extended Euclid when pow(b, -1, m) exists, is shorter, faster, and reports failure properly.
  • Catching nothing around pow(b, -1, m) and letting the ValueError escape when the modulus is composite.
  • Writing the Euclid updates as separate statements, which uses the already-updated value and produces wrong coefficients.
Language differences that matter here
  • Only Python has a built-in modular inverse (pow(b, -1, m), 3.8+), and it is the only one that signals non-existence by raising rather than by a sentinel or an option type.
  • Simultaneous assignment: Python tuple assignment and JS/TS array destructuring both express the Euclidean update in one line; C++ needs std::tie plus std::make_tuple to get the same effect.
  • Negative normalisation is needed in C++ and JS/TS (where % follows the dividend) and is free in Python (where it follows the divisor) — the Bezout coefficient is frequently negative, so this is not a corner case.
  • Signalling "no inverse": C++ std::optional, TypeScript bigint | null, Python a raised ValueError, and JavaScript a bare null — four different contracts for the same mathematical fact.

Complexity

Best
O(log m)
Average
O(log m)
Worst
O(log m)
Space
O(1)

Fermat: O(log p) multiplications. Extended Euclid: O(log m) steps with smaller constants. Batch inverses of 1..n: O(n) total.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Fermat when the modulus is a known prime (10^9 + 7, 998244353) — shortest code, one powMod call.
  • Extended Euclid when the modulus is composite or unknown to be prime, or when you also need to verify that the inverse exists.
  • Precomputed inverse factorials or batch inverses when a problem needs O(n) or more divisions.
Avoid it when
  • When gcd(a, m) ≠ 1 — no inverse exists. Cancel common factors symbolically, or use the CRT to split the modulus.
  • When m is prime but a is a multiple of m — a ≡ 0 has no inverse; Fermat silently returns 0.
  • When exact rational output is required — modular "fractions" are residues, not numbers you can compare.

Alternatives

GCD (Euclidean Algorithm)Fast Exponentiation

Common mistakes

  • Using Fermat with a composite modulus (10^9, 2^32) — the result is garbage with no error.
  • Forgetting to normalize the Euclid coefficient: x can be negative; return ((x % m) + m) % m.
  • Exponent typo: a^(p-1) (which is 1) instead of a^(p-2).
  • JavaScript: computing b * inv % p with plain numbers — the product exceeds 2^53; use BigInt.
  • Recomputing powMod inside a loop for n divisions when precomputed inverse factorials would make each O(1).

Interview patterns

  • Binomial coefficients mod p via factorial and inverse-factorial tables — see Combinatorics.
  • Expected value / probability answers "as p · q^-1 mod 10^9 + 7".
  • Geometric series Σ r^i = (r^n - 1) / (r - 1) mod p using the inverse of r - 1.
  • Linear congruence a·x ≡ b (mod m): divide by g = gcd(a, m) if g | b, then multiply by the inverse of a/g mod m/g.

Example problems

Unique PathsmediumPow(x, n)medium