Greatest Common Divisor

Euclid’s algorithm:

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

মূল lemma: gcd(a, b) = gcd(b, a mod b) — কারণ {a,b}-এর সাধারণ ভাজকের set আর {b, a mod b}-এর সাধারণ ভাজকের set অভিন্ন।

Termination আসে [[well-ordering-principle]] থেকে: b কঠোরভাবে কমছে এবং অ-ঋণাত্মক।

Extended Euclid শুধু gcd নয়, Bézout সহগও দেয়:

ax + by = gcd(a, b)

আর সেখান থেকেই [[modular-inverse]]: gcd(a,m) = 1 হলে ax + my = 1, তাই ax ≡ 1 (mod m) — x ই inverse।

যেখানে লাগে: ভগ্নাংশ সরল করা, [[modular-inverse]], RSA-র key generation, cryptography-র বহু জায়গা, আর lattice-ভিত্তিক algorithm।

gcd(a,b) = 1 হলে a আর b কে coprime বলে — আর সেই শর্তটাই বহু theorem-এর precondition।