125 — Extended Euclidean Algorithm

স্বাগতম Level 10-এ! একটা কথা আগেই বলে রাখি — এই level (আর পরেরটা) মূলত competitive programming-এর দিকে ঝোঁকা, big-tech interview-এর জন্য optional। extended Euclid বা Miller-Rabin interview-তে প্রায় আসেই না। তাই interview target হলে চাইলে এখন skip করে মূল DS topic-এ যেতে পারো, পরে ফিরলেও কিছু হারাবে না। কিন্তু সংখ্যার সবচেয়ে সুন্দর গল্পগুলো এখানেই — তাই থাকলে চলো, ধীরে ধীরে এগোই।

Source

• Original source: CP-Algorithms — Extended Euclidean Algorithm
• Platform: CP-Algorithms — https://cp-algorithms.com/algebra/extended-euclid-algorithm.html
• Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
• Difficulty: Medium
• Pattern: back substitution
• Basic idea inherited from: 018, 019 (gcd / Euclid algorithm)

1. Problem in simple words

দুটো integer a আর b দেওয়া আছে। শুধু তাদের gcd(a, b) বের করলেই হবে না — সেই সাথে দুটো integer x আর y-ও খুঁজে দিতে হবে, যাতে এই সম্পর্কটা মেলে:

a · x + b · y = gcd(a, b)

মানে gcd-টাকে a আর b-এর একটা "ওজন-মেশানো যোগফল" (integer combination) হিসেবে লিখতে হবে। সাধারণ Euclid শুধু gcd দেয়; extended Euclid সেই gcd বানানোর recipe-টাও (x, y) দেয়।

ছোট করে বলি: এটা Level 10-এর একদম প্রথম problem, আর পুরো level-এর ভিত্তি। কারণ এই x-টাই পরে modular inverse (130), CRT (127), আর Diophantine (126)-এর মূল চাবি হয়ে দাঁড়াবে। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু এই একটা problem না বুঝলে পরের তিনটা ঝুলে যাবে।

2. What is the math idea?

মূল idea-টা একটা গভীর theorem থেকে আসে — Bézout's identity: যেকোনো দুটো integer a, b-এর জন্য এমন integer x, y থাকবেই যাতে a·x + b·y = gcd(a, b)। আর শুধু থাকবে না — Euclid-এর সিঁড়ি বেয়ে নেমে আবার উঠে এসে আমরা সেটা হাতে বানিয়ে ফেলতে পারি।

এই level CP-leaning হলেও idea-টা চমৎকার সরল: Euclid যখন gcd(a, b) বের করে, প্রতি ধাপে সে লেখে a = q·b + r (q = ভাগফল, r = ভাগশেষ)। আমরা যদি প্রতিটা ধাপের ভাগশেষকে মনে রাখি, তাহলে শেষে নিচে নেমে gcd পাওয়ার পর সেই ভাগশেষগুলোকে উল্টোপথে substitute করতে করতে উপরে উঠে gcd-কে a আর b-এর ভাষায় লিখে ফেলা যায়। এটাই back substitution।

3. Which basic idea does this inherit from?

এটা সরাসরি 018, 019 (gcd / Euclid)-এর extension। সাধারণ Euclid মনে করো:

gcd(a, b) = gcd(b, a % b),   আর gcd(a, 0) = a

extended Euclid ঠিক একই recursion-এর সিঁড়ি বেয়ে নামে — শুধু পার্থক্য, ফেরার সময় সে gcd-এর সাথে x, y-ও বয়ে আনে। তাই Euclid যদি বন্ধু হয়, extended Euclid হলো সেই বন্ধু যে শুধু গন্তব্যে পৌঁছায় না, ফেরার সময় পুরো রাস্তার ম্যাপটাও এঁকে আনে।

এর উপরে আবার দাঁড়াবে: 126 (Diophantine) — এক solution পেতে, 127 (CRT) — modulus merge করতে, 130 (modular inverse) — inverse বের করতে। তাই এটা পুরো level-এর শিকড়।

4. Real-life analogy

ভাবো তোমার কাছে দুই ধরনের weight আছে — একটা a গ্রামের, একটা b গ্রামের। একটা দাঁড়িপাল্লায় তুমি এই weight গুলো দুই পাশে রেখে চাও একদম ছোট সম্ভব পার্থক্য (যেটা হলো gcd) মাপতে।

