127 — Chinese Remainder Theorem Basic¶
এই note-এ আমরা একটা সুন্দর ধাঁধা সমাধান করব — "দুটো ভাঙা ঘড়ির reading থেকে আসল সময় বের করা"। আবারও মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — CRT interview-তে প্রায় আসে না, কিন্তু CP-তে (বিশেষ করে CSES Mathematics-এ) এটা ঘন ঘন ফিরবে। 125-এর extended Euclid এখানে আবার চাবি হিসেবে আসবে, তাই ওটা ঝালাই করা থাকলে ভালো।
Source¶
- Original source: CP-Algorithms — Chinese Remainder Theorem
- Platform: CP-Algorithms — https://cp-algorithms.com/algebra/chinese-remainder-theorem.html
- Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
- Difficulty: Hard
- Pattern: modulus merge
- Basic idea inherited from: 125 (Extended Euclidean Algorithm)
1. Problem in simple words¶
দুটো শর্ত (congruence) দেওয়া আছে একটা অজানা সংখ্যা x-এর উপর:
x ≡ a1 (mod m1) (x-কে m1 দিয়ে ভাগ করলে ভাগশেষ a1)
x ≡ a2 (mod m2) (x-কে m2 দিয়ে ভাগ করলে ভাগশেষ a2)
খুঁজে বের করতে হবে এমন একটা x যেটা দুটো শর্তই একসাথে মানে। basic CRT ধরে নেয় m1 আর m2 coprime (gcd = 1) — তখন 0 থেকে m1·m2 − 1-এর মধ্যে উত্তর ঠিক একটাই, আর পুরো উত্তরটা হয় x ≡ ans (mod m1·m2)।
মনে রেখো — এই level CP-leaning, interview-optional। কিন্তু CRT-র গল্পটা সংখ্যাতত্ত্বের সবচেয়ে মার্জিত ফলাফলগুলোর একটা।
2. What is the math idea?¶
মূল idea — দুটো আলাদা modulus-কে এক বড় modulus-এ merge করা। যদি m1, m2 coprime হয়, তবে দুটো ভিন্ন ভাগশেষ-শর্ত একসাথে ঠিক একটা সমাধান শ্রেণি (mod m1·m2) তৈরি করে — এটাই Chinese Remainder Theorem।
কীভাবে বের করি? x = a1 + m1·t লিখি (এটা প্রথম শর্ত আপনিই মানে, যেকোনো integer t-তে)। তারপর দ্বিতীয় শর্তে বসাই:
এখানে m1⁻¹ (mod m2) লাগে — আর সেটা দেয় আমাদের পুরোনো বন্ধু extended Euclid (125)। এই level CP-leaning হলেও দেখো, পুরোটাই 125-এর উপর দাঁড়ানো।
3. Which basic idea does this inherit from?¶
সরাসরি 125 (Extended Euclidean Algorithm)। CRT-র গোটা হিসাবের কেন্দ্রে m1-এর inverse mod m2 — আর coprime দুটো সংখ্যার inverse বের করার একমাত্র সাধারণ হাতিয়ার extended Euclid (m1·p + m2·q = 1 থেকে p = m1⁻¹ mod m2)।
তাই শিকড়ের শৃঙ্খল: 125 (ext Euclid) → 127 (CRT)। আর 126 (Diophantine)-এর "combination-এ ঠিক মান বানানো" চিন্তাও এখানে কাজে লাগে। মনে রাখো — README-র recommended order-এ 127 ঠিক 125-এর পরেই, কারণ এটা ext-Euclid-এর সবচেয়ে সরাসরি প্রয়োগ।
4. Real-life analogy¶
ভাবো একটা ঘটনা ঘটেছিল, কিন্তু সঠিক সময় ভুলে গেছ। হাতে দুটো ভাঙা ঘড়ি:
- একটা 3-ঘণ্টার ঘড়ি (শুধু 0, 1, 2 দেখায়) — সেটায় কাঁটা ছিল 2-এ →
x ≡ 2 (mod 3) - একটা 5-ঘণ্টার ঘড়ি (0 থেকে 4) — সেটায় কাঁটা ছিল 3-এ →
x ≡ 3 (mod 5)
আলাদাভাবে প্রতিটা ঘড়ি অনেক সময়ের সাথে মেলে। কিন্তু দুটো একসাথে মেলানোর সময়? দুই ঘড়ির "মোট চক্র" হলো 3 × 5 = 15 ঘণ্টা (যেহেতু coprime), আর সেই 15 ঘণ্টার মধ্যে দুটো reading একসাথে মেলে ঠিক একবার — সময়টা 8। তার পরের বার আবার 8 + 15 = 23, তারপর 38... ।
CRT হলো সেই কৌশল যা দুই ভাঙা ঘড়ির আংশিক তথ্য জুড়ে আসল সময়টা (mod 15) বের করে দেয়।
5. Visual explanation¶
x ≡ 2 (mod 3) আর x ≡ 3 (mod 5) মেলাই — আগে চোখে, তারপর সূত্রে:
চোখে — দুই তালিকা মিলিয়ে দেখা:
x ≡ 2 (mod 3): 2, 5, 8, 11, 14, 17, ...
x ≡ 3 (mod 5): 3, 8, 13, 18, ...
▲
প্রথম মিল x = 8, পরেরটা 8 + 15 = 23 ...
উত্তর: x ≡ 8 (mod 15)
সূত্রে (merge):
x = a1 + m1·t = 2 + 3t [প্রথম শর্ত মানা]
দ্বিতীয় শর্তে: 2 + 3t ≡ 3 (mod 5)
3t ≡ 1 (mod 5)
t ≡ 1 · (3⁻¹ mod 5) (mod 5)
3⁻¹ mod 5 = 2 [কারণ 3·2 = 6 ≡ 1]
t ≡ 1·2 = 2 (mod 5)
x = 2 + 3·2 = 8 ✓
নতুন modulus = m1·m2 = 15
লক্ষ করো — 3⁻¹ mod 5 বের করতেই extended Euclid-এর দরকার। আর উত্তর 8 দুই তালিকার প্রথম মিল-এর সাথে হুবহু মিলল।
6. Example input and output¶
input (a1, m1, a2, m2) -> output (ans, mod)
----------------------------------------------------------------
2, 3, 3, 5 -> (8, 15) 8%3=2 ✓, 8%5=3 ✓
2, 3, 2, 7 -> (2, 21) 2%3=2 ✓, 2%7=2 ✓
1, 4, 2, 9 -> (29, 36) 29%4=1 ✓, 29%9=2 ✓
0, 5, 0, 7 -> (0, 35) 0 দুটোই মানে
3, 5, 1, 11 -> (23, 55) 23%5=3 ✓, 23%11=1 ✓
খেয়াল করো: basic CRT ধরে নেয় m1, m2 coprime — যেমন (3, 5), (4, 9), (5, 11)। coprime না হলে (যেমন m1 = 4, m2 = 6) এই সরল সূত্র চলে না; তখন general CRT লাগে (নিচে common mistakes-এ)। উত্তর সবসময় 0 থেকে m1·m2 − 1-এর মধ্যে normalize করা হয়।
7. Brute force thinking¶
inverse-টিন্স ছাড়া প্রথম idea — 0 থেকে m1·m2 − 1 পর্যন্ত প্রতিটা সংখ্যা চেক করা, কোনটা দুটো শর্তই মানে:
def crt_brute(a1, m1, a2, m2):
for x in range(m1 * m2):
if x % m1 == a1 % m1 and x % m2 == a2 % m2:
return x, m1 * m2
return None
ছোট moduli-তে (3, 5) এটা সহজেই 8 খুঁজে দেয়। coprime হলে সমাধান নিশ্চিত আছে — তাই এটা সবসময় উত্তর পায়। শুরুর জন্য একদম ঠিক।
8. Why brute force may be slow¶
loop ঘোরে m1 · m2 বার। ছোট moduli-তে কিছুই না, কিন্তু moduli বড় হলে সর্বনাশ:
m1, m2 ছোট (3, 5): 15 বার loop — চোখের পলক
m1, m2 = 10⁶, 10⁶: 10¹² বার loop — কয়েক দিন!
CRT merge (inverse): O(log m) — মুহূর্তে
দুটো বড় modulus-এ brute force কার্যত অচল। অথচ আসল CRT merge শুধু একটা extended Euclid (log ধাপ) আর কয়েকটা গুণ — তাই moduli যত বড়ই হোক, প্রায় তাৎক্ষণিক।
9. Better thinking¶
মূল insight — খোঁজার দরকার নেই, সরাসরি হিসাব করা যায়। ধাপগুলো:
1. x = a1 + m1·t ধরো (প্রথম শর্ত আপনিই মানা)
2. দ্বিতীয় শর্তে বসাও: a1 + m1·t ≡ a2 (mod m2)
3. m1·t ≡ (a2 − a1) (mod m2)
4. t ≡ (a2 − a1) · inv(m1, m2) (mod m2) [extended Euclid!]
5. x = a1 + m1·t, নতুন modulus = m1·m2
6. উত্তর normalize: x % (m1·m2)
পুরো ব্যাপারটা একটা inverse আর কয়েকটা গুণ-যোগে শেষ। inverse-টাই একমাত্র "ভারী" ধাপ, আর সেটা 125-এর ext-gcd দিয়ে O(log m)। coprime হওয়ায় inverse সবসময় থাকে — তাই merge সবসময় সফল।
10. Thinking tweak¶
আসল "আহা" মুহূর্ত: x = a1 + m1·t লিখে ফেললে প্রথম শর্ত আর ভাবতে হয় না — শুধু দ্বিতীয় শর্ত থেকে t বের করলেই হলো।
brute force দুটো শর্ত একসাথে মেলাতে পুরো range চষছিল; tweak হলো — একটা শর্তকে x-এর গঠনে (a1 + m1·t) ঢুকিয়ে দাও, তখন বাকি থাকে শুধু একটা variable t, আর একটা congruence — যা inverse দিয়ে এক ধাপে solve হয়। দুই শর্তের যুগপৎ খোঁজা থেকে এক variable-এর সরল সমাধানে নেমে এল।
11. Step-by-step dry run¶
crt(2, 3, 3, 5) — মানে x ≡ 2 (mod 3), x ≡ 3 (mod 5):
| step | কী করছি | মান |
|---|---|---|
| 1 | g, p, q = ext_gcd(m1, m2) = ext_gcd(3, 5) | g = 1, p = 2, q = −1 (3·2 + 5·(−1) = 1) |
| 2 | p হলো m1⁻¹ mod m2 → 3⁻¹ mod 5 | p = 2 (যেহেতু 3·2 = 6 ≡ 1 mod 5) |
| 3 | diff = a2 − a1 = 3 − 2 | 1 |
| 4 | t = (diff · p) % m2 = (1·2) % 5 | t = 2 |
| 5 | x = a1 + m1·t = 2 + 3·2 | x = 8 |
| 6 | mod = m1·m2 = 3·5 | 15 |
| 7 | normalize: 8 % 15 | 8 |
| 8 | যাচাই: 8 % 3 = 2 ✓, 8 % 5 = 3 ✓ | (8, 15) |
চূড়ান্ত: (8, 15)। দুই ঘড়ির reading মিলে গেল ঠিক 8-এ — section 5-এর চোখে-দেখা মিলের সাথে হুবহু।
12. Python solution¶
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 crt(a1, m1, a2, m2):
"""x ≡ a1 (mod m1), x ≡ a2 (mod m2) merge করে (ans, m1*m2)।
ধরে নেয় gcd(m1, m2) = 1 (basic CRT)।"""
g, p, _ = ext_gcd(m1, m2)
assert g == 1, "basic CRT-তে m1, m2 coprime হতে হবে"
mod = m1 * m2
diff = (a2 - a1) % m2
t = (diff * p) % m2 # p = m1⁻¹ mod m2
x = (a1 + m1 * t) % mod
return x, mod
def crt_list(remainders, moduli):
"""একাধিক congruence জোড়ায় জোড়ায় merge করে।"""
cur_a, cur_m = remainders[0], moduli[0]
for a, m in zip(remainders[1:], moduli[1:]):
cur_a, cur_m = crt(cur_a, cur_m, a, m)
return cur_a, cur_m
# --- ছোট test গুলো (সব pass করা উচিত) ---
from math import gcd
def verify(a1, m1, a2, m2):
ans, mod = crt(a1, m1, a2, m2)
assert mod == m1 * m2, f"mod ভুল: {a1,m1,a2,m2}"
assert ans % m1 == a1 % m1, f"শর্ত 1 ভাঙল: {a1,m1,a2,m2} -> {ans}"
assert ans % m2 == a2 % m2, f"শর্ত 2 ভাঙল: {a1,m1,a2,m2} -> {ans}"
assert 0 <= ans < mod, f"range বাইরে: {ans}"
verify(2, 3, 3, 5)
verify(2, 3, 2, 7)
verify(1, 4, 2, 9)
verify(0, 5, 0, 7)
verify(3, 5, 1, 11)
verify(10, 13, 4, 17)
# একাধিক congruence: x ≡ 2(3), 3(5), 2(7) -> CSES classic
multi, mmod = crt_list([2, 3, 2], [3, 5, 7])
assert multi % 3 == 2 and multi % 5 == 3 and multi % 7 == 2
assert mmod == 3 * 5 * 7
# brute force-এর সাথে cross-check
def crt_brute(a1, m1, a2, m2):
for x in range(m1 * m2):
if x % m1 == a1 % m1 and x % m2 == a2 % m2:
return x
return None
for (a1, m1, a2, m2) in [(2,3,3,5), (1,4,2,9), (3,5,1,11), (2,3,2,7)]:
assert crt(a1, m1, a2, m2)[0] == crt_brute(a1, m1, a2, m2)
print(crt(2, 3, 3, 5)) # (8, 15)
print(crt(1, 4, 2, 9)) # (29, 36)
print(crt_list([2, 3, 2], [3, 5, 7])) # (23, 105)
print("সব test pass!")
13. Line-by-line explanation¶
def crt(a1, m1, a2, m2):
g, p, _ = ext_gcd(m1, m2)
assert g == 1, "basic CRT-তে m1, m2 coprime হতে হবে"
extended Euclid দিয়ে m1·p + m2·q = g পাচ্ছি। coprime হলে g = 1, আর তখন p হলো m1-এর inverse mod m2। coprime না হলে assert থামিয়ে দেয় (basic CRT-র সীমা)।
merge-এর গণিত: m1·t ≡ (a2 − a1) (mod m2) থেকে t = (a2 − a1)·m1⁻¹ mod m2। diff-কে আগে % m2 করছি যাতে negative না হয়।
x = a1 + m1·t প্রথম শর্ত মানে, আর t-এর হিসাবে দ্বিতীয়টাও। শেষে % mod দিয়ে 0 থেকে m1·m2 − 1-এ normalize।
দুটোর বেশি congruence? একটা একটা করে আগেরটার সাথে merge — প্রতি merge-এ modulus গুণ হয়ে বড় হয়। এভাবে CSES-এর মতো অনেক congruence-ও সামলানো যায়।
বাকি verify, brute-force cross-check আর assert লাইনগুলো নিশ্চিত করে — উত্তর দুটো শর্তই মানে, range-এ আছে, আর brute force-এর সাথে হুবহু মেলে। সব ঠিক থাকলে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম লাইন crt(2, 3, 3, 5) → (8, 15): 8 % 3 = 2, 8 % 5 = 3। দ্বিতীয় crt(1, 4, 2, 9) → (29, 36): 29 % 4 = 1, 29 % 9 = 2। তৃতীয় crt_list([2,3,2], [3,5,7]) → (23, 105): 23 % 3 = 2, 23 % 5 = 3, 23 % 7 = 2 — তিন শর্তই মানে, modulus 3·5·7 = 105। সব assert ও brute-force cross-check pass — তাই সব test pass!।
15. Time complexity¶
O(log min(m1, m2)) এক জোড়া merge-এর জন্য — পুরো খরচ extended Euclid-এর (inverse বের করা)। বাকি সব O(1) গুণ-যোগ। n টা congruence merge করলে n−1 বার merge, তাই O(n · log M)। brute force-এর O(m1·m2)-এর তুলনায় বিশাল লাফ।
16. Space complexity¶
O(log min(m1, m2)) recursive ext_gcd-এর call stack-এর জন্য; iterative ext_gcd নিলে O(1)। crt নিজে কোনো বড় array রাখে না, শুধু কয়েকটা variable। crt_list-ও running pair (cur_a, cur_m) ছাড়া বাড়তি কিছু রাখে না।
17. Common mistakes¶
- moduli coprime কি না না দেখা — সবচেয়ে কমন। basic CRT শুধু
gcd(m1, m2) = 1হলে চলে। coprime না হলে general CRT লাগে: সমাধান থাকে ⟺(a1 − a2)কেgcd(m1, m2)ভাগ করে; নতুন modulus হয় lcm(m1, m2)। - diff বা t negative রেখে দেওয়া —
(a2 − a1)negative হতে পারে;% m2দিয়ে সবসময় positive-এ আনো, নইলে ভুল x। - inverse ভুল দিক থেকে নেওয়া —
pহলোm1⁻¹ mod m2(ext_gcd(m1, m2)-এর প্রথম সহগ),m2⁻¹নয়। - চূড়ান্ত উত্তর normalize না করা —
% (m1·m2)না করলে উত্তর range-এর বাইরে চলে যেতে পারে। - overflow ভাবা (অন্য ভাষায়) — Python-এ বড় সংখ্যা auto-handle হয়, কিন্তু C++/Java-তে
m1 * tবাm1 * m2overflow করতে পারে; সেখানে __int128 বা mulmod লাগে।
18. Harder problems that inherit this idea¶
- CSES — Chinese Remainder Theorem-ধাঁচের problem আর Mathematics section (https://cses.fi/problemset/) — একাধিক congruence merge।
- Codeforces — "x ≡ ... (mod ...)" merge সহ constructive problems (https://codeforces.com/problemset) — প্রায়ই general (non-coprime) CRT লাগে।
- 130 (Modular Inverse Advanced) — এই repo-রই সঙ্গী; CRT-র inverse-অংশটাই সেখানে মূল বিষয়, আর 126 (Diophantine)-এর divisibility-চিন্তা general CRT-তে ফেরে।
19. Pattern learned¶
Modulus merge via CRT — coprime দুটো congruence-কে এক বড় modulus (m1·m2)-এ মেলাও; x = a1 + m1·t-এ দ্বিতীয় শর্ত বসিয়ে t = (a2−a1)·m1⁻¹ mod m2। বড় শিক্ষা: একটা শর্তকে চলকের গঠনে ঢুকিয়ে দিলে যুগপৎ সমস্যা সরল এক-চলকের সমীকরণে নেমে আসে — আর inverse-টা সবসময় ext-Euclid থেকে।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "CRT (coprime) = x = a1 + m1·t, t = (a2−a1)·inv(m1, m2) mod m2; উত্তর mod m1·m2। non-coprime হলে general CRT (gcd | diff, lcm modulus)।" Signal: "দুটো ভিন্ন mod-এর ভাগশেষ একসাথে মেলাতে হবে" — দেখলেই CRT মনে পড়বে।
পরের ধাপ → 128 — Euler Totient Advanced (multiplicative function-এর জগৎ শুরু)। ভিত্তি → 125 — Extended Euclidean Algorithm; সঙ্গী → 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।