GCD আর Euclid-এর algorithm — Bézout আর extended Euclid

১ · সমান প্যাকেট আর একসঙ্গে ডেলিভারি — gcd আর lcm

বাজারঘরের গুদামে ২৫২টি সাবান আর ১৯৮টি শ্যাম্পু আছে। ঈদের উপহার হিসেবে এগুলো এমন কয়েকটি প্যাকেটে ভাগ করতে হবে, যাতে প্রতিটি প্যাকেট হুবহু এক রকম হয় (একই সংখ্যক সাবান, একই সংখ্যক শ্যাম্পু) আর কিছুই বাকি না থাকে। সবচেয়ে বেশি কয়টি প্যাকেট বানানো যায়? প্যাকেটের সংখ্যা ২৫২ আর ১৯৮ দুটিকেই নিঃশেষে ভাগ করতে হবে, আর আমরা চাই সবচেয়ে বড় এমন সংখ্যা। উত্তর ১৮: প্রতিটি প্যাকেটে ১৪টি সাবান আর ১১টি শ্যাম্পু। এটিই gcd (greatest common divisor, স্কুলের “গসাগু”)।

উল্টো ধরনের প্রশ্নও আছে। বাজারঘরের একটি ভ্যান প্রতি ৬ দিনে একবার সিলেটে যায়, আরেকটি প্রতি ৯ দিনে একবার। আজ দুটিই গেছে; আবার কবে একসঙ্গে যাবে? দিনের সংখ্যাটি ৬ আর ৯ দুটিরই গুণিতক হতে হবে, আর আমরা চাই সবচেয়ে ছোট ধনাত্মকটি: ১৮ দিন পরে। এটি lcm (least common multiple, স্কুলের “লসাগু”)। এই পর্বে দুটি ধারণাকে সঠিক সংজ্ঞায় বাঁধব, আর দেখব gcd বের করার একটি ২,৩০০ বছরের পুরোনো পদ্ধতি কেন আজও কম্পিউটারের প্রতিটি নিরাপদ সংযোগে কাজ করে।

কয়েকটি ছোট বিষয় খেয়াল করুন। (১) 1 সবসময় একটি সাধারণ ভাজক, আর কোনো অশূন্য সংখ্যার ভাজক তার পরম মানের চেয়ে বড় হতে পারে না; তাই সাধারণ ভাজকের সেট অশূন্য আর ওপরে সীমিত, ফলে gcd সবসময় আছে আর তা ≥ 1. (২) ভাজক চিহ্নের তোয়াক্কা করে না, তাই gcd(a, b) = gcd(|a|, |b|); যেমন gcd(−12, 18) = 6. (৩) gcd(a, 0) = |a|, কারণ প্রতিটি সংখ্যা 0-কে ভাগ করে (0 = d · 0). (৪) gcd(0, 0) সংজ্ঞায়িত নয়, কারণ প্রতিটি পূর্ণসংখ্যাই 0-কে ভাগ করে, সবচেয়ে বড়টি নেই; অনেক প্রোগ্রামিং ভাষা সুবিধার জন্য একে 0 ধরে, Python-এর math.gcd(0, 0)-ও 0 দেয়।

মৌলিক গুণনীয়ক দিয়ে gcd আর lcm

স্কুলে gcd বের করা হয় দুটি সংখ্যাকে মৌলিক গুণনীয়কে ভেঙে। 252 = 2² · 3² · 7 আর 198 = 2 · 3² · 11. দুটিতেই আছে 2 আর 3; প্রতিটির ছোট ঘাত নিলে gcd = 2¹ · 3² = 18. সব মৌলিক সংখ্যার বড় ঘাত নিলে lcm = 2² · 3² · 7 · 11 = 2772. এই পদ্ধতিকে উপপাদ্য হিসেবে লেখা যাক। প্রতিটি n ≥ 2 মৌলিক সংখ্যার গুণফল, তা আমরা পর্ব ১১-এ strong induction দিয়ে প্রমাণ করেছি; এই ভাঙন যে একভাবেই হয়, তা পর্ব ২০-এর fundamental theorem of arithmetic.

এখানে ∏ হলো গুণফলের চিহ্ন (∑-এর মতো, কিন্তু যোগের বদলে গুণ), আর min, max মানে দুটির ছোট আর বড়টি।

প্রমাণ:

1. একটি ধনাত্মক d, a-কে ভাগ করে ⇔ d = ∏ p^δ_p, যেখানে প্রতিটি p-তে 0 ≤ δ_p ≤ α_p. কারণ a = dk হলে d আর k-এর ভাঙন একসঙ্গে a-এর ভাঙন দেয়, আর ভাঙন অনন্য বলে ঘাতগুলো যোগ হয়ে α_p হয়; উল্টো দিকে k = ∏ p^{α_p − δ_p} নিলেই চলে। — অনন্য factorization
2. তাই d সাধারণ ভাজক ⇔ প্রতিটি p-তে δ_p ≤ min(α_p, β_p). প্রতিটি ঘাত সর্বোচ্চ নিলে সবচেয়ে বড় সাধারণ ভাজক পাওয়া যায়, তাই gcd-এর সূত্রটি। — ধাপ ১, দুবার
3. একইভাবে m-কে a আর b দুটিই ভাগ করে ⇔ প্রতিটি p-তে m-এর ঘাত ≥ max(α_p, β_p). প্রতিটি ঘাত সর্বনিম্ন নিলে সবচেয়ে ছোট এমন m, তাই lcm-এর সূত্রটি। — ধাপ ১
4. যেকোনো দুটি সংখ্যায় min(α, β) + max(α, β) = α + β (একটি ছোটটি, অন্যটি বড়টি). প্রতিটি p-তে ঘাত যোগ করলে gcd · lcm-এর ঘাত α_p + β_p, যা ঠিক ab-এর ঘাত। ∎ — ঘাতের যোগ