• x মানে: a-গ্রামের weight কয়টা, আর কোন পাশে (positive হলে এক পাশ, negative হলে উল্টো পাশ)
• y মানে: b-গ্রামের weight কয়টা, কোন পাশে

extended Euclid তোমাকে শুধু বলে না "সবচেয়ে ছোট মাপ কত" — সে তোমাকে ঠিক recipe দেয়: কয়টা a-weight, কয়টা b-weight, কোন পাশে রাখলে ওই ছোট মাপটা পাবে। সাধারণ Euclid শুধু মাপটা বলত; extended বলে কীভাবে সাজাবে।

5. Visual explanation

gcd(30, 18)-এর পুরো যাত্রা দেখি — আগে সিঁড়ি বেয়ে নামা (Euclid), তারপর back-substitution-এ উঠে আসা:

নামা (Euclid division steps):
  30 = 1·18 + 12
  18 = 1·12 +  6
  12 = 2· 6 +  0   <- ভাগশেষ 0, তাই gcd = 6

ওঠা (back-substitution, ভাগশেষকে আগের লাইনে বদলাই):
  6 = 18 − 1·12                      [দ্বিতীয় লাইন থেকে 6 আলাদা করলাম]
    = 18 − 1·(30 − 1·18)            [12 = 30 − 1·18 বসালাম]
    = 18 − 1·30 + 1·18
    = 2·18 − 1·30
  ⇒ 30·(−1) + 18·(2) = 6   ✓

ফল:  x = −1,  y = 2
যাচাই:  30·(−1) + 18·2 = −30 + 36 = 6 = gcd ✓

লক্ষ করো — নিচে নামার সময় প্রতিটা ভাগশেষ (12, তারপর 6) তৈরি হলো; উপরে ওঠার সময় সেই ভাগশেষগুলোকে একে একে আগের সংখ্যার ভাষায় লিখে শেষে শুধু 30 আর 18 রয়ে গেল। এটাই সিঁড়ির খেলা।

6. Example input and output

input (a, b)  ->  output (g, x, y)        যাচাই (a·x + b·y)
-----------------------------------------------------------------
   30, 18     ->  (6, -1, 2)              30·(-1) + 18·2 = 6   ✓
   35, 15     ->  (5, 1, -2)              35·1 + 15·(-2) = 5   ✓
   17, 5      ->  (1, -2, 7)              17·(-2) + 5·7 = 1    ✓ (coprime)
   12, 0      ->  (12, 1, 0)              12·1 + 0·0 = 12      ✓ (b = 0)
   0, 7       ->  (7, 0, 1)               0·0 + 7·1 = 7        ✓ (a = 0)
   48, 36     ->  (12, 1, -1)             48·1 + 36·(-1) = 12  ✓

দুটো edge case খেয়াল করো: b = 0 হলে gcd = a, আর x = 1, y = 0 (কারণ a·1 + 0·0 = a)। আর coprime (gcd = 1) হলে x ঠিক a-এর inverse mod b হয়ে দাঁড়ায় — সেটাই 130-তে কাজে লাগবে। (x, y-এর মান unique নয়; একই gcd-এর জন্য একাধিক (x, y) সম্ভব, আমরা একটা valid জোড়া দিই।)

7. Brute force thinking

x, y না জেনে শুরু করলে প্রথম যে naive idea আসে — সব ছোট integer জোড়া ধরে চেষ্টা করা। আগে সাধারণ Euclid দিয়ে g = gcd বের করি, তারপর x আর y-কে একটা range-এ ঘুরিয়ে দেখি কোন জোড়ায় a·x + b·y == g মেলে:

def ext_gcd_brute(a, b):
    from math import gcd
    g = gcd(a, b)
    limit = max(abs(a), abs(b)) + 1     # |x|, |y| এর মোটামুটি সীমা
    for x in range(-limit, limit + 1):
        for y in range(-limit, limit + 1):
            if a * x + b * y == g:
                return g, x, y
    return g, None, None

