035 — Modular Division¶
mod-এর জগতে
/চিহ্ন কাজ করে না — কিন্তু "ভাগ" করার দরকার তো ফুরায় না। 032-এ inverse বানানো শিখেছ; এই note-এ সেই inverse দিয়ে আসল কাজটা করব: mod-জগতে ভাগ = inverse দিয়ে গুণ। ছোট্ট কিন্তু গভীর idea — nCr, probability mod, যেকোনো ভগ্নাংশ mod — সবখানে লাগবে।
Source¶
- Original source: Classic exercise (modular division via inverse)
- Platform: Classic exercise — CP-তে নিত্য; CP-Algorithms module-inverse page-এর সরাসরি প্রয়োগ
- Topic: Math-based programming fundamentals → Level 2: Modular Arithmetic
- Difficulty: Medium
- Pattern: multiply by inverse (modular division)
- Basic idea inherited from: 032 — Modular Inverse Basic (inverse দিয়ে ভাগ)
1. Problem in simple words¶
দুটো সংখ্যা a (ভাজ্য) আর b (ভাজক) আর একটা prime p দেওয়া (b যেন p-এর গুণিতক না হয়)। বের করতে হবে (a / b) mod p — মানে এমন একটা মান যা mod-জগতে "a-কে b দিয়ে ভাগ"-এর সঠিক প্রতিনিধি।
সমস্যা: mod-এ সরাসরি (a % p) / (b % p) চলে না (concept-notes-এ দেখেছ — মেলে না)। সমাধান: ভাগের বদলে b-এর inverse দিয়ে গুণ — a × b⁻¹ % p।
2. What is the math idea?¶
মূল idea — division as multiplication by inverse:
(a / b) mod p = (a × b⁻¹) mod p, যেখানে b⁻¹ হলো b-এর modular inverse
সাধারণ গণিতেও "a ÷ b" মানে আসলে "a × (1/b)"। mod-জগতে 1/b নেই, কিন্তু তার বদলি b⁻¹ আছে (032-এর Fermat inverse, b^(p−2) mod p)। তাই:
(a / b) mod p = a × b^(p−2) mod p
শর্ত: ভাগটা যেন "নিখুঁত" অর্থে valid হয় — অর্থাৎ b-এর inverse থাকতে হবে, মানে gcd(b, p) = 1 (prime p-তে b যেন p-এর গুণিতক না হয়)।
3. Which basic idea does this inherit from?¶
সরাসরি 032 — Modular Inverse Basic থেকে। 032-এ শিখেছ b⁻¹ = b^(p−2) mod p; এই note সেটা ব্যবহার করে আসল ভাগ করে। 032 ছিল "inverse কী", 035 হলো "inverse দিয়ে কী করি"।
পেছনে 028 (modular multiplication — কারণ ভাগ এখন গুণ) আর 026 (congruence — কারণ result যাচাই করি result × b ≡ a দিয়ে)। মানে inverse + গুণ = mod-জগতে ভাগ; দুই চেনা জিনিসের জোট।
4. Real-life analogy¶
ভাবো একটা দেশে ভাগ করার যন্ত্রই নেই — শুধু গুণ করা যায়। তুমি 6 টাকা 3 জনের মধ্যে ভাগ করতে চাও। ভাগ যন্ত্র নেই, তাই কী করবে?
তুমি খুঁজবে "3-এর উল্টো জিনিস" — এমন একটা সংখ্যা যাকে 3 দিয়ে গুণ করলে 1 হয় (সাধারণ গণিতে 1/3)। তারপর 6-কে সেই উল্টো দিয়ে গুণ করলেই ভাগের উত্তর। mod-জগতেও তাই: ভাগ যন্ত্র নেই, কিন্তু b-এর "উল্টো" (inverse) দিয়ে গুণ করলেই ভাগ হয়ে যায়। inverse-ই সেই হারানো ভাগ-যন্ত্রের বিকল্প।
5. Visual explanation¶
mod 7-এ "6 ভাগ 3" — inverse দিয়ে:
লক্ষ্য: (6 / 3) mod 7
mod-এ ভাগ নেই, তাই:
step 1: inverse(3) mod 7 = 5 (কারণ 3×5=15≡1)
step 2: 6 × 5 % 7 = 30 % 7 = 2
Check: result × b ≡ a ? 2 × 3 = 6 ≡ 6 (mod 7) ✓
সাধারণ গণিতেও 6/3 = 2 — এখানে মিলেও গেল
কেন সরাসরি ভাগ চলে না — একটা পাল্টা উদাহরণ:
(12 / 6) mod 4 = 2 (সত্যি)
কিন্তু ((12%4) / (6%4)) = (0 / 2) = 0 <- ভুল!
^ সরাসরি mod-করা সংখ্যায় ভাগ মেলে না
তাই inverse দিয়ে গুণই একমাত্র সঠিক পথ
6. Example input and output¶
a b p (prime) -> (a/b) mod p check (result × b % p == a % p)
----------------------------------------------------------------------
6 3 7 -> 2 2×3=6 ✓
10 2 7 -> 5 5×2=10≡3, আর 10%7=3 ✓
1 3 7 -> 5 5×3=15≡1 ✓ (= inverse(3))
8 4 7 -> 2 2×4=8≡1, 8%7=1 ✓
5 5 13 -> 1 যেকোনো/নিজে = 1
14 7 1000000007 -> 2 (বড় prime-এও)
খেয়াল করো result সবসময় 0..p−1-এর মধ্যে। আর যাচাইয়ের নিয়ম: (result × b) % p == a % p — সত্যিকার ভাগ হলে এটা মিলবেই। b যদি p-এর গুণিতক হয় (inverse নেই), ভাগ অসংজ্ঞায়িত।
7. Brute force thinking¶
কী খুঁজছি? এমন x (0..p−1) যাতে x × b ≡ a (mod p)। সব x চেষ্টা করো:
def mod_div_brute(a, b, p):
a %= p
b %= p
for x in range(p):
if (x * b) % p == a:
return x
return None # b-এর inverse না থাকলে (b ≡ 0)
ছোট p-তে সঠিক আর স্পষ্ট — সংজ্ঞাটাই সরাসরি যাচাই করছে। সমস্যা: loop চলে p পর্যন্ত।
8. Why brute force may be slow¶
loop ঘোরে p বার। p = 10⁹+7 হলে প্রায় 1 বিলিয়ন iteration — একটা ভাগেই সেকেন্ড গড়ায়। CP/interview-তে অচল।
p = 10^9+7 হলে:
brute (O(p)): ~10^9 বার চেষ্টা -> প্রতি ভাগে সেকেন্ড
inverse (O(log p)): ~30 বার গুণ -> ঝটপট
log2(10^9) ≈ 30 -> 1 বিলিয়ন বনাম 30
মূল শিক্ষা: প্রতিটা x চেষ্টা না করে, b-এর inverse এক ধাপে (Fermat, fast power) বের করে গুণো।
9. Better thinking¶
inverse দিয়ে গুণ — 032-এর mod_inverse কাজে লাগিয়ে:
def mod_inverse(b, p):
return pow(b, p - 2, p) # 032: Fermat inverse
def mod_div(a, b, p):
a %= p
b %= p
return a * mod_inverse(b, p) % p
দুই লাইনেই mod-জগতে ভাগ — O(log p)। mod_inverse ভেতরে square-and-multiply চালায়, তাই b-এর inverse এক লাফে।
চাইলে inline:
10. Thinking tweak¶
আসল "আহা!": mod-জগতে a / b মানে a × b⁻¹ — ভাগ চিহ্নটা ভুলে গিয়ে "inverse দিয়ে গুণ" ভাবো। / operator mod-এ অর্থহীন (concept-notes-এর পাল্টা উদাহরণ মনে রাখো); একমাত্র সঠিক পথ inverse।
সবচেয়ে দামি অভ্যাস: ভাগ করার পর সবসময় (result × b) % p == a % p দিয়ে মিলিয়ে নাও। mod-এর bug চোখে দেখা যায় না — এই যাচাইতেই ধরা পড়ে। আর মনে রাখো এটা শুধু prime p-তে সরল; non-prime হলে gcd(b, p)=1 লাগবে আর Extended GCD।
11. Step-by-step dry run¶
mod_div(6, 3, 7):
inverse(3) mod 7 = 3^(7-2) % 7 = 3^5 % 7, fast power-এ (5 = 101₂):
| step | exp (binary) | last bit | result | base (square হয়ে) |
|---|---|---|---|---|
| শুরু | 101 | — | 1 | 3 |
| 1 | 101 | 1 | 1×3 % 7 = 3 | 3×3 % 7 = 2 |
| 2 | 10 | 0 | 3 | 2×2 % 7 = 4 |
| 3 | 1 | 1 | 3×4 % 7 = 5 | — |
তাই inverse(3) = 5। এবার ভাগ:
উত্তর 2। Check: (2 × 3) % 7 = 6 = 6 % 7 ✓ — সত্যিকার ভাগ। আর সাধারণ গণিতেও 6/3 = 2, এখানে মিলেও গেল (যখন ভাগ "নিখুঁত")।
12. Python solution¶
def mod_inverse(b, p):
"""b-এর modular inverse mod p (Fermat, p prime, b % p != 0)।"""
b %= p
if b == 0:
raise ValueError("0-এর inverse নেই — ভাগ অসংজ্ঞায়িত")
return pow(b, p - 2, p)
def mod_div(a, b, p):
"""(a / b) mod p = a × b⁻¹ mod p (p prime)।"""
a %= p
return a * mod_inverse(b, p) % p
def mod_div_brute(a, b, p):
"""যাচাইয়ের জন্য সরল O(p): x × b ≡ a খুঁজি।"""
a %= p
b %= p
for x in range(p):
if (x * b) % p == a:
return x
return None
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert mod_div(6, 3, 7) == 2 # 6/3 = 2
assert mod_div(1, 3, 7) == 5 # 1/3 = inverse(3) = 5
assert mod_div(10, 2, 7) == 5 # 10×inv(2)=10×4=40≡5
assert mod_div(5, 5, 13) == 1 # নিজে/নিজে = 1
# মূল যাচাই: (result × b) ≡ a (mod p)
for a in range(0, 7):
for b in range(1, 7): # b ≠ 0 mod 7
x = mod_div(a, b, 7)
assert (x * b) % 7 == a % 7
# brute-এর সাথে মিল (ছোট prime):
for a in range(0, 13):
for b in range(1, 13):
assert mod_div(a, b, 13) == mod_div_brute(a, b, 13)
# বড় prime-এ যাচাই:
P = 1000000007
assert (mod_div(14, 7, P) * 7) % P == 14 % P
assert (mod_div(123456789, 987654321, P) * 987654321) % P == 123456789 % P
print(mod_div(6, 3, 7)) # 2
print(mod_div(1, 3, 7)) # 5
print(mod_div(14, 7, 1000000007)) # 2
print("সব test pass!")
13. Line-by-line explanation¶
032-এর Fermat inverse: b-কে ঘড়িতে নামাই; 0 হলে inverse নেই, তাই error (নাহলে ভাগ ভুল হতো); নাহলে b^(p−2) mod p।
এটাই হৃদয়: ভাগ = a গুণ b-এর inverse, তারপর % p। / চিহ্ন নেই কোথাও — পুরোটাই গুণ।
mod_div_brute-এ সংজ্ঞা সরাসরি: কোন x-এ x × b ≡ a। শুধু যাচাই আর বোঝার জন্য।
এই double loop প্রতিটা (a, b)-র জন্য result × b ≡ a নিশ্চিত করছে — ভাগের সংজ্ঞাই যাচাই। আর mod_div_brute-এর সাথে মিলিয়ে দ্বিগুণ নিশ্চিত। বড় prime-এও একই যাচাই। সব ঠিক থাকলে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম লাইন mod_div(6, 3, 7) → 2 (6/3)। দ্বিতীয় mod_div(1, 3, 7) → 5 (1/3 = inverse(3))। তৃতীয় mod_div(14, 7, 10⁹+7) → 2 (14/7, বড় prime-এও সরল)। আগের সব assert (সংজ্ঞা + brute মিল + বড় prime সহ) চুপচাপ pass — তারপর সব test pass!।
15. Time complexity¶
O(log p) — মূল খরচ mod_inverse-এর pow(b, p-2, p) (square-and-multiply), তারপর একটা গুণ। p = 10⁹+7-এও ~30 ধাপ। brute O(p) (~10⁹)-এর তুলনায় বিশাল লাফ।
16. Space complexity¶
O(1) — pow iterative, শুধু গুটিকয় variable। কোনো list/array লাগে না।
17. Common mistakes¶
- সরাসরি
/বা//ব্যবহার —(a % p) // (b % p)mod-জগতে ভুল (concept-notes-এর পাল্টা উদাহরণ)। ভাগ মানে inverse দিয়ে গুণ। b % p == 0ভুলে যাওয়া — তখন inverse নেই, ভাগ অসংজ্ঞায়িত; না ধরলে ভুল 0 বা crash।- non-prime mod-এ Fermat —
b^(p−2)inverse দেয় শুধু p prime হলে। non-prime হলে gcd(b, p)=1 লাগবে + Extended GCD; gcd≠1 হলে ভাগই হয় না। aআগে mod না নেওয়া —aবড় হলেa %= pআগে নিলে গুণফল ছোট থাকে; না নিলে অযথা বড়/C++-এ overflow।- ভাগের পর যাচাই না করা —
(result × b) % p == a % pদিয়ে মিলিয়ে নাও; mod-এর bug একমাত্র এভাবেই ধরা পড়ে। - "নিখুঁত ভাগ" আশা করা —
(a/b) mod p-এর উত্তর সাধারণ ভাগফলের সমান নাও হতে পারে (যখন b, a-কে নিঃশেষে ভাগ করে না); এটা mod-অর্থে সঠিক, integer ভাগফল নয়।
18. Harder problems that inherit this idea¶
- 034 (nCr mod Prime) (https://cp-algorithms.com/combinatorics/binomial-coefficients.html) —
n!/(r!(n−r)!)-এর ভাগটাই এই inverse-গুণ; সরাসরি প্রয়োগ। - Probability / expected value mod p problems — উত্তর ভগ্নাংশ
P/QহলেP × Q⁻¹ mod pচাওয়া হয়; এই modular division-ই চাবি। - CSES — Binomial Coefficients / Exponentiation II (https://cses.fi/problemset/task/1079) — ভাগ mod p দরকার এমন combinatorial problem।
19. Pattern learned¶
Modular division = multiply by inverse — (a / b) mod p = a × b⁻¹ mod p, যেখানে b⁻¹ = b^(p−2) (Fermat, p prime)। / চিহ্ন mod-এ অর্থহীন। সবসময় (result × b) % p == a % p দিয়ে যাচাই করো।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "mod-এ ভাগ = inverse দিয়ে গুণ: (a/b) mod p = a × pow(b, p-2, p) % p। / চিহ্ন ভুলে যাও। 'mod-জগতে ভগ্নাংশ/ভাগ লাগছে' দেখলেই inverse-গুণ মনে পড়ুক — আর result × b ≡ a মিলিয়ে নাও।"
পরের ধাপ → 036 — Cyclic Remainder Pattern (power-এর remainder কীভাবে চক্রে ঘোরে)। সম্পর্কিত → 032 — Modular Inverse Basic, 034 — nCr mod Prime।
ফিরে দেখা: এই 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" / "CP-তে নিত্য দরকারি" লেখা।