উদাহরণে: 18 · 2772 = 49896 = 252 · 198. আর ভ্যানের প্রশ্নে lcm(6, 9) = 6 · 9 / gcd(6, 9) = 54 / 3 = 18, আগের উত্তরই। কিন্তু একটি সতর্কতা। এই প্রমাণ দাঁড়িয়ে আছে factorization অনন্য হওয়ার ওপর, আর প্রথাগত পথে সেই অনন্যতার প্রমাণে লাগে Euclid-এর লেমা, যা আমরা §৫-এ প্রমাণ করব; পর্ব ২০ অবশ্য অন্য পথে, minimal counterexample দিয়ে, লেমা ছাড়াই অনন্যতা প্রমাণ করেছে। যুক্তিটি বৃত্তাকার নয়, কারণ §৫-এর প্রমাণ factorization একেবারেই ব্যবহার করে না; শুধু Bézout, আর Bézout শুধু well-ordering. ছবি ৫.১-এ এই নির্ভরতার শিকলটি দেখবেন। আর একটি ব্যবহারিক সমস্যা: বড় সংখ্যাকে মৌলিক গুণনীয়কে ভাঙা খুবই কঠিন, যা পর্ব ২৫ “Primality test আর factoring”-এর বিষয়। তাই gcd বের করতে আমাদের এমন একটি পদ্ধতি লাগবে, যা factorization ছাড়াই কাজ করে।

২ · Euclid-এর algorithm — কেন gcd(a, b) = gcd(b, a mod b)

মূল পর্যবেক্ষণটি সহজ। ২৫২টি সাবান আর ১৯৮টি শ্যাম্পুকে যদি d-টি সমান প্যাকেটে ভাগ করা যায়, তবে “সাবান বিয়োগ শ্যাম্পু”, অর্থাৎ ৫৪-কেও d ভাগ করে। উল্টো দিকে, d যদি ১৯৮ আর ৫৪-কে ভাগ করে, তবে তাদের যোগফল ২৫২-কেও ভাগ করে। তাই (252, 198) আর (198, 54)-এর সাধারণ ভাজক হুবহু এক, ফলে gcd-ও এক। একবার বিয়োগের বদলে যতবার সম্ভব বিয়োগ করলে, অর্থাৎ ভাগশেষ নিলে, একই যুক্তি খাটে। x mod y মানে x-কে y দিয়ে ভাগ করার ভাগশেষ (modulo), যা division algorithm দেয়: y > 0 হলে অনন্য q, r আছে যাতে x = qy + r আর 0 ≤ r < y (অস্তিত্বের প্রমাণ পর্ব ১১-এ)।

প্রমাণ: (এর লুপ-রূপটি পর্ব ১৩-এর লেমা ৬.২-এ invariant হিসেবে এসেছে; এখানে সংখ্যাতত্ত্বের ভাষায়।)

1. Division algorithm দিয়ে a = qb + r, যেখানে r = a mod b. — division algorithm
2. d ∣ a আর d ∣ b হলে r = a − qb, যা d-এর দুটি গুণিতকের পূর্ণসংখ্যা-সমন্বয়, তাই d ∣ r. — a = dk, b = dl ⇒ r = d(k − ql)
3. উল্টো দিকে d ∣ b আর d ∣ r হলে a = qb + r, তাই d ∣ a. — একই যুক্তি
4. ফলে (a, b) আর (b, r)-এর সাধারণ ভাজকের সেট একই। b > 0, তাই দুটি জোড়াই (0, 0) নয়, আর একই সেটের সবচেয়ে বড় উপাদান একই। ∎

লেমাটি বারবার লাগালেই Euclid-এর algorithm: (a, b) থেকে (b, a mod b), তারপর আবার, যতক্ষণ না দ্বিতীয় সংখ্যাটি 0 হয়। তখন gcd(x, 0) = x. প্রতিবার দ্বিতীয় সংখ্যা কঠোরভাবে কমে কিন্তু ঋণাত্মক হয় না, তাই well-ordering অনুযায়ী লুপটি থামে; এই termination-এর পূর্ণ প্রমাণ পর্ব ১৩-এ। পর্ব ১২-এ একই নিয়মকে আমরা gcd-এর recursive সংজ্ঞা হিসেবে দেখেছি। নিচের stepper (252, 198)-এ প্রতিটি ধাপ দেখায়।

1a, b = 252, 1982while b != 0:3    q, r = a // b, a % b4    a, b = b, r5print(a)   # gcd

কত ধাপ লাগে?

বারবার বিয়োগ করলে gcd(1000001, 1) পেতে দশ লক্ষ ধাপ লাগত। ভাগশেষ নিলে লাগে এক ধাপ। সাধারণভাবে দ্রুততার কারণ নিচের সরল উপপাদ্য।

প্রমাণ:

1. r_i+2 = r_i mod r_i+1 < r_i+1. — ভাগশেষ ভাজকের চেয়ে ছোট
2. ক্ষেত্র ১: r_i+1 ≤ r_i/2. তাহলে ধাপ ১ থেকে r_i+2 < r_i+1 ≤ r_i/2. — proof by cases
3. ক্ষেত্র ২: r_i+1 > r_i/2. তাহলে r_i < 2r_i+1, তাই ভাগফল ঠিক 1, আর r_i+2 = r_i − r_i+1 < r_i − r_i/2 = r_i/2. — বীজগণিত
4. প্রতি দুই ধাপে সংখ্যা অর্ধেকের নিচে নামে, আর ধনাত্মক পূর্ণসংখ্যা log₂ b বারের বেশি অর্ধেক হতে পারে না আগে 1-এর নিচে নামার। ∎

আরও সূক্ষ্ম সীমা Gabriel Lamé-এর ১৮৪৪ সালের উপপাদ্য: ধাপের সংখ্যা ছোট সংখ্যাটির দশমিক অঙ্ক-সংখ্যার পাঁচগুণের বেশি নয়, আর সবচেয়ে খারাপ ইনপুট পরপর দুটি Fibonacci সংখ্যা। এর আলোচনা আর পরীক্ষা পর্ব ১৩-এ আছে। মোট কথা: ৩০০ অঙ্কের সংখ্যাতেও Euclid কয়েকশো ধাপে শেষ হয়, অথচ সেই সংখ্যাকে factorize করা আজকের জানা পদ্ধতিতে কার্যত অসম্ভব।