ছোট সংখ্যায় (যেমন 30, 18) এটা ঠিক জোড়া (একটা valid x, y) খুঁজে দেয়। বড়জোর "কোনোভাবে হলেও হলো" — কিন্তু এটাই আমাদের শুরু।

8. Why brute force may be slow

সমস্যা স্পষ্ট — এটা দুটো nested loop, প্রতিটা প্রায় max(a, b) লম্বা। তাই মোট কাজ O(a · b)-এর কাছাকাছি, মানে দুটো সংখ্যার গুণফলের মাপের।

a, b ছোট (30, 18):     ~60 × 60 = 3,600 জোড়া পরীক্ষা — চোখের পলকে
a, b মাঝারি (10⁶):     ~10⁶ × 10⁶ = 10¹² জোড়া — কয়েক ঘণ্টা/দিন!

মানে সংখ্যা একটু বড় হলেই brute force কার্যত অচল। অথচ সাধারণ Euclid নিজেই O(log min(a, b))-এ gcd বের করে — তাহলে x, y বের করতেও তো log ধাপেই হওয়া উচিত, পুরো grid চষার দরকার নেই। সেটাই extended Euclid-এর প্রতিশ্রুতি।

9. Better thinking

মূল insight: back-substitution-টা recursion নিজেই করে দিতে পারে। আলাদা করে সব ভাগশেষ খাতায় লিখে উপরে ওঠার দরকার নেই — recursion যখন নিচ থেকে ফেরে, প্রতিটা return-এ x, y update করে নিয়ে এলেই হলো।

ধরো আমরা b আর a % b-এর জন্য ইতিমধ্যে (x₁, y₁) পেয়েছি:

b·x₁ + (a % b)·y₁ = g

