Linear congruence আর Chinese Remainder Theorem

১ · Modulo-র জগতে ভাগ — modular inverse

বাজারঘরের এক কর্মী একটি হিসাব মেলাচ্ছেন। প্রতিটি অর্ডারের id-কে 17 দিয়ে গুণ করে 3120 দিয়ে ভাগ করলে যে ভাগশেষ থাকে, সেটি invoice-এ ছাপা হয়। একটি invoice-এ ছাপা আছে 9. মূল id-এর ভাগশেষ কত ছিল? সাধারণ পাটিগণিতে আমরা লিখতাম 17x = 9, তাই x = 9/17. কিন্তু এখানে আমরা পূর্ণসংখ্যার জগতে, modulo 3120-এ; 9/17 কোনো পূর্ণসংখ্যা নয়। তাহলে “17 দিয়ে ভাগ” বলতে কী বোঝাবে?

পর্ব ২২ “Modular arithmetic — ঘড়ির গণিত আর modular exponentiation”-এ দেখেছেন, mod m-এ যোগ, বিয়োগ আর গুণ নির্ভয়ে করা যায়। ভাগ আলাদা। সাধারণ সংখ্যায় 17 দিয়ে ভাগ মানে 1/17 দিয়ে গুণ, আর 1/17 হলো সেই সংখ্যা, যাকে 17 দিয়ে গুণ করলে 1 হয়। Modulo-র জগতে একই প্রশ্ন করা যায়: এমন কোনো পূর্ণসংখ্যা s আছে কি, যাতে 17s-এর ভাগশেষ 1? থাকলে 17x ≡ 9-এর দুই পাশকে s দিয়ে গুণ করলেই x বেরিয়ে আসবে।

প্রথমে চিহ্নগুলো মনে করিয়ে দিই। m ≥ 1 একটি পূর্ণসংখ্যা হলে a ≡ b (mod m) পড়া হয় “a congruent b modulo m”, আর এর অর্থ m ∣ (a − b), অর্থাৎ m দিয়ে ভাগ করলে a আর b-এর ভাগশেষ সমান। এই সম্পর্কটির নাম congruence; m-কে বলে modulus. “∣” চিহ্নের অর্থ “নিঃশেষে ভাগ করে” (divisibility). আর gcd(a, m) হলো a আর m-এর গরিষ্ঠ সাধারণ গুণনীয়ক (gcd); gcd(a, m) = 1 হলে a আর m সহমৌলিক (coprime).

সব সংখ্যার inverse থাকে না। mod 6-এ 2-কে নিন: 2 · 0, 2 · 1, …, 2 · 5-এর ভাগশেষ 0, 2, 4, 0, 2, 4. কখনো 1 আসে না, কারণ 2s সবসময় জোড় আর 6-এর গুণিতকও জোড়, তাই 2s − 1 (বিজোড়) কখনো 6-এর গুণিতক হতে পারে না। সমস্যাটি 2 আর 6-এর সাধারণ গুণনীয়ক 2. এই পর্যবেক্ষণই পুরো উত্তর।

প্রমাণ: এখানে Bézout-এর অভেদ লাগবে: যেকোনো পূর্ণসংখ্যা a, m (দুটিই শূন্য নয়) হলে এমন পূর্ণসংখ্যা s, t আছে যাতে as + mt = gcd(a, m). এর প্রমাণ (well-ordering দিয়ে) পর্ব ২১ “GCD আর Euclid-এর algorithm — Bézout আর extended Euclid”-এ।

1. (⇐) ধরি gcd(a, m) = 1. Bézout অনুযায়ী as + mt = 1 এমন s, t আছে। তাহলে as − 1 = −mt, যা m-এর গুণিতক, তাই as ≡ 1 (mod m). — Bézout, congruence-এর সংজ্ঞা
2. (⇒) ধরি as ≡ 1 (mod m). তাহলে কোনো পূর্ণসংখ্যা k-এর জন্য as − 1 = mk, অর্থাৎ as − mk = 1. — congruence-এর সংজ্ঞা
3. d = gcd(a, m) হলে d ∣ a আর d ∣ m, তাই d ∣ (as − mk) = 1. ধনাত্মক d-এর জন্য এর অর্থ d = 1. — ভাজক দুটি সংখ্যাকে ভাগ করলে তাদের যেকোনো পূর্ণসংখ্যা-সমন্বয়কেও ভাগ করে
4. (অনন্যতা) as ≡ 1 আর as′ ≡ 1 হলে s ≡ s · 1 ≡ s(as′) = (sa)s′ ≡ 1 · s′ = s′ (mod m). ∎ — congruence গুণ মানে (পর্ব ২২), আর পূর্ণসংখ্যার গুণ associative ও commutative

উপপাদ্যটির দুটি তাৎক্ষণিক ফল মনে রাখার মতো। প্রথমত, p মৌলিক (prime) হলে 1, 2, …, p − 1 প্রত্যেকটি p-এর সঙ্গে সহমৌলিক, তাই mod p-এ প্রতিটি অশূন্য ভাগশেষের inverse আছে: মৌলিক modulus-এ ভাগ সবসময় চলে। দ্বিতীয়ত, gcd(a, m) > 1 হলে কোনো চালাকিতেই inverse পাওয়া যাবে না; mod 26-এ 13-এর inverse খোঁজা সময় নষ্ট। প্রথম ফলটির ওপর ভর করে পর্ব ৩০ “Finite field আর elliptic curve-এর পরিচয়”-এ ℤ_p-কে একটি field হিসেবে দেখা হবে।

