Linear Diophantine Solution

Diophantine equations ask for integer solutions—linear ax+by=c solved via extended GCD when gcd(a,b)|c.

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)

Find one solution (x0,y0) from ext_gcd, then add multiples of (b/g, -a/g). Transform constraints into gcd feasibility first.

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

• Missing divisibility condition on c.
• Only finding one solution when general family needed.
• Sign errors in parameter t.

Key takeaways

• Check c % gcd(a,b)==0 immediately.
• Generate general solution formula on paper.