126 — Linear Diophantine Equation

এই note-টা 125-এর সরাসরি উত্তরসূরি — extended Euclid যে x, y বানাল, এবার সেটা দিয়ে আসল সমীকরণ সমাধান করব। মনে করিয়ে দিই: এই Level 10 মূলত competitive programming-ঘেঁষা, interview-এর জন্য optional — Diophantine interview-তে প্রায় আসে না, কিন্তু CP-তে এটা নিত্যসঙ্গী। তাড়া নেই; 125 ভালো করে বুঝে থাকলে এটা মাখনের মতো গলে যাবে।

Source

• Original source: CP-Algorithms — Linear Diophantine Equation
• Platform: CP-Algorithms — https://cp-algorithms.com/algebra/linear-diophantine-equation.html
• Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
• Difficulty: Medium
• Pattern: gcd divisibility
• Basic idea inherited from: 125 (Extended Euclidean Algorithm)

1. Problem in simple words

তিনটা integer a, b, c দেওয়া আছে। খুঁজে বের করতে হবে এমন integer x আর y, যাতে এই সমীকরণটা মেলে:

a · x + b · y = c

এটাকে বলে linear Diophantine equation — "Diophantine" মানে আমরা শুধু integer সমাধান চাই (ভগ্নাংশ নয়)। দুটো প্রশ্ন:

1. সমাধান আছে কি না? (সব ক্ষেত্রে থাকে না!)
2. থাকলে — একটা সমাধান, আর সেই সাথে সব সমাধানের সূত্র।

মনে রেখো — এই level CP-leaning, interview-optional। কিন্তু "কখন integer সমাধান সম্ভব" এই প্রশ্নের উত্তরটা সংখ্যাতত্ত্বের একটা সুন্দর ছোট রত্ন।

2. What is the math idea?

মূল idea একটাই বাক্যে — solvable ⟺ gcd(a, b) ভাগ করে c-কে:

a·x + b·y = c  এর integer সমাধান আছে  ⟺  gcd(a, b) | c

কেন? কারণ a·x + b·y যাই হোক না কেন, সেটা সবসময় gcd(a, b)-এর গুণিতক (g যেহেতু a, b দুটোকেই ভাগ করে, সে তাদের যেকোনো combination-কেও ভাগ করে)। তাই c যদি g-এর গুণিতক না হয়, সমাধান অসম্ভব। আর হলে — extended Euclid (125) থেকে a·x₀ + b·y₀ = g পেয়ে দুপাশে c/g গুণ করলেই এক সমাধান। এই level CP-leaning হলেও এই divisibility শর্তটাই পুরো problem-এর হৃদয়।

3. Which basic idea does this inherit from?

এটা সরাসরি 125 (Extended Euclidean Algorithm)-এর উপর দাঁড়ানো। 125 আমাদের দিয়েছিল x₀, y₀ যাতে a·x₀ + b·y₀ = gcd(a, b)। Diophantine সেই ছোট জয়টাকে scale করে:

a·x₀ + b·y₀ = g          (125 থেকে)
দুপাশে (c/g) গুণ:
a·(x₀·c/g) + b·(y₀·c/g) = c
⇒ x = x₀·(c/g),  y = y₀·(c/g)

মানে 125 না বুঝে 126-এ ঢোকা যায় না — extended Euclid-ই এর ইঞ্জিন। আর এর উপরে দাঁড়াবে CRT (127), যেখানে দুটো congruence merge করতে এই একই combination-চিন্তা লাগে।

4. Real-life analogy

ভাবো তোমার কাছে দুই ধরনের কয়েন আছে — a টাকার আর b টাকার। তুমি ঠিক c টাকা বানাতে চাও। কিন্তু একটা মোচড় আছে: কয়েন তুমি যোগও করতে পারো, আবার কাউকে ফেরতও দিতে পারো (negative = ফেরত)।