নিচের ব্লক দুটি পদ্ধতিকে পাশাপাশি রাখে: মৌলিক গুণনীয়ক দিয়ে gcd আর lcm (trial division, কতগুলো ভাজক পরীক্ষা হলো তা গুনে), আর Euclid (কয় ধাপ লাগল)। দ্বিতীয় জোড়াটি 10007 · 9973 আর 10007 · 10009, তিনটিই মৌলিক। শেষে ৫,০০০টি এলোমেলো জোড়ায় gcd · lcm = ab পরীক্ষা হয়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from math import gcd, lcm
import random
def factor(n):                     # trial division; also counts the divisors tried
    f, p, tries = {}, 2, 0
    while p * p <= n:
        tries += 1
        while n % p == 0:
            f[p] = f.get(p, 0) + 1
            n //= p
        p += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f, tries
def gcd_lcm_by_factors(a, b):      # min of exponents for gcd, max for lcm
    (fa, ta), (fb, tb) = factor(a), factor(b)
    g = l = 1
    for p in fa.keys() | fb.keys():
        g *= p ** min(fa.get(p, 0), fb.get(p, 0))
        l *= p ** max(fa.get(p, 0), fb.get(p, 0))
    return g, l, ta + tb
def euclid(a, b):
    steps = 0
    while b:
        a, b, steps = b, a % b, steps + 1
    return a, steps

print("252 =", factor(252)[0], "  198 =", factor(198)[0])
for a, b in [(252, 198), (10007 * 9973, 10007 * 10009)]:
    g, l, tries = gcd_lcm_by_factors(a, b)
    g2, steps = euclid(a, b)
    print(f"a={a} b={b}: gcd {g} (Euclid {g2}), lcm {l}")
    print(f"   trial divisions: {tries},  Euclid steps: {steps}")
random.seed(7)
pairs = [(random.randint(1, 10**6), random.randint(1, 10**6)) for _ in range(5000)]
print("gcd*lcm == a*b on 5000 pairs:", all(gcd(a, b) * lcm(a, b) == a * b for a, b in pairs))

252 = {2: 2, 3: 2, 7: 1}   198 = {2: 1, 3: 2, 11: 1}
a=252 b=198: gcd 18 (Euclid 18), lcm 2772
   trial divisions: 4,  Euclid steps: 4
a=99799811 b=100160063: gcd 10007 (Euclid 10007), lcm 998896308299
   trial divisions: 19978,  Euclid steps: 4
gcd*lcm == a*b on 5000 pairs: True

৩ · Bézout-এর অভেদ — gcd একটি linear combination

বাজারঘরের পুরোনো দাঁড়িপাল্লায় মাত্র দুই রকম বাটখারা: ২৪০ গ্রাম আর ৪৬ গ্রাম, যতগুলো খুশি। বাটখারা দুই পাল্লাতেই রাখা যায়। সবচেয়ে ছোট কত ওজন মাপা যায়? এক পাল্লায় ৪৭টি ৪৬ গ্রাম (২,১৬২ গ্রাম), অন্য পাল্লায় ৯টি ২৪০ গ্রাম (২,১৬০ গ্রাম) রাখলে পার্থক্য ঠিক ২ গ্রাম। আর ২-এর কম ধনাত্মক ওজন অসম্ভব, কারণ ২৪০ আর ৪৬ দুটিই জোড়, তাই যেকোনো পার্থক্যও জোড়। লক্ষ করুন, ২ = gcd(240, 46). কাকতালীয় নয়।

এই ফলের ইংরেজি নাম Bézout's identity, বাংলায় Bézout-এর অভেদ। প্রমাণটি পর্ব ১১-এর well-ordering principle-এর একটি সুন্দর প্রয়োগ: ℕ-এর প্রতিটি অশূন্য উপসেটে একটি ক্ষুদ্রতম উপাদান আছে।

প্রমাণ: S = {ax + by : x, y ∈ ℤ, ax + by > 0} ধরি, অর্থাৎ ধনাত্মক linear combination-গুলোর সেট।

1. S অশূন্য: x = a, y = b নিলে a² + b² > 0, কারণ a, b দুটিই শূন্য নয়। — সরাসরি উদাহরণ
2. S ⊆ ℕ আর অশূন্য, তাই এর একটি ক্ষুদ্রতম উপাদান d আছে; লিখি d = ax₀ + by₀. — well-ordering
3. দাবি d ∣ a. Division algorithm দিয়ে a = qd + r, 0 ≤ r < d. তাহলে r = a − q(ax₀ + by₀) = a(1 − qx₀) + b(−qy₀), অর্থাৎ r নিজেও একটি linear combination. — division algorithm, বীজগণিত
4. r > 0 হলে r ∈ S আর r < d, যা d ক্ষুদ্রতম হওয়ার বিরোধী। তাই r = 0, অর্থাৎ d ∣ a. একই যুক্তিতে d ∣ b. — proof by contradiction
5. তাই d একটি সাধারণ ভাজক। এখন c যেকোনো সাধারণ ভাজক হলে c ∣ ax₀ + by₀ = d, আর d > 0, তাই c ≤ |c| ≤ d. — ভাজক তার গুণিতকের চেয়ে বড় নয়
6. d সাধারণ ভাজক আর সব সাধারণ ভাজকের চেয়ে ছোট নয়, তাই d = gcd(a, b). ∎

প্রমাণের ধাপ ৫ থেকে একটি শক্তিশালী ফল বিনা খরচে আসে, যা পরের সব অংশে লাগবে।

