Extended GCD Computation

GCD measures shared divisibility; the Euclidean algorithm replaces (a,b) with (b, a mod b) until remainder 0.

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)

gcd(a,b) is the largest d dividing both. Extended GCD finds ax+by=gcd(a,b)—needed for inverses and CRT.

Try this in Python

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a


print(gcd(48, 18))

Common mistakes

• Negative numbers without abs first.
• Confusing GCD with LCM formula a*b/gcd overflow.
• Stopping Euclidean loop one step early.

Key takeaways

• gcd(a,b)==1 means coprime—often a feasibility condition.
• Batch GCD queries may use Euclidean on pairs or factor-based reasoning.