২ · Inverse হাতে বের করা — extended Euclid-এর ছক

উপপাদ্য ১.২-এর প্রমাণটি গঠনমূলক: Bézout-এর s-ই inverse. সেই s বের করে extended Euclidean algorithm. সাধারণ Euclid-এর algorithm gcd(a, b) = gcd(b, a mod b) বারবার লাগিয়ে gcd দেয়; এর সঠিকতা আর সময় (Lamé-এর সীমা) পর্ব ১৩ “Program-এর সঠিকতা — loop invariant আর Hoare logic-এর ধারণা”-এ প্রমাণ করা হয়েছে। Extended সংস্করণ প্রতিটি ভাগশেষের পাশে একটি সহগ t রাখে, যাতে একটি loop invariant সবসময় সত্য থাকে:

প্রতিটি সারিতে: r ≡ t · a (mod m)

শুরুর দুটি সারি r = m, t = 0 (কারণ m ≡ 0 · a) আর r = a, t = 1. তারপর প্রতিটি নতুন সারি আগের দুটি থেকে আসে: q = আগের r ÷ এখনকার r-এর ভাগফল, নতুন r = আগের r − q · এখনকার r, আর নতুন t = আগের t − q · এখনকার t. দুটি সারিতে invariant সত্য হলে এই রৈখিক সমন্বয়েও সত্য থাকে। r যখন 1 হয়, তখন 1 ≡ t · a, অর্থাৎ t-ই inverse. r = 1-এ না পৌঁছে যদি 0-তে পৌঁছায়, তবে শেষ অশূন্য r = gcd > 1, আর inverse নেই। এখন শুরুর প্রশ্নের 17-এর inverse mod 3120 ছকে বের করা যাক।

1   r      q      t23120      —      03  17      —      14   9    183   −1835   8      1    1846   1      1   −36772753 = −367 + 3120

এবার শুরুর invoice-এর প্রশ্ন: 17x ≡ 9 (mod 3120)-এর দুই পাশকে 2753 দিয়ে গুণ করলে x ≡ 9 · 2753 = 24777 ≡ 2937 (mod 3120). যাচাই: 17 · 2937 = 49929 = 16 · 3120 + 9. লক্ষ করুন, গুণের ধাপটি উল্টানোও যায় (17 দিয়ে গুণ করলে আগের সমীকরণ ফেরে), তাই নতুন সমীকরণটি মূলটির সমতুল্য, শুধু একটি পরিণতি নয়।

Python-এ এই সবকিছু এক লাইনে হয়: Python 3.8 থেকে pow(a, -1, m) inverse দেয়, আর inverse না থাকলে ValueError তোলে। Python-এর int-এর আকারের কোনো নির্দিষ্ট সীমা নেই (Python প্রোগ্রামিং কোর্সের পর্ব ০৭), তাই কয়েকশো অঙ্কের modulus-এও এটি কাজ করে। নিচের ব্লক extended Euclid শূন্য থেকে লেখে (recursive রূপে), স্টেপারের ফল মেলায়, তারপর mod 26-এর পুরো inverse-তালিকা ছাপে। mod 26 বেছে নেওয়ার কারণ: ইংরেজি বর্ণমালার ২৬টি অক্ষর, আর পর্ব ২৭ “Classical cipher — shift, affine আর frequency analysis”-এর affine cipher-এ ঠিক এই তালিকাটিই লাগবে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from math import gcd

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

def inverse(a, m):
    g, x, _ = ext_gcd(a % m, m)
    if g != 1:
        return None                # no inverse because gcd(a, m) > 1
    return x % m

print("ext_gcd(17, 3120) =", ext_gcd(17, 3120))
print("inverse(17, 3120) =", inverse(17, 3120), "  pow:", pow(17, -1, 3120))
print("check: 17 * 2753 % 3120 =", 17 * 2753 % 3120)

m = 26
units = [a for a in range(1, m) if gcd(a, m) == 1]
print(f"mod {m}: {len(units)} of {m - 1} values have an inverse")
pairs = [f"{a}->{inverse(a, m)}" for a in units]
for i in range(0, len(pairs), 4):
    print("   ".join(pairs[i:i + 4]))
print("self-inverse:", [a for a in units if inverse(a, m) == a])
print("13 * x mod 26 takes only:", sorted({13 * x % m for x in range(m)}))
try:
    pow(13, -1, 26)
except ValueError as e:
    print("pow(13, -1, 26) -> ValueError:", e)

ext_gcd(17, 3120) = (1, -367, 2)
inverse(17, 3120) = 2753   pow: 2753
check: 17 * 2753 % 3120 = 1
mod 26: 12 of 25 values have an inverse
1->1   3->9   5->21   7->15
9->3   11->19   15->7   17->23
19->11   21->5   23->17   25->25
self-inverse: [1, 25]
13 * x mod 26 takes only: [0, 13]
pow(13, -1, 26) -> ValueError: base is not invertible for the given modulus

৩ · Linear congruence ax ≡ b (mod m) — কখন সমাধান, আর কয়টি

