Course contentsShow
← Mathematics
Lesson 2736 of 3,12154. Number TheoryFree lesson

Finding Modular Inverses

Use the Extended Euclidean Algorithm to find multiplicative inverses modulo n.

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.

  1. Use Extended Euclidean Algorithm: gcd(7, 26) = 1, and find s, t such that 7s + 26t = 1
  2. Working backward through the algorithm gives: 7(15) + 26(−4) = 1
  3. So s = 15, meaning 7 · 15 ≡ 1 (mod 26)
  4. 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.