কনটেন্টে যান

019 — Extended GCD Intro

এটা এই level-এর প্রথম Hard problem, আর Level 2-র দিকে একটা সেতু। ঘাবড়িও না — এখন perfection-এর দরকার নেই। শুধু "এটা সম্ভব আর কীভাবে সম্ভব" এটুকু বুঝে গেলেই যথেষ্ট; modular inverse করার সময় (Level 2) এই কৌশল আবার ফিরবে, তখন আরও অর্থবহ লাগবে। ধীরে পড়ো।

Problem link ও উৎস

  • 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 1: Divisibility, Prime, GCD, LCM
  • Difficulty: Hard
  • Pattern: back-substitution — a·x + b·y = gcd(a, b)
  • Basic idea inherited from: 018 — GCD using Euclidean Algorithm

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

উদাহরণ
a · x + b · y = gcd(a, b)

উদাহরণ: a = 48, b = 18 হলে gcd = 6, আর একটা সমাধান হলো x = −1, y = 3, কারণ 48 × (−1) + 18 × 3 = −48 + 54 = 6। ঠিকঠাক!

মানে শুধু "সবচেয়ে বড় common divisor কত" নয়, "সেই divisor-কে a আর b-র একটা যোগফল হিসেবে কীভাবে সাজানো যায়" — সেই coefficient দুটো বের করাই কাজ।

Input ও output

উদাহরণ
   a  ,   b   ->  (g, x, y)   যাচাই: a·x + b·y
-----------------------------------------------
  48  ,  18   ->  (6, -1, 3)    48·(-1)+18·3 = 6   ✓
  30  ,  20   ->  (10, 1, -1)   30·1 + 20·(-1) = 10 ✓
  35  ,  15   ->  (5, 1, -2)    35·1 + 15·(-2) = 5  ✓
  7   ,   0   ->  (7, 1, 0)     7·1 + 0·0 = 7       ✓
  3   ,   5   ->  (1, 2, -1)    3·2 + 5·(-1) = 1    ✓ (coprime)

খেয়াল করো: x, y একমাত্র নয় — একাধিক জোড়া কাজ করে (যেমন 48·(−1)+18·3 = 6, আবার 48·2+18·(−5) = 6-ও হয়)। আমরা যেটা পাই, সেটা একটা বৈধ সমাধান; verify করার সময় সবসময় a·x + b·y == g চেক করব, ঠিক কোন জোড়া বেরিয়েছে তা নয়।

চেনা উদাহরণে বোঝা

ভাবো তোমার কাছে শুধু দুই মাপের ওজন আছে — 48 গ্রামের আর 18 গ্রামের বাটখারা — আর একটা দুই-পাল্লার দাঁড়িপাল্লা। তুমি জানতে চাও: এই দুটো দিয়ে ঠিক 6 গ্রাম ওজন মাপা যায় কি না।

হ্যাঁ যায় — এক পাল্লায় একটা 18 আর আরেকটা 18 (মোট 54), অন্য পাল্লায় একটা 48 রাখলে পার্থক্য 54 − 48 = 6। মানে "18 তিনবার যোগ, 48 একবার বিয়োগ" → 18×3 + 48×(−1) = 6। এখানে ধনাত্মক coefficient মানে "এই পাল্লায়", ঋণাত্মক মানে "ওই পাল্লায়"।

Extended GCD আসলে তোমাকে সেই recipe-টাই বলে দেয়: কোন বাটখারা কতবার, কোন পাল্লায়।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা সরাসরি 018 (GCD using Euclidean Algorithm)-এর উপর দাঁড়িয়ে। 018-এ আমরা শুধু সংখ্যাটা (gcd) ফেরত দিতাম; এখানে সেই একই ধাপগুলো ধরে রেখে, প্রতিবার coefficient-ও বয়ে নিয়ে যাই।

মূল পার্থক্য: 018 শুধু "কত" বলে; 019 বলে "কীভাবে a আর b মিলিয়ে সেই 'কত' বানানো যায়"। তাই 018 ভালো করে বুঝে না থাকলে আগে সেখানে এক ধাপ পিছিয়ে যাও — back-substitution আসলে সেই ধাপগুলোরই উল্টো যাত্রা।

ভেতরের অঙ্ক

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