a, b পূর্ণসংখ্যা আর m ≥ 1 হলে ax ≡ b (mod m) আকারের সমীকরণকে linear congruence বলে; অজানা x-এর ঘাত 1, তাই “linear”. gcd(a, m) = 1 হলে কাজ সহজ: দুই পাশকে a⁻¹ দিয়ে গুণ করলে x ≡ a⁻¹b, mod m-এ ঠিক একটি সমাধান। কিন্তু gcd(a, m) > 1 হলে কী? mod 21-এ 9x ≡ 12 নিন। 9-এর inverse নেই (gcd(9, 21) = 3), তবু x = 6 কাজ করে: 9 · 6 = 54 = 2 · 21 + 12. আবার 8x ≡ 5 (mod 12)-এর কোনো সমাধানই নেই, কারণ 8x − 5 সবসময় বিজোড়, আর 12-এর গুণিতক জোড়। এই দুই আচরণের পেছনে একটিই নিয়ম।

প্রমাণ:

1. (প্রয়োজনীয়তা) x একটি সমাধান হলে ax − b = mq কোনো q-এর জন্য, তাই b = ax − mq. d ∣ a আর d ∣ m, তাই d ∣ b. — congruence-এর সংজ্ঞা, ভাজকের রৈখিক সমন্বয়
2. (যথেষ্টতা) এখন ধরি d ∣ b. লিখি a = da′, m = dm′, b = db′. Bézout থেকে as + mt = d, d দিয়ে ভাগ করে a′s + m′t = 1; তাই gcd(a′, m′) = 1 (উপপাদ্য ১.২-এর ধাপ ৩-এর যুক্তি)। — Bézout
3. m ∣ (ax − b) ⇔ dm′ ∣ d(a′x − b′) ⇔ m′ ∣ (a′x − b′). অর্থাৎ ax ≡ b (mod m) ⇔ a′x ≡ b′ (mod m′). — দুই পাশ থেকে ধনাত্মক d বাদ দেওয়া যায়
4. gcd(a′, m′) = 1, তাই উপপাদ্য ১.২ অনুযায়ী a′-এর inverse u আছে (m′ = 1 হলে সব x-ই সমাধান, x₀ = 0). a′x ≡ b′ (mod m′) ⇔ x ≡ ub′ (mod m′), কারণ u দিয়ে গুণ আর a′ দিয়ে গুণ একে অপরকে উল্টায়। x₀ = ub′ mod m′. — উপপাদ্য ১.২
5. তাই সমাধানগুলো ঠিক সেই x, যেখানে x ≡ x₀ (mod m′). 0 থেকে m − 1-এর মধ্যে এরা x₀ + km′, k = 0, 1, …, d − 1, কারণ m = dm′. এরা mod m-এ আলাদা, কারণ যেকোনো দুটির পার্থক্য অশূন্য আর পরম মানে m-এর চেয়ে ছোট। মোট d-টি। ∎ — গণনা

19x ≡ 12 (mod 21)2d = gcd(9, 21) = 3, 3 ∣ 1233x ≡ 4 (mod 7)43 · 5 = 15 ≡ 1 (mod 7)5x ≡ 4 · 5 = 20 ≡ 6 (mod 7)6x ∈ {6, 13, 20} (mod 21)

উপপাদ্য ৩.১-এর একটি পার্শ্বফল প্রতিদিনের হিসাবে খুব কাজে লাগে: কাটাকাটির নিয়ম। ca ≡ cb (mod m) হলে a ≡ b (mod m/gcd(c, m)). বিশেষ করে gcd(c, m) = 1 হলে c নির্ভয়ে কাটা যায়, কিন্তু অন্যথায় modulus-ও ছোট হয়ে যায়। উদাহরণ: 2 · 1 ≡ 2 · 4 (mod 6), কারণ 2 আর 8-এর পার্থক্য 6; কিন্তু 1 ≢ 4 (mod 6). সঠিক উপসংহার 1 ≡ 4 (mod 3). প্রমাণ উপপাদ্যের ধাপ ৩ আর ৪-এর মতোই; অনুশীলন ১-এ নিজে লিখে দেখুন।

৪ · Chinese Remainder Theorem — একসঙ্গে কয়েকটি ভাগশেষ

প্রাচীন চীনা গণিত-গ্রন্থ Sunzi Suanjing (“সুনজির গণিত-গ্রন্থ”, সাধারণত খ্রিস্টীয় তৃতীয় থেকে পঞ্চম শতাব্দীর মধ্যে রচিত বলে ধরা হয়; সঠিক সাল অনিশ্চিত) একটি ধাঁধা দেয়, মোটামুটি এমন: “কিছু জিনিস আছে, সংখ্যা জানা নেই। তিনটি করে গুনলে দুটি বাকি থাকে, পাঁচটি করে গুনলে তিনটি, সাতটি করে গুনলে দুটি। জিনিস কয়টি?” আধুনিক ভাষায়:

x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