এখন a % b = a − (a // b)·b বসিয়ে দিই:

b·x₁ + (a − (a // b)·b)·y₁ = g
a·y₁ + b·(x₁ − (a // b)·y₁) = g

মিলিয়ে দেখো — a-এর সহগ এখন y₁, আর b-এর সহগ x₁ − (a // b)·y₁। মানে:

নতুন x = y₁
নতুন y = x₁ − (a // b)·y₁

এই দুই লাইনের update rule-ই পুরো algorithm। recursion শেষ হয় b = 0-তে, যেখানে a·1 + 0·0 = a — তাই base case (a, 1, 0)।

10. Thinking tweak

আসল "আহা" মুহূর্ত: g বানানোর recipe-টা return-এর সময় বয়ে আনা যায় — gcd আর তার combination একই recursion-এ একসাথে উঠে আসে।

brute force পুরো (x, y) grid খুঁজছিল; tweak হলো — Euclid যে সিঁড়ি বেয়ে এমনিতেই নামছে, ঠিক সেই সিঁড়ি বেয়ে ফেরার সময় দুটো extra সংখ্যা (x, y) update করে নিয়ে এসো। O(a·b) থেকে সোজা O(log min(a, b))-এ নেমে এল, কারণ Euclid নিজেই log ধাপে নামে।

(সতর্কতা: এই x = y₁, y = x₁ − (a//b)·y₁ rule-টা একবার নিজে খাতায় gcd(30, 18)-এ verify না করলে মুখস্থ ভুল হবেই — এটাই এই level-এর #১ common mistake।)

11. Step-by-step dry run

ext_gcd(30, 18) recursion-এর সিঁড়ি — আগে নিচে নামা (call), তারপর ফেরা (return) সহ:

call	a	b	a % b	a // b	কী হবে
1	30	18	12	1	ext_gcd(18, 12)-এর জন্য অপেক্ষা
2	18	12	6	1	ext_gcd(12, 6)-এর জন্য অপেক্ষা
3	12	6	0	2	ext_gcd(6, 0)-এর জন্য অপেক্ষা
4	6	0	—	—	base case → return (6, 1, 0)

এবার ফেরার পথ (নিচ থেকে উপরে), update rule x = y₁, y = x₁ − (a//b)·y₁:

ফেরা	পেলাম (g, x₁, y₁)	a // b	নতুন x = y₁	নতুন y = x₁ − (a//b)·y₁	return
call 4 → 3	(6, 1, 0)	2	0	1 − 2·0 = 1	(6, 0, 1)
call 3 → 2	(6, 0, 1)	1	1	0 − 1·1 = −1	(6, 1, −1)
call 2 → 1	(6, 1, −1)	1	−1	1 − 1·(−1) = 2	(6, −1, 2)

শেষ return: (6, −1, 2)। যাচাই: 30·(−1) + 18·2 = −30 + 36 = 6 ✓। দেখো — back-substitution-এর সেই সিঁড়িটাই recursion নিজে নিজে চড়ে উঠল।

12. Python solution

def ext_gcd(a, b):
    """gcd(a, b) এবং এমন (x, y) ফেরত দেয় যাতে a*x + b*y = gcd(a, b)।"""
    if b == 0:
        return a, 1, 0                       # a*1 + 0*0 = a
    g, x1, y1 = ext_gcd(b, a % b)            # b*x1 + (a % b)*y1 = g
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y


def ext_gcd_iter(a, b):
    """একই কাজ, কিন্তু loop দিয়ে (recursion-এর গভীরতা এড়াতে)।"""
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    return old_r, old_x, old_y               # (g, x, y)


# --- ছোট test গুলো (সব pass করা উচিত) ---
from math import gcd

def check(a, b):
    """দুই version মেলে কিনা, আর a*x + b*y == g কিনা যাচাই করে।"""
    g1, x1, y1 = ext_gcd(a, b)
    g2, x2, y2 = ext_gcd_iter(a, b)
    assert g1 == gcd(a, b), f"gcd ভুল: {a},{b}"
    assert a * x1 + b * y1 == g1, f"recursive identity ভুল: {a},{b}"
    assert a * x2 + b * y2 == g2, f"iterative identity ভুল: {a},{b}"
    assert g1 == g2, f"দুই version-এর gcd আলাদা: {a},{b}"

check(30, 18)
check(35, 15)
check(17, 5)
check(12, 0)
check(0, 7)
check(48, 36)
check(99, 78)
check(1, 1)
check(1000000007, 998244353)   # বড় coprime জোড়া

g, x, y = ext_gcd(30, 18)
assert (g, x, y) == (6, -1, 2)

print(ext_gcd(30, 18))         # (6, -1, 2)
print(ext_gcd(35, 15))         # (5, 1, -2)
print(ext_gcd_iter(17, 5))     # (1, -2, 7)
print("সব test pass!")

13. Line-by-line explanation

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0

base case — b শূন্য হলে gcd হলো a নিজেই, আর a·1 + 0·0 = a মেলে, তাই x = 1, y = 0।

    g, x1, y1 = ext_gcd(b, a % b)

ছোট সমস্যাটা আগে solve করছি — b আর a % b-এর জন্য (g, x₁, y₁) পাচ্ছি, যেখানে b·x₁ + (a % b)·y₁ = g। এটাই Euclid-এর সিঁড়ি নিচে নামা।

    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

ফেরার সময় section 9-এর algebra প্রয়োগ — নতুন x হলো পুরোনো y₁, আর নতুন y হলো x₁ − (a // b)·y₁। gcd একই থাকে, শুধু সহগ দুটো update হয়।

def ext_gcd_iter(a, b):
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1
    while r != 0:
        q = old_r // r
        ...

iterative রূপ — তিন জোড়া variable (remainder, x, y) একসাথে এগোয়। প্রতি ধাপে ভাগফল q বের করে তিনটাকেই একই rule-এ update করি। এতে recursion-এর গভীরতা (deep recursion) এড়ানো যায়, বড় input-এ নিরাপদ।

বাকি check function আর assert লাইনগুলো নিজেরাই যাচাই করে — দুই version মেলে কিনা, আর মূল identity a·x + b·y == g সত্যি কিনা। সব ঠিক থাকলে শেষে সব test pass! ছাপে।

14. Output walkthrough

চালালে যা ছাপবে:

(6, -1, 2)
(5, 1, -2)
(1, -2, 7)
সব test pass!

প্রথম লাইন ext_gcd(30, 18) → (6, −1, 2), মানে 30·(−1) + 18·2 = 6। দ্বিতীয় ext_gcd(35, 15) → (5, 1, −2), মানে 35·1 + 15·(−2) = 5। তৃতীয় ext_gcd_iter(17, 5) → (1, −2, 7), মানে 17·(−2) + 5·7 = 1 (coprime, তাই gcd 1)। তার আগের সব assert চুপচাপ pass করেছে — তাই শেষে সব test pass!।

15. Time complexity

O(log min(a, b)) — ঠিক সাধারণ Euclid-এর মতোই। প্রতি ধাপে (a, b) থেকে (b, a % b)-তে যাই, আর Euclid-এর তত্ত্ব বলে দুই ধাপে সংখ্যা অন্তত অর্ধেক হয় (Fibonacci জোড়া worst case)। তাই ধাপ সংখ্যা ছোট সংখ্যাটার অঙ্ক-সংখ্যার সমানুপাতিক — logarithmic। brute force-এর O(a·b) থেকে আকাশ-পাতাল পার্থক্য।

16. Space complexity

Recursive version: O(log min(a, b)) — recursion-এর গভীরতা যত ধাপ, তত stack frame। Iterative version: O(1) — মাত্র গুটিকয় variable, কোনো extra array নেই। বড় input-এ iterative version-ই নিরাপদ (Python-এ default recursion limit-এ ধাক্কা খাবে না)।

17. Common mistakes

1. Update rule গুলিয়ে ফেলা — সবচেয়ে কমন ভুল। x = y₁, y = x₁ − (a//b)·y₁ — কেউ x আর y উল্টে ফেলে, কেউ (a//b) ভুলে যায়। একটা ছোট উদাহরণে (gcd(30, 18)) হাতে verify না করে কখনো ছাড়বে না।
2. base case ভুল — b == 0-তে return (a, 1, 0) হওয়া উচিত; কেউ ভুল করে (a, 0, 1) বা (b, ...) লেখে।
3. negative x, y-কে ভুল ভাবা — x বা y negative হওয়া স্বাভাবিক ও সঠিক; minus দেখে ভয় পেয়ো না, identity মিললেই হলো।
4. x, y unique ভাবা — একই gcd-এর জন্য অসীম (x, y) জোড়া আছে (x + k·b/g, y − k·a/g)। তোমার উত্তর reference-এর সাথে হুবহু না মিললেও যদি a·x + b·y == g মেলে, সেটা সঠিক।
5. বড় input-এ recursion limit — Python-এ অতি বড় বা বিশেষ জোড়ায় recursion গভীরে গেলে error; তখন iterative version use করো।

18. Harder problems that inherit this idea

• CSES — Exponentiation II (https://cses.fi/problemset/task/1712) — modular inverse লাগে, যার পেছনে এই ext-gcd-এর চিন্তা (অথবা Fermat)।
• Codeforces — Modular Inverse style problems (https://codeforces.com/problemset) — অনেক number theory problem-এ a·x ≡ 1 (mod m) সমাধানে সরাসরি extended Euclid।
• 126 (Linear Diophantine), 127 (CRT), 130 (Modular Inverse) — এই repo-রই পরের তিনটা, প্রত্যেকটাই extended Euclid-এর সরাসরি প্রয়োগ।

19. Pattern learned

Back substitution via extended Euclid — gcd বের করার সিঁড়ি বেয়ে ফেরার সময় (x, y) update করে নিয়ে আসা, যাতে a·x + b·y = gcd(a, b) মেলে। বড় শিক্ষা: একটা algorithm যে পথ ধরে চলে, সেই একই পথে সামান্য extra হিসাব বইয়ে আনলে অনেক বেশি তথ্য বিনামূল্যে পাওয়া যায় — gcd-র সাথে তার combination।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "extended Euclid = Euclid-এর সিঁড়ি বেয়ে ফেরার সময় x = y₁, y = x₁ − (a//b)·y₁ দিয়ে x, y বইয়ে আনা; ফল a·x + b·y = gcd। এটাই inverse, CRT, Diophantine-এর চাবি।" Signal: যখনই gcd-কে combination হিসেবে লিখতে হবে, বা inverse/Diophantine লাগবে — এই pattern মনে পড়বে।

পরের ধাপ → 126 — Linear Diophantine Equation (এই x, y দিয়ে ax + by = c সমাধান)। সম্পর্কিত → 127 — CRT, 130 — Modular Inverse Advanced।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-এর ছক → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — এই level CP-leaning, interview-optional।