প্রমাণ: (ক) c ∣ a আর c ∣ b হলে c ∣ ax₀ + by₀ = gcd(a, b). (খ) (⇒) Bézout সরাসরি। (⇐) ax + by = 1 হলে প্রতিটি সাধারণ ভাজক 1-কে ভাগ করে, তাই সেটি ±1, আর gcd = 1. (গ) d = gcd ভাগ করে a আর b-কে, তাই প্রতিটি ax + by-কে; উল্টো দিকে d-এর গুণিতক kd = a(kx₀) + b(ky₀). ∎

(খ)-এর (⇐) দিকটি খেয়াল করুন: ax + by = 1 থেকে gcd = 1 আসে, কিন্তু ax + by = 6 থেকে gcd = 6 আসে না, শুধু gcd ∣ 6 আসে। যেমন 4 · (−3) + 9 · 2 = 6, অথচ gcd(4, 9) = 1. এই ভুলটি পরীক্ষায় আর AI-এর উত্তরে প্রায়ই দেখা যায়।

তবে Bézout-এর প্রমাণটি nonconstructive: x₀, y₀ আছে বলে, কিন্তু খুঁজে দেয় না (পর্ব ০৯-এ existence proof-এর দুই ধরন দেখেছেন)। S অসীম সেট, তার ক্ষুদ্রতম উপাদান একে একে খুঁজে পাওয়া যায় না। পরের অংশে Euclid-এর algorithm-কেই একটু বাড়িয়ে আমরা একটি constructive প্রমাণ পাব।

৪ · Extended Euclid — টেবিলে x আর y খোঁজা

ধারণাটি হলো: Euclid-এর প্রতিটি ভাগশেষকে শুরুর দুটি সংখ্যার linear combination হিসেবে লিখে রাখা। শুরুর দুটি সারি তো সহজ: a = a · 1 + b · 0 আর b = a · 0 + b · 1. এরপর প্রতিটি নতুন ভাগশেষ আগের দুটি থেকে আসে, r_i+1 = r_i−1 − q_ir_i, আর একই নিয়মে তার সহগগুলোও আসে। শেষ অশূন্য ভাগশেষ gcd, আর তার সারির সহগই Bézout-এর x, y. এই পদ্ধতির নাম extended Euclidean algorithm.

এখানে ⌊x⌋ হলো x-এর floor, x-এর চেয়ে বড় নয় এমন সবচেয়ে বড় পূর্ণসংখ্যা, যা পর্ব ১৬-এ এসেছে।

প্রমাণ (i-এর ওপর strong induction, পর্ব ১১; প্রতিটি সারি আগের দুটির ওপর নির্ভর করে):

1. ভিত্তি i = 0, 1: a · 1 + b · 0 = a = r₀, আর a · 0 + b · 1 = b = r₁. — শুরুর মান
2. Hypothesis: সারি i − 1 আর i-তে দাবিটি সত্য। — অনুমান
3. as_i+1 + bt_i+1 = a(s_i−1 − q_is_i) + b(t_i−1 − q_it_i) = (as_i−1 + bt_i−1) − q_i(as_i + bt_i) = r_i−1 − q_ir_i = r_i+1. — বণ্টন নিয়ম, hypothesis
4. r-গুলো ঠিক Euclid-এর ভাগশেষ, তাই §২ অনুযায়ী শেষ অশূন্যটি gcd. ∎ — লেমা ২.১

এক কথায়, প্রতিটি সারি একটি loop invariant মেনে চলে, যেমন পর্ব ১৩-এ দেখেছেন। নিচের stepper (240, 46)-এ পুরো টেবিলটি এক সারি করে ভরে, আর প্রতি ধাপে invariant মিলিয়ে দেখায়।

1   r    q    s     t2 240    –    1     03  46    –    0     14  10    5    1    −55   6    4   −4    216   4    1    5   −267   2    1   −9    478   0    2   23  −120

হাতে পরীক্ষায় অনেকে অন্য পদ্ধতি ব্যবহার করেন: back-substitution, অর্থাৎ পেছন থেকে প্রতিস্থাপন। Euclid-এর ভাগগুলো লিখে শেষেরটি থেকে উল্টো দিকে যান: 2 = 6 − 1 · 4; 4 = 10 − 1 · 6 বসালে 2 = 2 · 6 − 10; 6 = 46 − 4 · 10 বসালে 2 = 2 · 46 − 9 · 10; 10 = 240 − 5 · 46 বসালে 2 = 47 · 46 − 9 · 240. একই উত্তর। টেবিল পদ্ধতির সুবিধা হলো এটি সামনের দিকে চলে, তাই আগের ভাগগুলো মনে রাখতে হয় না, আর প্রতিটি সারি সঙ্গে সঙ্গে যাচাই করা যায়।

নিচের ব্লক টেবিলটি হুবহু ছাপে, (252, 198)-এর জন্যও, তারপর ১০,০০০টি এলোমেলো বড় জোড়ায় (10¹² পর্যন্ত) প্রতিটি সারির invariant আর শেষ gcd যাচাই করে। Python-এর int যত বড় দরকার তত বড় হতে পারে (arbitrary precision), তাই বড় সংখ্যায় overflow-এর ভয় নেই।

from math import gcd
import random

def ext_table(a, b):          # rows (r, q, s, t) with r = a*s + b*t on every row
    rows = [(a, "", 1, 0), (b, "", 0, 1)]
    while rows[-1][0] != 0:
        (r0, _, s0, t0), (r1, _, s1, t1) = rows[-2], rows[-1]
        q = r0 // r1
        rows.append((r0 - q * r1, q, s0 - q * s1, t0 - q * t1))
    return rows

for a, b in [(240, 46), (252, 198)]:
    rows = ext_table(a, b)
    print(f"a = {a}, b = {b}")
    print("     r    q     s     t")
    for r, q, s, t in rows:
        print(f"{r:6} {q!s:>4} {s:5} {t:5}")
    d, _, s, t = rows[-2]
    print(f"gcd = {d} = {a}*({s}) + {b}*({t})\n")