গ্রন্থের উত্তর 23. প্রশ্নটির বাজারঘর-সংস্করণ সহজেই বানানো যায়: গুদামে কতগুলো প্যাকেট আছে কেউ জানে না, কিন্তু ৩টির বাক্সে ভরলে ২টি, ৫টির বাক্সে ভরলে ৩টি, ৭টির বাক্সে ভরলে ২টি বেঁচে যায়। কয়েকটি ছোট modulus-এর ভাগশেষ জানলে একটি বড় modulus-এর ভাগশেষ কি পুরোপুরি জানা যায়? উত্তর দেয় এই পর্বের কেন্দ্রীয় উপপাদ্য। এখানে m₁, …, m_k-কে জোড়ায় জোড়ায় সহমৌলিক বলা হয়, যদি i ≠ j হলে gcd(m_i, m_j) = 1. যেমন 3, 5, 7 জোড়ায় জোড়ায় সহমৌলিক, কিন্তু 4, 6, 7 নয় (gcd(4, 6) = 2), যদিও তিনটির একসঙ্গে gcd 1.

এটি একটি existence আর uniqueness উপপাদ্য, পর্ব ০৯ “প্রমাণের কৌশল — case, existence, uniqueness আর counterexample”-এর ধাঁচে, তাই প্রমাণেও দুটি অংশ। অস্তিত্বের প্রমাণটি গঠনমূলক: শুধু “আছে” বলে না, সূত্র দিয়ে বানিয়ে দেখায়। নামটি এই Chinese Remainder Theorem (CRT) সংক্ষেপেও বহুল প্রচলিত।

প্রমাণ (অস্তিত্ব): প্রতিটি i-এর জন্য M_i = M/m_i লিখি, অর্থাৎ m_i ছাড়া বাকি সব modulus-এর গুণফল।

1. gcd(M_i, m_i) = 1. কারণ, কোনো মৌলিক p যদি m_i আর M_i দুটিকেই ভাগ করে, তবে p গুণফল M_i-এর কোনো একটি উৎপাদক m_j (j ≠ i)-কে ভাগ করে, আর তখন gcd(m_i, m_j) ≥ p > 1, যা অনুমানের বিরোধী। — Euclid-এর lemma (p ∣ ab ⇒ p ∣ a বা p ∣ b), পর্ব ২১
2. উপপাদ্য ১.২ অনুযায়ী y_i = M_i⁻¹ mod m_i আছে: M_iy_i ≡ 1 (mod m_i). — উপপাদ্য ১.২
3. x = r₁M₁y₁ + r₂M₂y₂ + ⋯ + r_kM_ky_k নিই। একটি নির্দিষ্ট j ধরুন। i ≠ j হলে m_j হলো M_i-এর একটি উৎপাদক, তাই সেই পদ ≡ 0 (mod m_j). — M_i-এর সংজ্ঞা
4. বাকি থাকে j-তম পদ: x ≡ r_jM_jy_j ≡ r_j · 1 = r_j (mod m_j). প্রতিটি j-এর জন্য এটি সত্য, তাই x একটি সমাধান। — ধাপ ২, congruence গুণ আর যোগ মানে

প্রমাণ (অনন্যতা):

1. x আর x′ দুটিই সমাধান হলে প্রতিটি i-তে x ≡ r_i ≡ x′, তাই m_i ∣ (x − x′). — congruence-এর transitivity
2. সহায়ক দাবি: u ∣ n, v ∣ n আর gcd(u, v) = 1 হলে uv ∣ n. কারণ n = uw; v ∣ uw আর gcd(u, v) = 1, তাই Bézout-এর us + vt = 1-কে w দিয়ে গুণ করে w = uws + vwt, যার দুটি পদই v দিয়ে বিভাজ্য, তাই v ∣ w, আর uv ∣ uw = n. — Bézout
3. m₁ ∣ (x − x′) আর m₂ ∣ (x − x′) থেকে m₁m₂ ∣ (x − x′). তারপর gcd(m₁m₂, m₃) = 1 (অস্তিত্বের ধাপ ১-এর যুক্তি), তাই m₁m₂m₃ ∣ (x − x′). এভাবে k পর্যন্ত (k-এর ওপর induction, পর্ব ১০) M ∣ (x − x′). — সহায়ক দাবি, induction
4. উল্টোভাবে, x সমাধান হলে x + tM-ও সমাধান, কারণ প্রতিটি m_i ∣ M. তাই সমাধানের সেট ঠিক একটি congruence class mod M. ∎

1x ≡ 2 (3), 3 (5), 2 (7)2M = 3·5·7 = 1053i=1: m=3, M₁=35, y₁=?4i=2: m=5, M₂=21, y₂=?5i=3: m=7, M₃=15, y₃=?6x = Σ rᵢ·Mᵢ·yᵢ7x mod 105

CRT-কে একটি ফাংশন হিসেবেও দেখা যায়। f(x) = (x mod m₁, …, x mod m_k) নিয়মে {0, 1, …, M − 1} থেকে সব সম্ভাব্য ভাগশেষ-তালিকার সেটে একটি ফাংশন পাই। অনন্যতা বলে f one-to-one; দুই সেটেরই ঠিক M-টি উপাদান, তাই সসীম সেটের নিয়মে f onto-ও, অর্থাৎ একটি bijection, যার সংজ্ঞা পর্ব ১৬ “ফাংশন — one-to-one, onto, inverse আর composition”-এ দেখেছেন। এটি অস্তিত্বের একটি দ্বিতীয়, অগঠনমূলক প্রমাণ: শুধু গুনেই জানা যায় যে প্রতিটি তালিকার জন্য একটি x আছে, যদিও x-টি কী, তা বলে না। নিচের ছবি M = 15-এ এই bijection দেখায়, আর পাশে দেখায় modulus সহমৌলিক না হলে কী ভাঙে।

