Finding Modular Inverses
What You'll Learn
You'll learn how to systematically find the multiplicative inverse of a number modulo n using the Extended Euclidean Algorithm—a guaranteed method when the inverse exists.
The Core Idea
Remember that the modular inverse of a modulo n is a number x such that ax ≡ 1 (mod n). In other words, when you multiply a by x, the result leaves remainder 1 when divided by n.
Not every number has an inverse—a must be relatively prime to n (meaning gcd(a, n) = 1). But when the inverse exists, the Extended Euclidean Algorithm gives us a direct way to compute it.
How the Extended Euclidean Algorithm Helps
Recall that the Extended Euclidean Algorithm doesn't just find gcd(a, n)—it also finds integers s and t satisfying Bézout's Identity:
as + nt = gcd(a, n)
When gcd(a, n) = 1, this becomes:
as + nt = 1
Now take this equation modulo n. Since nt ≡ 0 (mod n), we get:
as ≡ 1 (mod n)
That means s is the modular inverse of a modulo n! If s is negative, simply add n to make it positive.
Example Walkthrough
Find the inverse of 7 modulo 26.
- Use Extended Euclidean Algorithm: gcd(7, 26) = 1, and find s, t such that 7s + 26t = 1
- Working backward through the algorithm gives: 7(15) + 26(−4) = 1
- So s = 15, meaning 7 · 15 ≡ 1 (mod 26)
- Verify: 7 × 15 = 105 = 4(26) + 1 ✓
The inverse of 7 modulo 26 is 15.
Key Takeaway: To find the modular inverse of a mod n, run the Extended Euclidean Algorithm to express gcd(a, n) = 1 as as + nt = 1; the coefficient s (adjusted to be positive if needed) is your inverse.