The Extended Euclidean Algorithm & Modular Inverses

Number Theory & Cryptographic Math

Chapter 5 · The Extended Euclidean Algorithm & Modular Inverses

Chapter 4 built the Euclidean algorithm to find a number — the GCD. This chapter extends it to find something far more useful: two numbers that combine to produce that GCD. That small extension is the entire tool needed to close the gap Chapter 3 left open — dividing under a modulus.

Bézout's Identity

The theorem

For any integers a and b, there exist integers x and y such that ax + by = gcd(a, b). These x, y are called Bézout coefficients.

This isn't just a useful trick — it's a genuine guarantee that a specific linear combination of a and b always exists and always lands exactly on their GCD, never anything smaller.

The Extended Euclidean Algorithm: Finding x and y

Run the same division steps as Chapter 4, but track two extra running values (s and t) at every step, each starting from the trivial coefficients of a and b themselves, updated by the same quotient used to update the remainder.

Traced and verified directly — a general (non-coprime) example, gcd(240, 46)

q=5: r=46, s=0, t=1
q=4: r=10, s=1, t=−5
q=1: r=6, s=−4, t=21
q=1: r=4, s=5, t=−26
q=2: r=2, s=−9, t=47
Final: gcd(240,46)=2, with x=−9, y=47. Check: 240×(−9) + 46×47 = −2160 + 2162 = 2 — exactly the GCD, confirmed directly.

Modular Inverses: What Bézout Actually Unlocks

A number a has a modular inverse mod n — a number a⁻¹ such that a × a⁻¹ ≡ 1 (mod n) — if and only if gcd(a, n) = 1 (a and n are coprime).

Why this follows directly from Bézout — no new theory needed

If gcd(a, n) = 1, Bézout guarantees integers x, y with ax + ny = 1. Reducing both sides mod n: the ny term vanishes (it's a multiple of n), leaving ax ≡ 1 (mod n) — x, reduced into [0, n), is the modular inverse. The extended Euclidean algorithm doesn't just prove an inverse exists — it directly computes it.

Traced and verified directly — the modular inverse of 17 mod 43

gcd(43, 17): q=2: r=17,s=0,t=1 · q=1: r=9,s=1,t=−2 · q=1: r=8,s=−1,t=3 · q=8: r=1,s=2,t=−5. Final: gcd=1, with s=2 (coefficient of 43) and t=−5 (coefficient of 17). Check: 43×2 + 17×(−5) = 86 − 85 = 1. The modular inverse of 17 mod 43 is t mod 43 = −5 mod 43 = 38. Verified: 17 × 38 mod 43 = 646 mod 43 = 1.

When No Inverse Exists

If gcd(a, n) ≠ 1, no modular inverse exists at all — not "hard to find," genuinely absent.

Verified directly — a counterexample, 4 mod 8

gcd(4, 8) = 4 ≠ 1. Checking every possible x from 0 to 7: 4x mod 8 only ever produces 0 or 4 — never 1, for any of the 8 possible values of x. No inverse exists, exactly as the gcd=1 condition predicts.

Real Relevance: This Is Literally RSA's Private Key

Chapter 9 computes RSA's private decryption exponent as d = e⁻¹ mod φ(n) — a modular inverse, found using exactly the algorithm in this chapter. Key generation deliberately chooses e to be coprime with φ(n) specifically so this inverse is guaranteed to exist — the gcd = 1 condition from this chapter is a real, load-bearing constraint on how RSA keys are generated, not a footnote.

The Extended Euclidean Algorithm in Code

def extended_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, old_s, old_t   # gcd, x, y -- with a*x + b*y == gcd

def mod_inverse(a, n):
    g, x, _ = extended_gcd(a, n)
    if g != 1:
        raise ValueError(f"no inverse: gcd({a},{n}) = {g}, not 1")
    return x % n

print(mod_inverse(17, 43))   # 38
print(mod_inverse(4, 8))     # raises ValueError -- gcd(4,8) = 4

Hands-On Exercises

Exercise 1

Using the extended Euclidean algorithm, find Bézout coefficients x, y for gcd(99, 78). Show each step's q, r, s, t, and verify 99x + 78y equals the GCD you found.

📄 View solution

Exercise 2

Find the modular inverse of 7 mod 26 using the extended Euclidean algorithm, showing every step, and verify 7 × (inverse) mod 26 = 1.

📄 View solution

Exercise 3

Without running the extended Euclidean algorithm, determine whether 6 has a modular inverse mod 15. Justify your answer using this chapter's own existence condition, then confirm it by checking every possible x from 0 to 14 for 6x mod 15.

📄 View solution

Chapter 5 Quick Reference

Bézout's identity: for any a, b, integers x, y exist with ax + by = gcd(a,b)
Extended Euclidean algorithm: track running coefficients s, t alongside the normal GCD steps
Modular inverse exists iff gcd(a,n)=1 — proved directly from Bézout, not a separate theorem
When gcd(a,n)≠1, no inverse exists at all — verified directly by exhaustively checking every candidate
This chapter's algorithm computes RSA's own private exponent: d = e⁻¹ mod φ(n) (Chapter 9)
Next chapter: Prime numbers and primality testing