৫ · Back-substitution, আর modulus সহমৌলিক না হলে

সূত্র-পদ্ধতি সুন্দর, কিন্তু হাতে কষার সময় প্রায়ই আরেকটি পদ্ধতি সহজ: back-substitution, একবারে একটি congruence. প্রথমটি থেকে x-এর সাধারণ রূপ লিখি, পরেরটিতে বসাই, নতুন অজানার জন্য একটি linear congruence সমাধান করি, আবার সাধারণ রূপ লিখি। সুনজির ধাঁধায়:

1. x ≡ 2 (mod 3) ⇒ x = 2 + 3k, যেকোনো পূর্ণসংখ্যা k.
2. দ্বিতীয়টিতে বসাই: 2 + 3k ≡ 3 (mod 5) ⇒ 3k ≡ 1 (mod 5). 3 · 2 = 6 ≡ 1, তাই k ≡ 2 (mod 5), k = 2 + 5j, আর x = 2 + 3(2 + 5j) = 8 + 15j.
3. তৃতীয়টিতে বসাই: 8 + 15j ≡ 2 (mod 7). 8 ≡ 1 আর 15 ≡ 1, তাই 1 + j ≡ 2, j ≡ 1 (mod 7). তাই x = 8 + 15 = 23, আর সাধারণ সমাধান x = 23 + 105t.

প্রতিটি ধাপ উপপাদ্য ৩.১-এর একটি linear congruence. এই পদ্ধতির বড় সুবিধা হলো এটি modulus সহমৌলিক না হলেও চলে, আর না চললে ঠিক কোথায় আটকায় তা দেখিয়ে দেয়। ধরুন x ≡ 1 (mod 4) আর x ≡ 2 (mod 6). x = 1 + 4k বসালে 4k ≡ 1 (mod 6). gcd(4, 6) = 2 আর 2 ∤ 1, তাই উপপাদ্য ৩.১ বলে সমাধান নেই। কারণটা সহজ: প্রথম শর্তে x বিজোড়, দ্বিতীয় শর্তে x জোড়। §৪-এর ছবির নিচের ছকে (সারি 1, কলাম 2) ঘরটি খালি। সাধারণ নিয়মটি:

প্রমাণ:

1. (প্রয়োজনীয়তা) সমাধান x হলে x = r₁ + m₁s = r₂ + m₂t কোনো s, t-এর জন্য, তাই r₁ − r₂ = m₂t − m₁s, যা d দিয়ে বিভাজ্য। — ভাজকের রৈখিক সমন্বয়
2. (যথেষ্টতা) x = r₁ + m₁k দ্বিতীয় শর্ত মানে ⇔ m₁k ≡ r₂ − r₁ (mod m₂). এর সহগ m₁ আর modulus m₂-এর gcd হলো d, আর d ∣ (r₂ − r₁), তাই উপপাদ্য ৩.১ অনুযায়ী এমন k আছে। — উপপাদ্য ৩.১
3. (অনন্যতা) x, x′ দুটিই সমাধান হলে m₁ আর m₂ দুটিই x − x′-কে ভাগ করে, অর্থাৎ x − x′ একটি সাধারণ গুণিতক, আর প্রতিটি সাধারণ গুণিতক lcm দিয়ে বিভাজ্য। তাই x ≡ x′ (mod L). উল্টোভাবে x + tL-ও সমাধান। ∎ — lcm-এর ধর্ম (পর্ব ২১)

দুইয়ের বেশি congruence থাকলে প্রতিটি জোড়ার জন্য gcd(m_i, m_j) ∣ (r_i − r_j) শর্তটি প্রয়োজনীয় (ধাপ ১ প্রতিটি জোড়ায় খাটে), আর জানা ফল হলো এটি যথেষ্টও; back-substitution-এ উপপাদ্য ৫.১ বারবার লাগিয়ে induction দিয়ে প্রমাণ করা যায়, আর তখন সমাধান সব modulus-এর lcm-এর modulo-তে অনন্য। লক্ষ করুন, d = 1 হলে উপপাদ্য ৫.১ ঠিক দুই modulus-এর CRT. নিচের ব্লক উপপাদ্য ৩.১ আর ৫.১-কে সরাসরি কোডে রূপ দেয়: solve_linear সব সমাধানের তালিকা দেয়, crt2 দুটি congruence জোড়ে (না জোড়া গেলে None), আর crt_all back-substitution চালায়। প্রতিটি উত্তর মূল শর্তে বসিয়ে যাচাই করা হয়।

from math import gcd

def solve_linear(a, b, m):        # every x in 0..m-1 with a*x ≡ b (mod m)
    d = gcd(a, m)
    if b % d:
        return []
    a1, b1, m1 = a // d, b // d, m // d
    x0 = b1 * pow(a1, -1, m1) % m1 if m1 > 1 else 0
    return [x0 + k * m1 for k in range(d)]

def crt2(r1, m1, r2, m2):         # x ≡ r1 (mod m1) and x ≡ r2 (mod m2)
    d = gcd(m1, m2)
    if (r2 - r1) % d:
        return None               # inconsistent system
    k = solve_linear(m1, r2 - r1, m2)[0]
    L = m1 // d * m2              # lcm(m1, m2)
    return (r1 + m1 * k) % L, L

def crt_all(system):              # back-substitution, one congruence at a time
    x, M = 0, 1
    for r, m in system:
        res = crt2(x, M, r, m)
        if res is None:
            return None
        x, M = res
    return x, M

