Extended Euclidean Algorithm: Find Modular Multiplicative Inverse with Examples

The Extended Euclidean Algorithm is a fundamental concept in number theory and computer science. It extends the classic Euclidean Algorithm for finding the GCD (Greatest Common Divisor) and enables us to compute coefficients that satisfy Bézout’s identity. One of its most important applications is finding the modular multiplicative inverse.

In this article, we’ll explain the algorithm step by step, demonstrate its use in calculating modular inverses, provide interactive diagrams, and share examples in Python that can be directly applied to problems in cryptography, modular arithmetic, and competitive programming.

---

Understanding the Basics

Before we explore the extended version, let’s recall Bézout’s Identity:

For any integers a and b, there exist integers x and y such that:
a × x + b × y = gcd(a, b)

The Extended Euclidean Algorithm helps us compute these integers x and y. If gcd(a, m) = 1, then x is the modular inverse of a modulo m.

---

Why Modular Multiplicative Inverse Matters

The modular multiplicative inverse of a modulo m is an integer x such that:

(a × x) mod m = 1

This concept is crucial in:

• Cryptography – RSA, ECC, and many encryption algorithms use modular inverses.
• Competitive programming – modular inverses help efficiently compute divisions in modular arithmetic.
• Mathematics – solving linear congruences relies on modular inverses.

---

Steps of Extended Euclidean Algorithm

The algorithm works recursively:

1. If b = 0, then gcd(a, b) = a, and we set x = 1, y = 0.
2. Otherwise, we compute gcd(b, a mod b) recursively.
3. As we unwind the recursion, we calculate updated x and y values.

---

Step-by-Step Example

Let’s compute the modular inverse of 17 mod 43.

1. Apply Extended Euclidean Algorithm with (a=17, m=43).
2. Find gcd(17, 43) = 1 (since they are coprime).
3. Trace back values of x and y.

Working backwards:

1 = 9 - 1 × 8
1 = 9 - 1 × (17 - 1 × 9) = 2 × 9 - 1 × 17
1 = 2 × (43 - 2 × 17) - 1 × 17
1 = 2 × 43 - 5 × 17

So, x = -5, y = 2. The modular inverse of 17 modulo 43 is -5 mod 43 = 38.

Answer: The inverse of 17 mod 43 is 38.

---

Python Implementation

Here is a clean and reusable Python implementation:

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

def modular_inverse(a, m):
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        return None  # Inverse doesn’t exist
    return x % m

# Example usage
print(modular_inverse(17, 43))  # Output: 38

---

Interactive Walkthrough (Visualization)

The diagram above illustrates how recursion computes gcd and then backtracks to derive the modular inverse.

---

Key Observations

• The modular inverse exists only if a and m are coprime.
• Extended Euclidean Algorithm provides gcd, along with x and y in Bézout’s identity.
• In modular arithmetic, x (mod m) is the modular inverse whenever gcd=1.

---

Applications in Real World

The Extended Euclidean Algorithm is widely used in:

1. Public Key Cryptography – RSA encryption/decryption relies on modular inverses.
2. Chinese Remainder Theorem – solving simultaneous modular equations.
3. Programming Contest Problems – modular division in combinatorics problems.

---

Conclusion

The Extended Euclidean Algorithm is not only a way to compute gcd but also a powerful tool to derive the modular multiplicative inverse. Mastery of this algorithm offers deep insights into number theory, cryptography, and algorithm design. With the provided explanations, visual diagrams, and Python code, you can now apply it confidently to competitive programming challenges and mathematical problems.