random.seed(21)
ok = 0
for _ in range(10000):
    a, b = random.randint(1, 10**12), random.randint(1, 10**12)
    rows = ext_table(a, b)
    d, _, s, t = rows[-2]
    every_row = all(r == a * s_ + b * t_ for r, _, s_, t_ in rows)
    ok += (d == gcd(a, b) and every_row)
print("checked on 10000 random pairs (up to 10^12):", ok, "of 10000")
print("pow(17, -1, 3120) =", pow(17, -1, 3120))

a = 240, b = 46
     r    q     s     t
   240          1     0
    46          0     1
    10    5     1    -5
     6    4    -4    21
     4    1     5   -26
     2    1    -9    47
     0    2    23  -120
gcd = 2 = 240*(-9) + 46*(47)

a = 252, b = 198
     r    q     s     t
   252          1     0
   198          0     1
    54    1     1    -1
    36    3    -3     4
    18    1     4    -5
     0    2   -11    14
gcd = 18 = 252*(4) + 198*(-5)

checked on 10000 random pairs (up to 10^12): 10000 of 10000
pow(17, -1, 3120) = 2753

৫ · Euclid-এর লেমা — মৌলিক সংখ্যার বিশেষ ক্ষমতা

12 ∣ 8 · 9 (72 = 12 · 6), কিন্তু 12 ∤ 8 আর 12 ∤ 9. একটি গুণফলকে ভাগ করা মানে কোনো একটি গুণককে ভাগ করা নয়, কারণ 12-এর গুণনীয়কগুলো (4 আর 3) দুটি গুণকে ছড়িয়ে আছে। মৌলিক সংখ্যার ক্ষেত্রে এমন ছড়িয়ে পড়া অসম্ভব, আর সেটিই মৌলিক সংখ্যার সবচেয়ে গুরুত্বপূর্ণ ধর্ম। প্রথমে একটি সাধারণ রূপ।

প্রমাণ:

1. gcd(a, b) = 1, তাই কিছু x, y আছে যাতে ax + by = 1. — Bézout (উপপাদ্য ৩.২)
2. দুই পাশকে c দিয়ে গুণ: c = acx + bcy. — বীজগণিত
3. a ∣ acx স্পষ্ট, আর a ∣ bc বলে a ∣ bcy. দুটি গুণিতকের যোগফলও গুণিতক, তাই a ∣ c. ∎ — বিভাজ্যতার নিয়ম

প্রমাণ:

1. p ∣ a হলে কাজ শেষ। ধরি p ∤ a. — proof by cases
2. p-এর ধনাত্মক ভাজক শুধু 1 আর p, তাই gcd(p, a) হয় 1, নয় p. p ∤ a বলে gcd(p, a) ≠ p, তাই gcd(p, a) = 1. — মৌলিকের সংজ্ঞা
3. উপপাদ্য ৫.১-এ (a, b, c)-এর জায়গায় (p, a, b) বসালে p ∣ b. — উপপাদ্য ৫.১
4. n টি গুণকের জন্য n-এর ওপর induction: p ∣ (a₁⋯a_n−1) · a_n থেকে দুই-গুণকের রূপ দিয়ে p ∣ a₁⋯a_n−1 বা p ∣ a_n; প্রথম ক্ষেত্রে hypothesis. ∎ — mathematical induction (পর্ব ১০)

এই লেমার নাম Euclid-এর লেমা, কারণ প্রায় এই রূপে এটি Euclid-এর Elements-এর সপ্তম খণ্ডে আছে। মৌলিক শর্তটি বাদ দেওয়া যায় না: 6 ∣ 4 · 9 = 36, অথচ 6 ∤ 4 আর 6 ∤ 9. ৬ একটি যৌগিক সংখ্যা, আর তার দুটি গুণনীয়ক 2 আর 3 দুটি আলাদা গুণকে বসে আছে। কিছু বইয়ে এই ধর্মকেই মৌলিক সংখ্যার সংজ্ঞা হিসেবে নেওয়া হয় (বীজগণিতের “prime element”), আর “1 আর নিজে ছাড়া ভাজক নেই” ধর্মটিকে বলা হয় irreducible; পূর্ণসংখ্যায় দুটি এক, কিন্তু অন্য সংখ্যা-ব্যবস্থায় আলাদা হতে পারে (ভাবনার প্রশ্ন ৫)।

পরের অংশে আরেকটি ছোট ফল লাগবে, তাই এখনই প্রমাণ করে রাখি।

প্রমাণ: Bézout দিয়ে ax + by = d. দুই পাশকে d দিয়ে ভাগ করলে (a/d)x + (b/d)y = 1, যেখানে a/d আর b/d পূর্ণসংখ্যা। অনুসিদ্ধান্ত ৩.৩(খ) অনুযায়ী gcd(a/d, b/d) = 1. ∎

৬ · Linear Diophantine equation — ax + by = c-এর সব সমাধান

বাজারঘরে ডিম আসে দুই রকম বাক্সে: ৬টির আর ৯টির। একজন পাইকারি ক্রেতা ঠিক ৩৩টি ডিম চান, বাক্স না খুলে। কয়টি ৬-এর আর কয়টি ৯-এর বাক্স দেবেন? আর ৩২টি চাইলে? প্রশ্নটি হলো 6x + 9y = 33 সমীকরণের এমন সমাধান, যেখানে x আর y পূর্ণসংখ্যা। যে সমীকরণের শুধু পূর্ণসংখ্যা সমাধান খোঁজা হয়, তাকে Diophantine equation বলে, আলেকজান্দ্রিয়ার গণিতবিদ Diophantus-এর নামে (সাধারণত খ্রিস্টীয় তৃতীয় শতাব্দীর বলে ধরা হয়)। ax + by = c আকারেরটি linear Diophantine equation.

প্রমাণ:

1. (ক, ⇒) d ∣ a আর d ∣ b, তাই প্রতিটি x, y-তে d ∣ ax + by. সমাধান থাকলে ax + by = c, তাই d ∣ c. — বিভাজ্যতার নিয়ম
2. (ক, ⇐) c = dk ধরি। Bézout দিয়ে ax' + by' = d; k দিয়ে গুণ করলে a(kx') + b(ky') = c. — Bézout, constructive (§৪)
3. (খ) প্রথমে সূত্রের প্রতিটি জোড়া সমাধান: a(x₀ + bt/d) + b(y₀ − at/d) = ax₀ + by₀ + abt/d − abt/d = c. — সরাসরি বসানো
4. উল্টো দিকে (x, y) যেকোনো সমাধান হলে দুটি সমীকরণ বিয়োগ করে a(x − x₀) = b(y₀ − y), আর d দিয়ে ভাগ করে (a/d)(x − x₀) = (b/d)(y₀ − y). — বীজগণিত
5. তাই (b/d) ∣ (a/d)(x − x₀), আর লেমা ৫.৩ অনুযায়ী gcd(b/d, a/d) = 1. উপপাদ্য ৫.১ বলে (b/d) ∣ (x − x₀); লিখি x − x₀ = (b/d)t. — লেমা ৫.৩, উপপাদ্য ৫.১
6. ধাপ ৪-এ বসালে (a/d)(b/d)t = (b/d)(y₀ − y). b ≠ 0, তাই b/d দিয়ে ভাগ করা যায়: y = y₀ − (a/d)t. ∎ — শূন্য নয় এমন সংখ্যা দিয়ে ভাগ

ধাপ ৬-এ “b ≠ 0, তাই ভাগ করা যায়” লেখাটি অলংকার নয়: শূন্য দিয়ে নিঃশব্দে ভাগ করা ভুল প্রমাণের একটি পুরোনো উৎস। আর ধাপ ৫ দেখায় কেন পদক্ষেপ b/d, শুধু b নয়: x = x₀ + bt লিখলে অর্ধেক বা আরও বেশি সমাধান হারিয়ে যেত। ডিমের প্রশ্নে চলুন।

16x + 9y = 3329 = 1·6 + 3,  6 = 2·333 = 9 − 6 = 6·(−1) + 9·14×11: 6·(−11) + 9·11 = 335x = −11 + 3t,  y = 11 − 2t6t=4: (1, 3); t=5: (4, 1)

সমাধান-পদ্ধতিটি তাই একটি স্থির রেসিপি: (১) Euclid দিয়ে d, (২) d ∣ c কি না, (৩) extended Euclid দিয়ে ax' + by' = d, (৪) c/d দিয়ে গুণ, (৫) সাধারণ সমাধান, (৬) দরকার হলে t-এর ওপর অসমতা। নিচের ব্লক এই রেসিপিটি recursive extended Euclid দিয়ে লেখে, তারপর তিনটি সমীকরণ আর দুটি বাক্স-ব্যবস্থা পরীক্ষা করে।