for a, b, m in [(9, 12, 21), (14, 30, 100), (8, 5, 12), (17, 9, 3120)]:
    sols = solve_linear(a, b, m)
    print(f"{a}x ≡ {b} (mod {m}): {sols}  check", all((a * x - b) % m == 0 for x in sols))

for system in [[(2, 3), (3, 5), (2, 7)], [(3, 6), (5, 8)], [(1, 4), (2, 6)], [(5, 8), (1, 12), (9, 18)]]:
    res = crt_all(system)
    ok = res is None or all(res[0] % m == r for r, m in system)
    print(system, "->", res, " check", ok)

9x ≡ 12 (mod 21): [6, 13, 20]  check True
14x ≡ 30 (mod 100): [45, 95]  check True
8x ≡ 5 (mod 12): []  check True
17x ≡ 9 (mod 3120): [2937]  check True
[(2, 3), (3, 5), (2, 7)] -> (23, 105)  check True
[(3, 6), (5, 8)] -> (21, 24)  check True
[(1, 4), (2, 6)] -> None  check True
[(5, 8), (1, 12), (9, 18)] -> None  check True

৬ · প্রয়োগ — ডেলিভারির সময়সূচি, residue number system আর RSA

সময়সূচি। বাজারঘরের তিনটি ভ্যান তিন জেলায় যায়: সিলেটে প্রতি ৩ দিনে, খুলনায় প্রতি ৫ দিনে, রাজশাহীতে প্রতি ৭ দিনে। মাসের হিসাব বাদ দিয়ে দিনগুলো 0, 1, 2, … গুনলে সিলেটের ভ্যান গেছে দিন 1-এ, খুলনার দিন 2-এ, রাজশাহীর দিন 3-এ। তিনটি ভ্যান একই দিনে বের হলে একজন তদারককারীই যথেষ্ট; সেই দিন কবে? শর্ত x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7), আর CRT বলে উত্তর mod 105-এ ঠিক একটি: দিন 52, তারপর প্রতি ১০৫ দিনে। যাচাই: 52 = 17 · 3 + 1 = 10 · 5 + 2 = 7 · 7 + 3. এখন ধরুন রাজশাহীর ভ্যান প্রতি ৬ দিনে যায় আর শেষবার গেছে দিন 3-এ। সিলেট (x ≡ 1 mod 3) আর রাজশাহী (x ≡ 3 mod 6) কখনো এক দিনে পড়বে না: দ্বিতীয় শর্তে x তিনের গুণিতক, প্রথম শর্তে নয়; উপপাদ্য ৫.১-এর ভাষায় gcd(3, 6) = 3 ∤ 1 − 3. পরিকল্পনাকারীর জন্য শিক্ষা: পর্যায়গুলো সহমৌলিক হলে সব সমন্বয় একসময় আসে; না হলে কিছু সমন্বয় কখনোই আসে না।

Residue number system. CRT বলে, জোড়ায় জোড়ায় সহমৌলিক modulus m₁, …, m_k নিলে 0 থেকে M − 1-এর প্রতিটি সংখ্যা তার ভাগশেষ-তালিকা দিয়ে পুরোপুরি চেনা যায়। আর যোগ, বিয়োগ, গুণ ভাগশেষে ভাগশেষে আলাদাভাবে করা যায়, কারণ congruence এই অপারেশনগুলো মানে। এভাবে সংখ্যা রাখার পদ্ধতির নাম residue number system (RNS). সুবিধা: প্রতিটি ভাগশেষ ছোট, আর এক ভাগশেষের হিসাব অন্যটির ওপর নির্ভর করে না, তাই সাধারণ যোগের মতো “হাতে রাখা” (carry) এক ঘর থেকে আরেক ঘরে যায় না; সবগুলো একসঙ্গে সমান্তরালে চলতে পারে। অসুবিধা: দুটি সংখ্যার কোনটি বড়, ভাগ, বা ফল M ছাড়িয়েছে কি না, এগুলো ভাগশেষ দেখে সহজে বলা যায় না; তখন CRT দিয়ে পুরো সংখ্যায় ফিরতে হয়। তাই RNS সাধারণ কম্পিউটারের মূল পাটিগণিত নয়, তবে কিছু বিশেষ ক্ষেত্রে (signal processing-এর hardware, বড় সংখ্যার cryptography) এর ব্যবহার নিয়ে গবেষণা আর প্রয়োগ আছে বলে জানা যায়।

RSA দ্রুত করা। পর্ব ২৮ “RSA-এর গণিত — key, encryption আর কেন কাজ করে”-এ দেখবেন, RSA-র decryption-এ একটি বিশাল ঘাত c^d mod n নিতে হয়, যেখানে n = pq দুটি বড় মৌলিকের গুণফল। গোপন key-এর মালিক p আর q জানেন, তাই তিনি হিসাবটি mod p আর mod q-এ আলাদা করে (প্রতিটি অর্ধেক মাপের সংখ্যায়) করে CRT দিয়ে জুড়তে পারেন। এতে decryption কয়েক গুণ দ্রুত হয়; সাধারণত প্রায় চার গুণের কথা বলা হয়, যদিও সঠিক লাভ বাস্তবায়নের ওপর নির্ভর করে। মনে রাখবেন, ছোট সংখ্যার “textbook RSA” শুধু বোঝার জন্য; বাস্তবে padding, বড় key আর পরীক্ষিত লাইব্রেরি লাগে (সাইবার সিকিউরিটি কোর্সের পর্ব ১০)।

