18.5 Modular Inverse
Division is one of the most subtle operations in modular arithmetic.
18.5 Modular Inverse
Division is one of the most subtle operations in modular arithmetic. Addition, subtraction, and multiplication always produce valid results under a modulus, but division only works under specific conditions. Understanding these conditions is essential because modular division appears throughout cryptography, combinatorics, polynomial arithmetic, number-theoretic transforms, and countless algorithmic problems.
The key idea is that modular arithmetic has no direct division operator. Instead, division is replaced by multiplication with a modular inverse. Finding that inverse efficiently is one of the most important applications of the Extended Euclidean Algorithm.
Problem
Given integers:
a
m
find an integer:
x
such that:
ax ≡ 1 (mod m)
The value x is called the modular inverse of a modulo m.
It is commonly written as:
a⁻¹ mod m
Once the inverse exists, modular division becomes:
b / a
=
b × a⁻¹
(mod m)
For example:
3⁻¹ mod 7
equals:
5
because:
3 × 5 = 15
and:
15 ≡ 1 (mod 7)
Why Ordinary Division Fails
Consider the congruence:
2x ≡ 4 (mod 6)
One might attempt to divide both sides by 2:
x ≡ 2 (mod 6)
Checking:
2 × 2 = 4
which works.
However:
x ≡ 5 (mod 6)
also satisfies:
2 × 5 = 10
≡ 4 (mod 6)
Division produced only one of several valid answers.
The problem occurs because:
gcd(2,6) ≠ 1
The number 2 does not possess an inverse modulo 6.
This example illustrates why modular division requires special care.
Existence of an Inverse
A modular inverse exists if and only if:
gcd(a,m)=1
In other words, a and m must be coprime.
This condition is both necessary and sufficient.
Example: Inverse Exists
Find:
3⁻¹ mod 11
Since:
gcd(3,11)=1
an inverse exists.
Testing residues:
3×1 = 3
3×2 = 6
3×3 = 9
3×4 = 12 ≡ 1
Therefore:
3⁻¹ ≡ 4 (mod 11)
Example: Inverse Does Not Exist
Find:
4⁻¹ mod 10
Since:
gcd(4,10)=2
no inverse exists.
No integer satisfies:
4x ≡ 1 (mod 10)
Computing an Inverse Using Extended Euclid
Suppose we want:
7⁻¹ mod 26
The Extended Euclidean Algorithm finds integers:
x
y
such that:
7x + 26y = 1
Applying the algorithm:
26 = 7×3 + 5
7 = 5×1 + 2
5 = 2×2 + 1
2 = 1×2 + 0
Back-substituting:
1 = 5 - 2×2
Replace:
2 = 7 - 5
giving:
1 = 5 - (7 - 5)×2
Simplify:
1 = 3×5 - 2×7
Replace:
5 = 26 - 3×7
giving:
1 = 3(26 - 3×7) - 2×7
Therefore:
1 = 3×26 - 11×7
Thus:
7(-11) + 26(3) = 1
Reducing modulo 26:
7(-11) ≡ 1 (mod 26)
The inverse is:
15
because:
-11 ≡ 15 (mod 26)
Verification:
7 × 15 = 105
105 mod 26 = 1
Implementation with Extended Euclid
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return g, x, y
def mod_inverse(a, m):
g, x, _ = extended_gcd(a, m)
if g != 1:
return None
return x % m
Example:
print(mod_inverse(7, 26))
Output:
15
The complexity remains:
O(log m)
which is efficient even for very large integers.
Fermat's Little Theorem
When the modulus is prime, there is another useful technique.
If:
p
is prime and:
a ≠ 0
then:
a^(p−1) ≡ 1 (mod p)
This is known as entity["scientific_concept","Fermat's Little Theorem","number theory theorem"].
Rearranging:
a × a^(p−2)
≡ 1
(mod p)
Therefore:
a⁻¹
≡
a^(p−2)
(mod p)
This provides an efficient inverse computation for prime moduli.
Example Using Fermat
Find:
5⁻¹ mod 13
Compute:
5^(13−2)
=
5^11
mod 13
Using fast exponentiation:
5^11 mod 13 = 8
Verification:
5 × 8 = 40
and:
40 mod 13 = 1
Therefore:
5⁻¹ ≡ 8 (mod 13)
Fast Modular Exponentiation
The Fermat approach relies on efficient exponentiation.
def mod_pow(base, exp, mod):
result = 1
while exp > 0:
if exp & 1:
result = (result * base) % mod
base = (base * base) % mod
exp >>= 1
return result
Inverse under a prime modulus:
def mod_inverse_prime(a, p):
return mod_pow(a, p - 2, p)
Complexity:
O(log p)
Inverses of Multiple Numbers
Many combinatorial algorithms require thousands or millions of inverses.
Computing each independently would be expensive.
For a prime modulus:
p
the recurrence:
inv[i]
=
p - (p // i) × inv[p % i] mod p
computes all inverses from:
1
...
n
in linear time.
def inverses(n, p):
inv = [0] * (n + 1)
inv[1] = 1
for i in range(2, n + 1):
inv[i] = p - (p // i) * inv[p % i] % p
return inv
This technique is common in competitive programming and combinatorial libraries.
Applications
Modular Division
Transform:
a / b
into:
a × b⁻¹
Binomial Coefficients
Efficient computation of:
n choose k
under a prime modulus depends on modular inverses.
RSA Cryptography
Private-key generation requires modular inverses.
Chinese Remainder Theorem
Reconstruction coefficients are computed through inverses.
Polynomial Arithmetic
Finite-field polynomial operations rely heavily on inversion.
Number-Theoretic Transform
Fast polynomial multiplication uses modular inverses repeatedly.
Common Mistakes
Forgetting the Coprimality Requirement
An inverse exists only when:
gcd(a,m)=1
Always check this condition.
Using Fermat with a Composite Modulus
The formula:
a^(p−2)
works only when the modulus is prime.
Using it with composite moduli produces incorrect results.
Forgetting Final Normalization
Extended Euclid often returns negative coefficients.
Normalize with:
x %= m
before returning the answer.
Overflow During Exponentiation
Always reduce after every multiplication.
Never compute large powers directly.
Complexity Summary
| Method | Modulus | Time Complexity |
|---|---|---|
| Brute force search | Any | O(m) |
| Extended Euclid | Any coprime modulus | O(log m) |
| Fermat's theorem | Prime modulus | O(log m) |
| Precomputed inverses | Prime modulus | O(n) total |
Takeaway
A modular inverse is the modular equivalent of division. An inverse of a modulo m exists exactly when a and m are coprime. The Extended Euclidean Algorithm provides the most general method for computing inverses, while Fermat's Little Theorem offers an elegant alternative when the modulus is prime. Modular inverses appear throughout modern algorithmics, enabling modular division, combinatorial counting, finite-field arithmetic, cryptographic protocols, and many advanced number-theoretic techniques.