• যদি দুই কয়েনের "সবচেয়ে ছোট ধাপ" (gcd) হয় 5 টাকা, তাহলে তুমি শুধু 5-এর গুণিতক বানাতে পারবে — 5, 10, 15, ... । 12 টাকা বানানো অসম্ভব, কারণ 12 ÷ 5-এ ভাগশেষ থাকে।
• কিন্তু c যদি 5-এর গুণিতক হয় (যেমন 20), তাহলে সম্ভব — আর সম্ভব অসংখ্যভাবে: একটা সমাধান পেলে কিছু a-কয়েন বেশি দিয়ে কিছু b-কয়েন কম দিলেই আরেকটা সমাধান।

সেই "gcd ভাগ করে কি না" চেকটাই solvability; আর "অসংখ্যভাবে" অংশটাই solution family।

5. Visual explanation

30x + 18y = 12 সমাধান করি। আগে solvability, তারপর এক সমাধান, তারপর পরিবার:

ধাপ 1 — solvability:
  gcd(30, 18) = 6,   c = 12,   12 % 6 = 0  ->  সমাধান আছে ✓

ধাপ 2 — extended Euclid (125 থেকে):
  30·(−1) + 18·(2) = 6        ->  x₀ = −1, y₀ = 2, g = 6

ধাপ 3 — c/g দিয়ে scale (k = 12 / 6 = 2):
  x = x₀·k = −1·2 = −2
  y = y₀·k =  2·2 =  4
  যাচাই:  30·(−2) + 18·(4) = −60 + 72 = 12  ✓

ধাপ 4 — পুরো পরিবার (t = যেকোনো integer):
  x = −2 + t·(18/6) = −2 + 3t
  y =  4 − t·(30/6) =  4 − 5t
  t = 1:  x = 1,  y = −1  ->  30·1 + 18·(−1) = 12 ✓
  t = 2:  x = 4,  y = −6  ->  30·4 + 18·(−6) = 12 ✓

দাঁড়িপাল্লার ছবি: x-কে b/g = 3 বাড়ালে যোগফলে 30·3 = 90 বাড়ে; y-কে a/g = 5 কমালে 18·5 = 90 কমে — দুই পাশ সমান, যোগফল অপরিবর্তিত c। তাই অসীম সমাধান।

6. Example input and output

input (a, b, c)  ->  output
------------------------------------------------------------------
   30, 18, 12    ->  (-2, 4)         30·(-2) + 18·4 = 12   ✓
   30, 18, 11    ->  None            11 % gcd(6) ≠ 0 -> সমাধান নেই
    2,  3,  7    ->  (7, -7) বা সমতুল্য   2·7 + 3·(-7) = -7? না -> দেখো নিচে
   35, 15,  5    ->  (1, -2)         35·1 + 15·(-2) = 5    ✓
    6,  9, 15    ->  (-5, 5) বা সমতুল্য   6·(-5)+9·5 = 15   ✓

খেয়াল করো: 2x + 3y = 7-এ gcd(2, 3) = 1, আর 7 % 1 = 0 — তাই সমাধান আছে (যেমন x = 2, y = 1: 2·2 + 3·1 = 7)। আমাদের সূত্র x₀·k দিয়ে অন্য একটা valid জোড়া দিতে পারে; x, y unique নয় — তাই যেকোনো জোড়া a·x + b·y == c মেলালেই সঠিক। আর 30x + 18y = 11-এ 11, 6-এর গুণিতক নয় → None (সমাধান নেই)। এটাই সবচেয়ে গুরুত্বপূর্ণ edge case।

7. Brute force thinking

extended Euclid ছাড়া প্রথম যে idea আসে — একটা variable ঘুরিয়ে অন্যটা মিলে যায় কিনা দেখা। ধরো x-কে একটা range-এ ঘোরাই; প্রতিটা x-এর জন্য চেক করি (c − a·x) কি b দিয়ে নিঃশেষে ভাগ যায় — গেলে y = (c − a·x) // b:

def diophantine_brute(a, b, c, search=2000):
    for x in range(-search, search + 1):
        rem = c - a * x
        if b != 0 and rem % b == 0:
            return x, rem // b
    return None

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

8. Why brute force may be slow

দুটো সমস্যা। এক — range কত বড় নেব তার নিশ্চয়তা নেই; সমাধানের x বিশাল (যেমন কোটির ঘরে) হতে পারে, তখন ছোট search window-তে মিস করে ভুল করে "None" বলবে। দুই — window বড় করলে loop লম্বা হয়, O(search) সময়।

সমাধানের x ছোট (|x| < 2000):   brute force পায়, কিন্তু ধীর
সমাধানের x বিশাল (10⁹):         brute force হয় miss করে, নয় কোটি বার loop
extended Euclid:                সবসময়, O(log min(a,b)) ধাপে সরাসরি x₀

মূল কথা: brute force-এর কোনো নিশ্চয়তা নেই (ঠিক window না নিলে ভুল), আর বড় সমাধানে ধীর। অথচ extended Euclid গণিতগতভাবে নিশ্চিত করে এক সমাধান দেয়, log ধাপে।

9. Better thinking

মূল insight দুই অংশে:

অংশ ১ — solvability আগে যাচাই করো। g = gcd(a, b) বের করে দেখো c % g == 0 কিনা। না হলে সোজা "None" — আর এক লাইনও কোড লাগে না। এই শর্তটাই algorithm-এর প্রথম লাইন।

অংশ ২ — extended Euclid দিয়ে scale করো। 125 থেকে a·x₀ + b·y₀ = g পাও, তারপর k = c // g দিয়ে গুণ:

x = x₀ · k,   y = y₀ · k

ব্যস, এক সমাধান তৈরি। আর সব সমাধান চাইলে পরিবার:

x = x₀·k + t·(b // g)
y = y₀·k − t·(a // g)       t = যেকোনো integer

এই family-র সৌন্দর্য: t বদলালে a·x যতটা বাড়ে, b·y ঠিক ততটা কমে — তাই যোগফল সবসময় c।

10. Thinking tweak

আসল "আহা" মুহূর্ত: "কখন সমাধান সম্ভব?" — এই গোটা প্রশ্নের উত্তর মাত্র একটা divisibility চেক: c % gcd(a, b) == 0।

brute force পুরো range চষছিল আদৌ সমাধান আছে কিনা জানতেও; tweak হলো — খোঁজার আগেই gcd দিয়ে এক লাইনে রায় দাও। আর থাকলে, খোঁজা লাগে না — 125-এর x₀, y₀-কে c/g দিয়ে গুণ করলেই হাতে এক সমাধান। অনিশ্চিত O(search) থেকে নিশ্চিত O(log min(a, b))-এ নেমে এল।

11. Step-by-step dry run

30x + 18y = 12-এর জন্য diophantine(30, 18, 12):

step	কী করছি	মান
1	g, x₀, y₀ = ext_gcd(30, 18)	g = 6, x₀ = −1, y₀ = 2
2	c % g চেক: 12 % 6	0 → সমাধান আছে
3	k = c // g = 12 // 6	k = 2
4	x = x₀·k = −1·2	x = −2
5	y = y₀·k = 2·2	y = 4
6	যাচাই: 30·(−2) + 18·4	−60 + 72 = 12 ✓

পরিবার বের করতে (যদি সব সমাধান চাই):

step	সূত্র	মান
7	b // g = 18 // 6	3 (x-এর ধাপ)
8	a // g = 30 // 6	5 (y-এর ধাপ)
9	t = 1: x = −2 + 3, y = 4 − 5	(1, −1) → 30·1 + 18·(−1) = 12 ✓

দেখো — base solution (−2, 4) থেকে t বদলে অন্য সমাধান (1, −1) পেলাম, যোগফল দুটোতেই 12।

12. Python solution

from math import gcd


def ext_gcd(a, b):
    """a*x + b*y = gcd(a, b) এর (g, x, y) ফেরত দেয় (125 থেকে)।"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def diophantine(a, b, c):
    """a*x + b*y = c এর একটা (x, y) ফেরত দেয়, সমাধান না থাকলে None।"""
    g, x0, y0 = ext_gcd(a, b)
    if c % g != 0:
        return None                      # gcd(a,b) ভাগ করে না c-কে
    k = c // g
    return x0 * k, y0 * k


def diophantine_family(a, b, c, t):
    """একই সমীকরণের t-তম সমাধান (পরিবারের যেকোনো সদস্য)।"""
    base = diophantine(a, b, c)
    if base is None:
        return None
    x0, y0 = base
    g = gcd(a, b)
    return x0 + t * (b // g), y0 - t * (a // g)


# --- ছোট test গুলো (সব pass করা উচিত) ---
def verify(a, b, c, must_exist):
    sol = diophantine(a, b, c)
    if not must_exist:
        assert sol is None, f"সমাধান থাকার কথা না: {a},{b},{c}"
        return
    assert sol is not None, f"সমাধান থাকার কথা: {a},{b},{c}"
    x, y = sol
    assert a * x + b * y == c, f"identity ভুল: {a},{b},{c} -> {sol}"
    # পরিবারের কয়েকটা সদস্যও যাচাই
    for t in (-3, -1, 0, 1, 2, 5):
        fx, fy = diophantine_family(a, b, c, t)
        assert a * fx + b * fy == c, f"family ভুল: {a},{b},{c}, t={t}"

verify(30, 18, 12, True)
verify(30, 18, 11, False)     # 11, 6-এর গুণিতক নয়
verify(35, 15, 5, True)
verify(2, 3, 7, True)
verify(6, 9, 15, True)
verify(6, 9, 14, False)       # 14, 3-এর গুণিতক নয়
verify(1, 1, 100, True)
verify(12, 8, 0, True)        # c = 0 -> (0, 0) সবসময় সমাধান

x, y = diophantine(30, 18, 12)
assert 30 * x + 18 * y == 12

print(diophantine(30, 18, 12))        # (-2, 4)
print(diophantine(30, 18, 11))        # None
print(diophantine_family(30, 18, 12, 1))  # (1, -1)
print("সব test pass!")

13. Line-by-line explanation

def diophantine(a, b, c):
    g, x0, y0 = ext_gcd(a, b)

প্রথমে 125-এর extended Euclid ডাকছি — পাচ্ছি g = gcd, আর x₀, y₀ যাতে a·x₀ + b·y₀ = g।

    if c % g != 0:
        return None

solvability-র মূল চেক — c যদি g-এর গুণিতক না হয়, integer সমাধান অসম্ভব, সোজা None। এটাই algorithm-এর প্রথম ও সবচেয়ে গুরুত্বপূর্ণ লাইন।

    k = c // g
    return x0 * k, y0 * k

scale করছি — a·x₀ + b·y₀ = g-এর দুপাশে k = c/g গুণ করলে a·(x₀k) + b·(y₀k) = c। তাই (x₀·k, y₀·k) একটা সমাধান।

def diophantine_family(a, b, c, t):
    ...
    return x0 + t * (b // g), y0 - t * (a // g)

পরিবারের t-তম সদস্য — base solution থেকে x-কে t·(b/g) বাড়িয়ে, y-কে t·(a/g) কমিয়ে। এই বাড়া-কমা ঠিক সমান ওজনের, তাই যোগফল c অপরিবর্তিত।

বাকি verify function ও assert লাইনগুলো নিজেরাই যাচাই করে — solvable হলে identity মেলে কিনা, পরিবারের সদস্যরাও মেলে কিনা, আর unsolvable হলে সত্যিই None আসে কিনা। সব ঠিক থাকলে শেষে সব test pass!।

14. Output walkthrough

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

(-2, 4)
None
(1, -1)
সব test pass!

প্রথম লাইন diophantine(30, 18, 12) → (−2, 4), যা 30·(−2) + 18·4 = 12 মেলায়। দ্বিতীয় diophantine(30, 18, 11) → None, কারণ 11, gcd 6-এর গুণিতক নয়। তৃতীয় diophantine_family(30, 18, 12, 1) → (1, −1), পরিবারের আরেক সদস্য (30·1 + 18·(−1) = 12)। আগের সব assert চুপচাপ pass — তাই সব test pass!।

15. Time complexity

O(log min(a, b)) — পুরো খরচ extended Euclid-এর, যা Euclid-এর মতোই logarithmic। তার পরে শুধু একটা ভাগ, একটা গুণ, একটা mod — সব O(1)। তাই brute force-এর অনিশ্চিত O(search)-এর তুলনায় এটা নিশ্চিত ও দ্রুত।

16. Space complexity

O(log min(a, b)) recursive ext_gcd-এর জন্য (call stack); iterative ext_gcd ব্যবহার করলে O(1)। মূল diophantine function নিজে কোনো extra array রাখে না, শুধু গুটিকয় variable।

17. Common mistakes

1. solvability চেক না করেই solution খোঁজা — সবচেয়ে কমন। c % g != 0 হলে সমাধান নেই; এই লাইন বাদ দিলে ভুল উত্তর। আগে শর্ত, পরে খোঁজা।
2. g দিয়ে নয়, ভুল সংখ্যা দিয়ে scale — k হলো c // g, c // a বা অন্য কিছু নয়।
3. family-র সূত্রে a, b উল্টে ফেলা — x বাড়ে b/g দিয়ে, y কমে a/g দিয়ে (cross করা)। উল্টে ফেললে যোগফল আর c থাকে না।
4. একটা সমাধানকেই একমাত্র ভাবা — অসীম সমাধান আছে; reference-এর সাথে হুবহু না মিললেও identity মিললেই সঠিক।
5. a বা b শূন্য ভুলে যাওয়া — যেমন a = 0 হলে সমীকরণ b·y = c, আলাদা করে ভাবা ভালো (যদিও ext_gcd এ-ও সামলায়, brute force সামলায় না)।

18. Harder problems that inherit this idea

• CSES — Stick Lengths / coin-style আর অনেক Codeforces problem যেখানে "ঠিক c বানানো যায় কিনা integer combination-এ" — সরাসরি Diophantine solvability।
• Codeforces — problemset-এ "ax + by = c" ধরনের constructive problem (https://codeforces.com/problemset) — solvability + এক সমাধান + non-negative সমাধান খোঁজা।
• 127 (CRT) — এই repo-রই পরের ধাপ, যেখানে দুটো congruence merge করতে এই combination-চিন্তা সরাসরি লাগে।

19. Pattern learned

gcd divisibility test for solvability — a·x + b·y = c integer-সমাধানযোগ্য ঠিক তখনই যখন gcd(a, b) | c; থাকলে extended Euclid-এর base solution-কে c/g দিয়ে scale করো, আর পরিবার x ± t·(b/g)। বড় শিক্ষা: খোঁজার আগে জিজ্ঞেস করো "আদৌ সম্ভব কি?" — অনেক সময় একটা divisibility চেকই পুরো উত্তর দিয়ে দেয়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Diophantine ax + by = c solvable ⟺ gcd(a,b) | c; থাকলে ext_gcd-এর (x₀, y₀)-কে c/g গুণ করো, পরিবার x + t·b/g, y − t·a/g।" Signal: "integer combination-এ ঠিক c বানানো যায় কি?" — দেখলেই এই gcd-divisibility pattern মনে পড়বে।

পরের ধাপ → 127 — Chinese Remainder Theorem Basic (দুটো congruence merge, আবার ext-gcd)। ভিত্তি → 125 — Extended 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" এমন দাবি করা হয়নি — এই level CP-leaning, interview-optional।