নিচের ব্লক তিনটি জিনিস দেখায়। প্রথমত, প্রমাণের সূত্র (crt_coprime) আর brute force, অর্থাৎ 0, 1, 2, … একে একে চেষ্টা, পাশাপাশি। প্রতিটি পরীক্ষায় ভাগশেষ হিসেবে m − 2 নেওয়া হয়েছে, যাতে উত্তর M − 2 হয়, brute force-এর জন্য প্রায় সবচেয়ে খারাপ ক্ষেত্র। দ্বিতীয়ত, ফলটি SymPy লাইব্রেরির crt-এর সঙ্গে মেলানো (প্রথমবার SymPy নামতে কয়েক সেকেন্ড বেশি লাগে)। তৃতীয়ত, modulus 7, 11, 13 (M = 1001) নিয়ে একটি ছোট RNS-এ গুণ আর যোগ।

from math import prod
from sympy.ntheory.modular import crt as sympy_crt

def crt_coprime(rs, ms):           # the constructive proof, pairwise coprime moduli
    M = prod(ms)
    x = 0
    for r, m in zip(rs, ms):
        Mi = M // m
        x += r * Mi * pow(Mi, -1, m)
    return x % M, M

def brute(rs, ms):                 # try 0, 1, 2, ... until every remainder fits
    x = 0
    while any(x % m != r for r, m in zip(rs, ms)):
        x += 1
    return x, x + 1                # answer, numbers tried

print("Sunzi:", crt_coprime([2, 3, 2], [3, 5, 7]), "  vans:", crt_coprime([1, 2, 3], [3, 5, 7]))
for ms in ([3, 5, 7], [11, 13, 17], [11, 13, 17, 19], [17, 19, 23, 29]):
    rs = [m - 2 for m in ms]
    x, M = crt_coprime(rs, ms)
    bx, tried = brute(rs, ms)
    print(f"moduli {ms}: CRT {x} (mod {M}), brute force {bx} after {tried} tries")
print("sympy agrees:", sympy_crt([17, 19, 23, 29], [5, 7, 1, 20]) == crt_coprime([5, 7, 1, 20], [17, 19, 23, 29]))

big = [10**9 + 7, 998244353, 10**9 + 9]          # three primes near 10^9
x, M = crt_coprime([1, 2, 3], big)
print("near 1e9: M has", len(str(M)), "digits; x mod each:", [x % m for m in big])

rns = (7, 11, 13)                                 # residue number system, M = 1001
ra, rb = [123 % m for m in rns], [7 % m for m in rns]
mul = [u * v % m for u, v, m in zip(ra, rb, rns)]
add = [(u + v) % m for u, v, m in zip(ra, rb, rns)]
print("123 ->", ra, " 7 ->", rb)
print("product", mul, "->", crt_coprime(mul, rns)[0], "  sum", add, "->", crt_coprime(add, rns)[0])

Sunzi: (23, 105)   vans: (52, 105)
moduli [3, 5, 7]: CRT 103 (mod 105), brute force 103 after 104 tries
moduli [11, 13, 17]: CRT 2429 (mod 2431), brute force 2429 after 2430 tries
moduli [11, 13, 17, 19]: CRT 46187 (mod 46189), brute force 46187 after 46188 tries
moduli [17, 19, 23, 29]: CRT 215439 (mod 215441), brute force 215439 after 215440 tries
sympy agrees: True
near 1e9: M has 27 digits; x mod each: [1, 2, 3]
123 -> [4, 2, 6]  7 -> [0, 7, 7]
product [0, 3, 3] -> 861   sum [4, 9, 0] -> 130

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

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

অঙ্ক ১: 14x ≡ 30 (mod 100)-এর সব সমাধান বের করুন

1. d = gcd(14, 100) = 2, আর 2 ∣ 30, তাই ঠিক ২টি সমাধান mod 100.
2. 2 দিয়ে ভাগ: 7x ≡ 15 (mod 50). 7 · 43 = 301 = 6 · 50 + 1, তাই 7⁻¹ ≡ 43 (mod 50). (Extended Euclid: 50 = 7 · 7 + 1, তাই 1 = 50 − 7 · 7, অর্থাৎ 7⁻¹ ≡ −7 ≡ 43.)
3. x ≡ 15 · 43 = 645 ≡ 45 (mod 50). mod 100-এ সমাধান 45 আর 95. যাচাই: 14 · 45 = 630 ≡ 30, 14 · 95 = 1330 ≡ 30 (mod 100).

অঙ্ক ২: গুদামের প্যাকেট ৫টির বাক্সে ভরলে ৩টি, ৭টির বাক্সে ২টি, ১১টির বাক্সে ৪টি বাঁচে। ৫০০-এর কম কয়টি প্যাকেট হতে পারে?