Core idea: সাধারণ Euclid যখন (a, b) থেকে (b, a % b)-তে নামে, তখন প্রতিটা remainder আসলে a আর b-র একটা যোগফল হিসেবে লেখা যায়। সবচেয়ে নিচের ধাপে (যেখানে gcd বেরোয়) সেই যোগফলের coefficient গুলোই আমাদের x, y।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

x, y কত হতে পারে না জানলে, সবচেয়ে সরল চিন্তা — প্রথমে সাধারণ gcd বের করি, তারপর x-কে একটা range-এ ঘুরিয়ে দেখি কোন x-এর জন্য (g − a·x) ঠিকঠাক b দিয়ে ভাগ যায় (তাহলেই y = (g − a·x) / b পূর্ণসংখ্যা):

Python
def extgcd_brute(a, b):
    from math import gcd
    g = gcd(a, b)
    if b == 0:
        return (g, 1, 0)
    # x ছোট range-এ খুঁজি: এমন x যাতে (g - a*x) b দিয়ে ভাগ যায়
    for x in range(-abs(b), abs(b) + 1):
        if (g - a * x) % b == 0:
            y = (g - a * x) // b
            return (g, x, y)

এটা |b| range-এ x খুঁজে একটা বৈধ জোড়া দেয় — কারণ একটা সমাধান সবসময় ওই range-এ থাকে। ঠিক উত্তরই বেরোয়, শুধু সাজানো নয়।

কোথায় বেশি কাজ হতে পারে

এই loop সবচেয়ে খারাপ ক্ষেত্রে 2·|b| বার ঘোরে। b ছোট হলে ঠিক আছে, কিন্তু b যদি 10⁹ হয়, তাহলে প্রায় ২০০ কোটি বার loop — Time Limit Exceeded।

উদাহরণ
b = 1000000000 হলে:
  brute force : ~2×10^9 বার loop   (ধীর, O(b))
  extended Euclid : ~30 ধাপের কম    (O(log min(a, b)), GCD-র মতোই)

মূল সমস্যা: আমরা x-কে অন্ধভাবে খুঁজছি, যেখানে Euclid-এর ধাপগুলোই আমাদের x, y হিসাব করে দিয়ে দিতে পারে। সেই হিসাবটাই দ্রুত পথ।

আরও ভালোভাবে ভাবা

মূল insight: base case-এ coefficient জানা, আর প্রতিটা recursion থেকে ফেরার সময় coefficient update করার একটা সরল সূত্র আছে।

Base case: extgcd(a, 0) = (a, 1, 0) — কারণ a·1 + 0·0 = a = gcd। সহজ।

