Extended Euclid Usage

A modular inverse of a mod m is x with a·x ≡ 1 (mod m)—exists iff gcd(a,m)=1 (or use CRT per prime power).

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Extended Euclidean gives inverse when gcd is 1. If m is prime, Fermat: a^(m-2) % m. Chain inverses when dividing in modular equations.

Try this in Python

def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def mod_inverse(a: int, mod: int) -> int:
    g, x, _ = ext_gcd(a, mod)
    if g != 1:
        raise ValueError("no inverse")
    return x % mod


print(mod_inverse(3, 11))

Common mistakes

• Inverse when gcd≠1 without CRT.
• Using (a/b) % m as a * inv(b) without checking inv exists.
• Off-by-one in Fermat exponent on composite m.

Key takeaways

• Always verify gcd(a,m)==1 before mod_inverse.
• Prefer ext_gcd in interviews; Fermat when m is prime and fast pow ready.