1. x ≡ 3 (mod 5), x ≡ 2 (mod 7), x ≡ 4 (mod 11); 5, 7, 11 মৌলিক, তাই CRT খাটে, M = 385.
2. Back-substitution: x = 3 + 5k; 3 + 5k ≡ 2 (mod 7) ⇒ 5k ≡ 6 (mod 7). 5 · 3 = 15 ≡ 1, তাই k ≡ 18 ≡ 4, আর x = 23 + 35j.
3. 23 + 35j ≡ 4 (mod 11). 23 ≡ 1 আর 35 ≡ 2, তাই 2j ≡ 3 (mod 11). 2⁻¹ ≡ 6, তাই j ≡ 18 ≡ 7, আর x = 23 + 245 = 268.
4. সব সমাধান 268 + 385t. ৫০০-এর কম ধনাত্মক মান শুধু 268 (পরেরটি 653). যাচাই: 268 = 53 · 5 + 3 = 38 · 7 + 2 = 24 · 11 + 4.

অঙ্ক ৩: x ≡ 5 (mod 8), x ≡ 1 (mod 12), x ≡ 9 (mod 18)-এর সমাধান আছে কি?

Modulus সহমৌলিক নয়, তাই প্রতিটি জোড়ার শর্ত দেখতে হবে। (8, 12): gcd 4, আর 5 − 1 = 4, বিভাজ্য। (8, 18): gcd 2, আর 5 − 9 = −4, বিভাজ্য। (12, 18): gcd 6, আর 1 − 9 = −8, যা 6 দিয়ে বিভাজ্য নয়। তাই সমাধান নেই: দ্বিতীয় শর্তে x ≡ 1 (mod 6), তৃতীয় শর্তে x ≡ 9 ≡ 3 (mod 6), দুটি একসঙ্গে অসম্ভব। §৫-এর ব্লকের শেষ লাইন একই কথা বলে।

অঙ্ক ৪: 17-এর inverse mod 3120 ব্যবহার করে 17x ≡ 9 (mod 3120) সমাধান করুন

§২-এর স্টেপার থেকে 17⁻¹ ≡ 2753. তাই x ≡ 9 · 2753 = 24777 = 7 · 3120 + 2937 ≡ 2937 (mod 3120). gcd 1 বলে এটিই একমাত্র সমাধান। যাচাই: 17 · 2937 = 49929 = 16 · 3120 + 9.

প্রমাণের ভুল ধরুন: “6x ≡ 12 (mod 9)-এর একমাত্র সমাধান x = 2”

একজন লিখলেন: “6x ≡ 12 (mod 9). দুই পাশকে 6 দিয়ে ভাগ করে x ≡ 2 (mod 9). তাই 0 থেকে 8-এর মধ্যে একমাত্র সমাধান 2. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: mod 9-এ 6 দিয়ে “ভাগ” মানে 6⁻¹ দিয়ে গুণ, কিন্তু gcd(6, 9) = 3, তাই উপপাদ্য ১.২ অনুযায়ী 6-এর inverse নেই। কাটাকাটির নিয়ম বলে 6x ≡ 6 · 2 থেকে শুধু x ≡ 2 (mod 9/3 = 3) পাওয়া যায়। উপপাদ্য ৩.১-ও একই কথা বলে: d = 3 ∣ 12, তাই ঠিক ৩টি সমাধান, 2, 5, 8. যাচাই: 6 · 5 = 30 ≡ 3 আর 6 · 8 = 48 ≡ 3, আর 12 ≡ 3 (mod 9). প্রমাণটি সমাধান 2 ঠিক পেয়েছে, কিন্তু “একমাত্র” দাবিটি মিথ্যা। শিক্ষা: modulo-র জগতে ভাগের আগে সবসময় gcd দেখুন।

৮ · AI-এর যুগে — congruence আর CRT-এর উত্তর যাচাই

AI সহকারীকে একটি linear congruence বা CRT-এর system দিলে উত্তর সাধারণত দ্রুত আর আত্মবিশ্বাসী আসে। কিন্তু modular হিসাবে একটি অঙ্কের ভুলই পুরো উত্তর বদলে দেয়, আর বড় সংখ্যায় ভাষা-মডেলের মাথায় গুণ-ভাগ প্রায়ই ভুল হয়। AI-এর কিছু ভুল নিয়মিত:

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

• প্রতিটি inverse-এর জন্য a · s mod m = 1 নিজে মিলিয়েছি
• d = gcd(a, m) বের করেছি, আর সমাধানের সংখ্যা ঠিক d (বা d ∤ b হলে শূন্য)
• কোথাও modulus না বদলে কাটাকাটি করা হয়নি
• CRT-এর আগে প্রতিটি জোড়া modulus-এর gcd দেখেছি; উত্তরের modulus lcm কি না দেখেছি
• শেষ উত্তর প্রতিটি মূল শর্তে বসিয়ে Python-এ মিলিয়েছি, আর ছোট ক্ষেত্রে brute force-এর সঙ্গে তুলনা করেছি
• উপপাদ্যের শর্ত (সহমৌলিক, m ≥ 2) আর ইতিহাসের সাল বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

সবচেয়ে সস্তা প্রথম পরীক্ষা: AI যে x দিল, সেটি প্রতিটি congruence-এ বসান। এক লাইনের Python-এ এটি করা যায়, আর একটি অমিলই উত্তরটি বাতিল করার জন্য যথেষ্ট। কিন্তু মিললেই কাজ শেষ নয়: “এটিই একমাত্র সমাধান” বা “কোনো সমাধান নেই” ধরনের দাবিও উপপাদ্য ৩.১ বা ৫.১ দিয়ে আলাদা করে যাচাই করুন।