def ext(a, b):                     # returns (d, x, y) with a*x + b*y = d
    if b == 0:
        return a, 1, 0
    d, x, y = ext(b, a % b)
    return d, y, x - (a // b) * y

def solve(a, b, c):                # x = x0 + (b/d)t, y = y0 - (a/d)t
    d, x, y = ext(a, b)
    if c % d != 0:
        return None
    return x * (c // d), y * (c // d), b // d, a // d

def nonneg(a, b, c):               # solutions with x >= 0 and y >= 0
    sol = solve(a, b, c)
    if sol is None:
        return None
    x0, y0, bx, ay = sol
    return [(x0 + bx * t, y0 - ay * t) for t in range(-c, c + 1)
            if x0 + bx * t >= 0 and y0 - ay * t >= 0]

print("6x + 9y = 33:  (x0, y0, b/d, a/d) =", solve(6, 9, 33))
print("   non-negative:", nonneg(6, 9, 33))
print("6x + 9y = 32: ", solve(6, 9, 32))
print("15x + 21y = 39:", solve(15, 21, 39), " non-negative:", nonneg(15, 21, 39))

def packable(n, a, b):
    return bool(nonneg(a, b, n))

bad = [n for n in range(1, 61) if not packable(n, 4, 9)]
print("boxes 4 and 9, impossible totals:", bad)
print("largest:", max(bad), "  ab-a-b =", 4 * 9 - 4 - 9, "  count:", len(bad))
print("boxes 6 and 9, impossible up to 30:",
      [n for n in range(1, 31) if not packable(n, 6, 9)])

6x + 9y = 33:  (x0, y0, b/d, a/d) = (-11, 11, 3, 2)
   non-negative: [(1, 3), (4, 1)]
6x + 9y = 32:  None
15x + 21y = 39: (39, -26, 7, 5)  non-negative: []
boxes 4 and 9, impossible totals: [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 19, 23]
largest: 23   ab-a-b = 23   count: 12
boxes 6 and 9, impossible up to 30: [1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29]

৭ · বাক্সে প্যাকিং — কোন সংখ্যা কখনো হয় না

আগের ব্লকের শেষ লাইন বলছে, ৬ আর ৯-এর বাক্সে ৩-এর গুণিতক ছাড়া কিছুই হয় না (তা উপপাদ্য ৬.১(ক) থেকেই জানা), আর ৩-এর গুণিতকের মধ্যে শুধু ৩ নিজে অসম্ভব। কারণ 6x + 9y = 3(2x + 3y), আর 2x + 3y অঋণাত্মক x, y-তে 1 ছাড়া প্রতিটি ধনাত্মক সংখ্যা হয় (2, 3, আর তারপর প্রতিবার একটি 2 যোগ করে)। পর্ব ১১-এ ৩ আর ৫ টাকার টিকিটে আমরা দেখেছি, coprime জোড়ায় একটি “সবচেয়ে বড় অসম্ভব সংখ্যা” থাকে, যাকে Frobenius number বলে, আর অনুমান করেছিলাম তা ab − a − b. ৪ আর ৯-এর বাক্সে ব্লকটি দেখাল 23 = 36 − 4 − 9, আর অসম্ভব সংখ্যা ১২টি = (4 − 1)(9 − 1)/2. এবার Bézout-এর সাধারণ সমাধান দিয়ে প্রথম দাবিটি প্রমাণ করা যাক।

প্রমাণ:

1. (ক) gcd = 1 ∣ n, তাই উপপাদ্য ৬.১ অনুযায়ী সমাধান আছে, আর সব সমাধানে x = x₀ + bt. t বদলে x-কে b-এর ধাপে সরানো যায়, তাই একটি সমাধান আছে যেখানে 0 ≤ x ≤ b − 1. — সাধারণ সমাধান, division algorithm
2. সেই সমাধানে by = n − ax ≥ n − a(b − 1) > (ab − a − b) − ab + a = −b, তাই y > −1, অর্থাৎ y ≥ 0. — অসমতা, y পূর্ণসংখ্যা
3. (খ) ধরি ax + by = ab − a − b, x, y ≥ 0. তাহলে a(x + 1) + b(y + 1) = ab. — proof by contradiction
4. b ∣ ab − b(y + 1) = a(x + 1), আর gcd(a, b) = 1, তাই b ∣ x + 1; x + 1 ≥ 1 বলে x + 1 ≥ b. একইভাবে y + 1 ≥ a. — উপপাদ্য ৫.১
5. তাহলে a(x + 1) + b(y + 1) ≥ ab + ab = 2ab > ab, বিরোধ। ∎

এই ফলটি সাধারণত James Joseph Sylvester-এর নামে যুক্ত (১৮৮০-এর দশকের একটি প্রশ্ন-সমাধান থেকে বলে উল্লেখিত); অসম্ভব সংখ্যার মোট সংখ্যা (a − 1)(b − 1)/2-এর প্রমাণ এখানে বাদ রাখলাম, ব্লকে শুধু একটি উদাহরণে মেলানো হলো। তিনটি বা তার বেশি বাক্সের মাপে Frobenius সংখ্যার কোনো সরল সূত্র জানা নেই, আর সাধারণ ক্ষেত্রে এটি বের করা গণনার দিক থেকে কঠিন সমস্যা বলে জানা যায়। বাজারঘরের জন্য ব্যবহারিক শিক্ষা: বাক্সের মাপ coprime রাখুন, তাহলে একটি সীমার পর যেকোনো অর্ডার না খুলে পাঠানো যায়।

৮ · Binary gcd — ভাগ ছাড়াই gcd

কম্পিউটারে বড় সংখ্যার ভাগ তুলনামূলক ব্যয়বহুল কাজ, অথচ ২ দিয়ে ভাগ শুধু bit সরানো (shift), আর বিয়োগ সস্তা। Josef Stein ১৯৬৭ সালে এমন একটি gcd পদ্ধতি প্রকাশ করেন যা শুধু এই সস্তা কাজগুলো ব্যবহার করে; একে binary gcd বা Stein-এর algorithm বলে (Knuth উল্লেখ করেছেন যে এর ধারণা প্রাচীন চীনা গণিতেও থাকতে পারে)। এটি তিনটি সহজ সত্যের ওপর দাঁড়িয়ে:

• a, b দুটিই জোড় হলে gcd(a, b) = 2 · gcd(a/2, b/2);
• a বিজোড় আর b জোড় হলে gcd(a, b) = gcd(a, b/2), কারণ 2 সাধারণ ভাজক হতে পারে না;
• a, b দুটিই বিজোড় আর a ≤ b হলে gcd(a, b) = gcd(a, b − a), আর b − a জোড় (লেমা ২.১-এর বিয়োগ-রূপ)।

বিজোড় − বিজোড় সবসময় জোড়, তাই প্রতিটি বিয়োগের পরেই অন্তত একটি ২ বাদ যায়, আর সংখ্যা দ্রুত ছোট হয়। নিচের ব্লক (252, 198)-এর ধাপগুলো ছাপে আর ১০,০০০টি এলোমেলো 64-bit জোড়ায় ফল math.gcd-এর সঙ্গে মেলায়।

from math import gcd
import random

def twos(n):                       # how many times 2 divides n (n > 0)
    return (n & -n).bit_length() - 1

def binary_gcd(a, b, trace=False):  # Stein: only shifts, comparisons, subtraction
    if a == 0 or b == 0:
        return a | b, 0
    k = min(twos(a), twos(b))      # common factor 2^k
    a, b = a >> twos(a), b >> twos(b)
    steps = 0
    while a != b:
        if trace:
            print(f"   ({a}, {b})")
        if a > b:
            a, b = b, a
        b = (b - a) >> twos(b - a)  # odd - odd is even: strip its 2s
        steps += 1
    return a << k, steps

print("binary gcd(252, 198), common 2^1 removed first:")
print("   gcd =", binary_gcd(252, 198, trace=True)[0])

random.seed(42)
ok, total = 0, 0
for _ in range(10000):
    a, b = random.getrandbits(64), random.getrandbits(64)
    g, steps = binary_gcd(a, b)
    ok += (g == gcd(a, b))
    total += steps
print("agrees with math.gcd:", ok, "of 10000;  average subtract steps:", round(total / 10000, 1))

binary gcd(252, 198), common 2^1 removed first:
   (63, 99)
   (63, 9)
   (9, 27)
   gcd = 18
agrees with math.gcd: 10000 of 10000;  average subtract steps: 43.7

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই বিষয়ের যে ধাঁচের অঙ্ক আসে, তার তিনটি পূর্ণ সমাধান। প্রতিটি সংখ্যা scratch-এ Python দিয়ে মেলানো।

অঙ্ক ১: gcd(391, 299), lcm(391, 299) আর Bézout-এর x, y বের করুন

1. Euclid: 391 = 1 · 299 + 92; 299 = 3 · 92 + 23; 92 = 4 · 23 + 0. তাই gcd = 23.
2. lcm: উপপাদ্য ১.২ থেকে lcm = 391 · 299 / 23 = 17 · 299 = 5083. (391 = 17 · 23, 299 = 13 · 23.)
3. পেছন থেকে প্রতিস্থাপন: 23 = 299 − 3 · 92 = 299 − 3(391 − 299) = 4 · 299 − 3 · 391. যাচাই: 1196 − 1173 = 23. তাই x = −3, y = 4.

অঙ্ক ২: 15x + 21y = 39-এর সব পূর্ণসংখ্যা সমাধান, আর অঋণাত্মক সমাধান কয়টি?

1. 21 = 1 · 15 + 6; 15 = 2 · 6 + 3; 6 = 2 · 3. d = 3, আর 3 ∣ 39, তাই সমাধান আছে।
2. 3 = 15 − 2 · 6 = 15 − 2(21 − 15) = 3 · 15 − 2 · 21. 39/3 = 13 দিয়ে গুণ: x₀ = 39, y₀ = −26.
3. b/d = 7, a/d = 5: x = 39 + 7t, y = −26 − 5t, t ∈ ℤ.
4. x ≥ 0 ⇔ t ≥ −39/7 ≈ −5.57, তাই t ≥ −5; y ≥ 0 ⇔ t ≤ −26/5 = −5.2, তাই t ≤ −6. দুটি একসঙ্গে অসম্ভব: অঋণাত্মক সমাধান ০টি। (t = −5-এ (4, −1), t = −6-এ (−3, 4): সীমার দুই পাশে।) §৬-এর ব্লকের চতুর্থ লাইনও তাই বলে।

অঙ্ক ৩: প্রমাণ করুন, প্রতিটি পূর্ণসংখ্যা n-এ gcd(2n + 1, 3n + 1) = 1

লেমা ২.১-এর প্রমাণে আসলে দেখানো হয়েছে, gcd(a, b) = gcd(b, a − qb) যেকোনো পূর্ণসংখ্যা q-তে (শুধু ভাগফলে নয়)। তাই gcd(3n + 1, 2n + 1) = gcd(2n + 1, n) = gcd(n, 1) = 1. Bézout দিয়ে সরাসরিও: 3(2n + 1) − 2(3n + 1) = 1, আর অনুসিদ্ধান্ত ৩.৩(খ) বলে gcd = 1. দ্বিতীয় পদ্ধতিটি পরীক্ষায় সবচেয়ে ছোট উত্তর: সহগগুলো খুঁজে বের করুন যাতে n কেটে যায়। n = 1 থেকে 9999 পর্যন্ত scratch-এ যাচাই করা হয়েছে, কিন্তু প্রমাণ সব n-এর জন্য।

প্রমাণের ভুল ধরুন: Euclid-এর লেমার একটি “সহজ” প্রমাণ

একজন লিখলেন: “দাবি: p মৌলিক, p ∣ ab হলে p ∣ a বা p ∣ b. প্রমাণ: a আর b-কে মৌলিক গুণনীয়কে ভাঙি। তাহলে ab-এর ভাঙন হলো দুটি ভাঙন পাশাপাশি রাখা। p ∣ ab, তাই p, ab-এর ভাঙনে আছে, কারণ ভাঙন অনন্য। তাই p হয় a-এর ভাঙনে আছে, নয় b-এর, অর্থাৎ p ∣ a বা p ∣ b. ∎” এরপর তিনি এই লেমা দিয়ে factorization-এর অনন্যতা প্রমাণ করলেন। পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: প্রমাণের প্রতিটি বাক্য সত্য, কিন্তু “ভাঙন অনন্য” ধাপটি সেই উপপাদ্যই ব্যবহার করছে, যা পরে এই লেমা দিয়ে প্রমাণ করা হবে। এটি circular reasoning বা চক্রাকার যুক্তি, যাকে পর্ব ০৮-এ begging the question নামে দেখেছেন। অনন্যতা আগে থেকে জানা থাকলে প্রমাণটি ঠিক আছে; কিন্তু অনন্যতার প্রমাণে এটি ব্যবহার করা যায় না। সঠিক পথ ছবি ৫.১-এর শিকল: Bézout থেকে Euclid-এর লেমা, factorization ছাড়াই। শিক্ষা: একটি প্রমাণ পড়ার সময় প্রতিটি ব্যবহৃত ফলের জন্য জিজ্ঞেস করুন, “এটি কোথায়, কী দিয়ে প্রমাণিত?”

১০ · AI-এর যুগে — gcd-এর হিসাব আর প্রমাণ যাচাই

AI সহকারী gcd আর extended Euclid-এর উত্তর খুব আত্মবিশ্বাসের সঙ্গে দেয়। ছোট সংখ্যায় সাধারণত ঠিক থাকে, কিন্তু বড় সংখ্যায়, ঋণাত্মক চিহ্নে আর প্রমাণে কিছু ভুল নিয়মিত দেখা যায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• দাবি করা gcd দুটি সংখ্যাকেই ভাগ করে কি না নিজে দেখেছি
• Bézout-এর x, y বসিয়ে ax + by হিসাব করেছি, আর তা gcd-এর সমান
• সাধারণ সমাধানে পদক্ষেপ b/d আর a/d, চিহ্ন বিপরীত; দুটি t-তে যাচাই করেছি
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত (মৌলিক, coprime, অশূন্য) মিলিয়েছি
• প্রমাণে কোনো ফল নিজেকে প্রমাণ করতে নিজেকেই ব্যবহার করেনি
• ছোট পরিসরে brute force দিয়ে উত্তর মিলিয়েছি, আর ইতিহাসের সাল ও নাম বিশ্বস্ত পাঠ্যবইয়ে দেখেছি

সবচেয়ে সস্তা প্রথম পরীক্ষা: AI যে x, y দিল, সেগুলো দিয়ে ax + by হিসাব করুন। এক লাইনের এই যাচাই প্রায় সব হিসাবের ভুল ধরে ফেলে।