Recursive ধাপ: ধরো আমরা ছোট সমস্যা extgcd(b, a % b) থেকে (g, x1, y1) পেলাম, মানে b·x1 + (a % b)·y1 = g। এখন a % b = a − (a // b)·b বসিয়ে সাজালে পাওয়া যায়:

উদাহরণ
g = a·y1 + b·(x1 − (a // b)·y1)

তাই বড় সমস্যার উত্তর: x = y1, y = x1 − (a // b)·y1। এই দুটো সূত্রই পুরো কাজ — কোনো খোঁজাখুঁজি নেই।

ভাবনার পরিবর্তন

আসল "আহা!" মুহূর্ত: Euclid নিচে নামার সময় শুধু সংখ্যা না, coefficient-ও বয়ে নিলে — ফেরার পথে তারা নিজেরাই সঠিক x, y-তে গুছিয়ে যায়।

মূল মোচড়টা ওই এক লাইনে: ছোট সমস্যার (x1, y1) থেকে বড় সমস্যার (x, y) হয় x = y1, y = x1 − (a // b)·y1। মানে x আর y যেন একে অপরের ভূমিকা বদলে নেয়, আর y-তে quotient a // b-র একটা সংশোধন যোগ হয়। এই সূত্রটা মুখস্থ নয় — বুঝে রাখলেই Level 2-তে কাজে দেবে।

ছবিতে বোঝা

প্রথমে সাধারণ Euclid নিচে নামে, তারপর আমরা coefficient নিয়ে আবার উপরে উঠি:

উদাহরণ
নিচে নামা (সাধারণ Euclid):
  48 = 18·2 + 12      <- remainder 12
  18 = 12·1 + 6       <- remainder 6  (এটাই gcd)
  12 =  6·2 + 0       <- শেষ

উপরে উঠে coefficient সাজানো (back-substitution):
  6 = 18 − 12·1
    = 18 − (48 − 18·2)·1      [12 = 48 − 18·2 বসালাম]
    = 18·3 − 48·1
  => x(for 48) = −1,  y(for 18) = 3

মিলিয়ে দেখো:

উদাহরণ
   48 · (−1)  +  18 · 3
 = −48        +  54
 =  6   ✓     (= gcd)

ছোট input-এ ধাপে ধাপে

চলো extgcd(48, 18) চালাই। আগে recursion নিচে নামে (base case পর্যন্ত), তারপর ফেরার পথে coefficient গোছায়:

নিচে নামা:

call a b a // b
1 48 18 2
2 18 12 1
3 12 6 2
4 6 0 — (base case)

ফেরার পথ (x = y1, y = x1 − (a//b)·y1):

ফিরছি base/ছোট থেকে (g, x1, y1) নতুন (g, x, y)
call 4 base: (6, 1, 0) (6, 1, 0)
call 3 (a//b=2) (6, 1, 0) (6, 0, 1 − 2·0) = (6, 0, 1)
call 2 (a//b=1) (6, 0, 1) (6, 1, 0 − 1·1) = (6, 1, −1)
call 1 (a//b=2) (6, 1, −1) (6, −1, 1 − 2·(−1)) = (6, −1, 3)

শেষ উত্তর (6, −1, 3)। যাচাই: 48·(−1) + 18·3 = −48 + 54 = 6 ✓ — section 5-এর হাতে-করা back-substitution-এর সাথে হুবহু মিলল।

কোড ও ব্যাখ্যা

Python

Python
def extended_gcd(a, b):
    """(g, x, y) ফেরত দেয় যেখানে g = gcd(a, b) আর a·x + b·y = g।"""
    if b == 0:
        return (a, 1, 0)              # base: a·1 + 0·0 = a
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1                            # coefficient গোছানোর সূত্র
    y = x1 - (a // b) * y1
    return (g, x, y)


def extended_gcd_iter(a, b):
    """একই কাজ, iterative — recursion ছাড়া, বড় input-এ নিরাপদ।"""
    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)       # (gcd, x, y)


# --- ছোট test গুলো (সব pass করা উচিত) ---
def check(a, b):
    g, x, y = extended_gcd(a, b)
    assert a * x + b * y == g          # Bézout মিলছে?
    from math import gcd
    assert g == gcd(a, b)              # সঠিক gcd?
    gi, xi, yi = extended_gcd_iter(a, b)
    assert a * xi + b * yi == gi       # iterative-ও মিলছে?
    assert gi == g
    return g, x, y


assert check(48, 18) == (6, -1, 3)
assert check(30, 20)[0] == 10          # g ঠিক; x, y যেকোনো বৈধ জোড়া
assert check(35, 15)[0] == 5
assert check(7, 0) == (7, 1, 0)        # base case
assert check(3, 5)[0] == 1             # coprime
assert check(1071, 462)[0] == 21       # বড় উদাহরণ

print(extended_gcd(48, 18))   # (6, -1, 3)
print(extended_gcd(3, 5))     # (1, 2, -1)
print(extended_gcd(7, 0))     # (7, 1, 0)
print("সব test pass!")

কোডের প্রতিটি অংশ

উদাহরণ
    if b == 0:
        return (a, 1, 0)

Base case — recursion থামার জায়গা। b = 0 হলে gcd = a, আর a·1 + 0·0 = a মেলে, তাই x = 1, y = 0।

উদাহরণ
    g, x1, y1 = extended_gcd(b, a % b)

ছোট সমস্যাটা আগে solve করি (ঠিক 018-এর Euclid-এর মতো নিচে নামা)। ওটা ফেরত দেয় (g, x1, y1) যেখানে b·x1 + (a % b)·y1 = g।

উদাহরণ
    x = y1
    y = x1 - (a // b) * y1

এই দুই লাইনই back-substitution-এর প্রাণ। ছোট সমস্যার coefficient থেকে বড় সমস্যার coefficient হিসাব করি (section 9-এর সূত্র)। নতুন x পুরোনো y1, আর নতুন y-তে quotient a // b-র সংশোধন।

iterative version-এ একই কাজ tuple-update দিয়ে: old_r, x, y ত্রয়ী একসাথে এগোয়, প্রতি ধাপে quotient q দিয়ে update — recursion না থাকায় বিশাল input-এও stack overflow হয় না।

check function প্রতিবার a*x + b*y == g যাচাই করে — অর্থাৎ ঠিক কোন জোড়া বেরোলো তা না দেখে, Bézout মেলে কি না সেটাই assert করি (কারণ সমাধান একাধিক)।

Output মিলিয়ে দেখা

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

উদাহরণ
(6, -1, 3)
(1, 2, -1)
(7, 1, 0)
সব test pass!

প্রথম লাইন: extgcd(48,18) = (6, −1, 3), যা section 11-এর dry run-এর সাথে মেলে। দ্বিতীয়: extgcd(3,5) = (1, 2, −1), যাচাই 3·2 + 5·(−1) = 1। তৃতীয়: base case (7,0) = (7, 1, 0)। সব assert (যেগুলো প্রতিবার Bézout আর gcd দুটোই যাচাই করেছে) চুপচাপ pass করেছে, তাই শেষে সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(log min(a, b)) — একদম সাধারণ Euclid-এর মতোই, কারণ ধাপের সংখ্যা হুবহু একই; শুধু প্রতি ধাপে দুটো বাড়তি coefficient হিসাব হচ্ছে (constant কাজ)। তাই 018-এর gcd যত দ্রুত, এটাও তত দ্রুত।

অতিরিক্ত জায়গা

O(log min(a, b)) recursive version-এ — recursion-এর গভীরতা ধাপের সংখ্যার সমান, প্রতি call একটা stack frame। iterative version-এ মাত্র O(1) — গুটিকয় variable, কোনো stack নেই। বড় input হলে iterative-টা নিরাপদ।

যে ভুলগুলো এড়াতে হবে

  1. Coefficient update সূত্র উল্টে ফেলা — মনে রেখো x = y1 আর y = x1 − (a // b)·y1; দুটো গুলিয়ে ফেললে Bézout মিলবে না।
  2. a % b আর a // b গুলিয়ে ফেলা — recursion-এ যায় a % b (remainder), কিন্তু coefficient সূত্রে লাগে a // b (quotient)।
  3. x, y unique ভাবা — একাধিক বৈধ জোড়া আছে; verify করতে সবসময় a·x + b·y == g চেক করো, নির্দিষ্ট মান নয়।
  4. Base case ভুলে যাওয়া বা ভুল লেখা — b == 0-তে (a, 1, 0) ফেরত; এটা না থাকলে recursion থামবে না।
  5. এখনই সব মুখস্থ করার চেষ্টা — এটা Hard আর Level 2-র সেতু; এখন idea বুঝলেই যথেষ্ট, modular inverse-এর সময় এটা স্বাভাবিকভাবে গেঁথে যাবে।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

  • CP-Algorithms — Linear Diophantine Equation (https://cp-algorithms.com/algebra/linear-diophantine-equation.html) — a·x + b·y = c সমাধান, সরাসরি extended GCD-র উপর গড়া।
  • CP-Algorithms — Modular Multiplicative Inverse (https://cp-algorithms.com/algebra/module-inverse.html) — Level 2-তে এই কৌশল দিয়েই inverse বের হবে; এটাই আসল গন্তব্য।
  • 023 (Euler Phi Basic) — এই repo-রই পরের ধাপে phi function, যা modular গণিতে extended GCD-র পাশেই কাজ করে।

কৌশলটি মনে রাখুন

Extended Euclid / back-substitution — Euclid-এর ধাপ ধরে coefficient বয়ে নিয়ে a·x + b·y = gcd বের করা (Bézout's identity)। মূল reusable টুকরো: base (a, 1, 0), আর update x = y1, y = x1 − (a // b)·y1। modular inverse-এর সময় এই pattern সরাসরি ফিরবে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "Extended GCD = সাধারণ Euclid + coefficient বয়ে আনা; base (a,1,0), update x=y1, y=x1−(a//b)·y1। 'a·x + b·y = gcd' দরকার দেখলেই এটা মনে করব — আর Level 2-তে modular inverse এখান থেকেই আসবে।"

পরের ধাপ → 020 — LCM using GCD (এবার gcd-র সহজ আত্মীয় LCM)। শিকড় → 018 — GCD using Euclidean Algorithm।

ফিরে দেখা: এই 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" দাবি করা হয়নি — বরং "common interview pattern" লেখা হয়েছে।