Problem link ও উৎস
- **Original source:** CP-Algorithms — Modular Multiplicative Inverse
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Medium
- **Pattern:** Fermat inverse (a^(p−2) mod p)
- **Basic idea inherited from:** 029 — Modular Exponentiation (fast power দিয়ে a^(p−2))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যা `a` আর একটা **prime** `p` দেওয়া (আর `a` যেন `p`-এর গুণিতক না হয়)। বের করতে হবে `a`-এর **modular inverse** — মানে এমন একটা `x`, যাতে:
`(a × x) % p == 1`
সাধারণ ভাষায়: এমন `x` যাকে দিয়ে `a` গুণ করলে ঘড়িতে ঠিক 1-এ পৌঁছাই। যেমন mod 7-এ 3-এর inverse 5, কারণ `3 × 5 = 15 ≡ 1 (mod 7)`।
এই inverse-ই mod-জগতে "ভাগ" করার চাবি (035-এ দেখবে)।
### Input ও output {#6-example-input-and-output}
```text
a p -> inverse check (a × inv % p)
-----------------------------------------------------
3 7 -> 5 3×5=15 ≡ 1 ✓
2 7 -> 4 2×4=8 ≡ 1 ✓
1 7 -> 1 1×1=1 ≡ 1 ✓
6 7 -> 6 6×6=36 ≡ 1 ✓ (6 ≡ -1, নিজেই নিজের inverse)
10 13 -> 4 10×4=40 ≡ 1 (mod 13) ✓
2 1000000007 -> 500000004 2×500000004 ≡ 1 ✓
```
খেয়াল করো: prime mod-এ **প্রতিটা** non-zero `a`-র inverse থাকে (ঠিক একটা)। `a = 0` বা `a` যদি `p`-এর গুণিতক হয় — তখন inverse নেই (0-কে দিয়ে গুণ করে কখনো 1 হয় না)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **তালা-চাবি**। `a` একটা তালা। তুমি এমন একটা চাবি `x` খুঁজছ, যেটা ঘোরালে তালা ঠিক "শুরুর অবস্থানে" (1-এ) ফিরে আসে।
সাধারণ গণিতে এই চাবি হলো `1/a` — গুণ করলে 1। কিন্তু mod-জগতে ভগ্নাংশ নেই, তাই চাবিটা একটা **পূর্ণসংখ্যা** হতে হবে। Fermat বলে দেয়: সেই চাবি হলো `a`-কে `(p−2)` বার নিজে দিয়ে গুণ করলে যা পাও (mod p)। অদ্ভুত শোনালেও — গুণ করে মিলিয়ে দেখো, ঠিক 1 হয়। ঘড়ির গণিতের এই চাবি-বানানোই modular inverse।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **029 — Modular Exponentiation** থেকে। inverse = `a^(p−2) mod p` — এটা নিছক একটা বিশাল exponent-এর power, যা square-and-multiply ছাড়া দ্রুত বের করা যায় না (`p` 10⁹+7 হলে exponent ~10⁹)।
আর শিকড়ে congruence (026) আর গুণ (028) — কারণ inverse-এর পুরো ধারণাই "গুণ করে 1 পাওয়া" (028-এর modular multiplication) আর "একই ঘরে (≡ 1)" (026-এর congruence)। 029 না থাকলে এই power বের করাই অসম্ভব হতো।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **Fermat's little theorem**। `p` prime আর `a` যদি `p`-এর গুণিতক না হয়:
`a^(p−1) ≡ 1 (mod p)`
এখন দুই পাশ থেকে একটা `a` খুলে নাও:
`a × a^(p−2) ≡ 1 (mod p)`
তুলনা করো inverse-এর সংজ্ঞা `a × x ≡ 1`-এর সাথে — দেখো `x = a^(p−2) mod p`! মানে:
`a⁻¹ ≡ a^(p−2) (mod p)`
আর `a^(p−2) mod p` বের করা মানেই 029-এর fast power। তাই inverse = `pow(a, p-2, p)` — O(log p)-তে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
inverse-এর সংজ্ঞা সরাসরি ব্যবহার করো: 1 থেকে p−1 পর্যন্ত প্রতিটা `x` চেষ্টা করো, যেটায় `(a × x) % p == 1` সেটাই inverse।
```python
def inverse_brute(a, p):
a %= p
for x in range(1, p):
if (a * x) % p == 1:
return x
return None # inverse নেই (a ও p coprime না হলে)
```
ছোট `p`-তে ঠিকঠাক কাজ করে, আর বোঝার জন্য সবচেয়ে স্পষ্ট। সমস্যা শুধু — loop চলে p পর্যন্ত।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে p−1 বার। CP-তে `p = 10⁹+7` — মানে প্রায় 1 বিলিয়ন iteration প্রতিটা inverse-এর জন্য। একটা inverse-এই কয়েক সেকেন্ড, আর nCr-এ লক্ষ লক্ষ inverse লাগে — সম্পূর্ণ অসম্ভব।
```text
p = 10^9+7 হলে:
brute (O(p)): ~10^9 বার চেষ্টা -> প্রতি inverse-এ সেকেন্ড লাগে
Fermat (O(log p)): ~30 বার গুণ -> চোখের নিমেষে
log2(10^9) ≈ 30 -> 1 বিলিয়ন বনাম 30
```
মূল শিক্ষা: প্রতিটা x চেষ্টা না করে, Fermat-এর সূত্রে সরাসরি একটা power-এ লাফ দাও।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
Fermat: `a⁻¹ = a^(p−2) mod p`। 029-এর fast power দিয়ে এক ধাপে:
```python
def mod_inverse(a, p):
"""p অবশ্যই prime, আর a % p != 0।"""
return pow(a, p - 2, p) # Python-এর তিন-argument pow = fast power
```
ব্যস — O(log p)-তে inverse। `pow(a, p-2, p)` ভেতরে square-and-multiply চালায়, তাই বিশাল exponent (p−2 ≈ 10⁹)-ও ~30 ধাপে।
চাইলে নিজের fast power দিয়েও (029-এর `power_mod`):
```python
def mod_inverse_manual(a, p):
return power_mod(a, p - 2, p) # 029-এর engine
```
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **mod-জগতে "1/a" মানে আসলে "a^(p−2)" (p prime) — ভগ্নাংশ নয়, একটা পূর্ণসংখ্যা power।** Fermat দুই পাশ থেকে এক `a` খুলে দিয়ে এই জাদুটা দেখায়: `a^(p−1) ≡ 1` → `a × a^(p−2) ≡ 1`।
সতর্কতার tweak: এটা **শুধু p prime হলে** চলে। `p` prime না হলে (যেমন mod 10) Fermat অচল — তখন Extended GCD লাগে (gcd(a,p)=1 হলে; নাহলে inverse-ই নেই)। তাই inverse লেখার আগে নিজেকে জিজ্ঞেস করো: "mod কি prime?"
### ছবিতে বোঝা {#5-visual-explanation}
mod 7-এ 3-এর সব গুণফল দেখো — কোথায় 1 হয়:
```text
mod 7 এ 3-এর গুণের সারি:
3×1=3, 3×2=6, 3×3=9≡2, 3×4=12≡5, 3×5=15≡1 <-- এখানে!
^
3 × 5 ≡ 1 (mod 7) -> inverse(3) = 5
```
Fermat দিয়ে সেই 5 বের করা (p = 7, তাই p−2 = 5):
```text
inverse(3) = 3^(7-2) % 7 = 3^5 % 7
fast power-এ: 3^1=3, 3^2=2, 3^4=4, 3^5 = 3^4 × 3 = 4×3 = 12 % 7 = 5
^ মিলল!
Check: 3 × 5 = 15 = 7×2 + 1 -> ≡ 1 ✓
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`mod_inverse(3, 7)` = `3^(7-2) % 7` = `3^5 % 7`, fast power-এ (5 = 101₂):
| step | b (binary) | last bit | result | a (square হয়ে) |
| --- | --- | --- | --- | --- |
| শুরু | 101 | — | 1 | 3 % 7 = 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 | 4×4 % 7 = 2 |
`b` এখন 0, উত্তর **5**। Check: `3 × 5 = 15 % 7 = 1` ✓ — সত্যিই inverse।
মিলিয়ে দেখো brute-এর সাথে: 1..6-এ একমাত্র x=5 দেয় `3×5 % 7 = 1`। দুই পথে একই উত্তর।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def mod_inverse(a, p):
"""a-এর modular inverse mod p, Fermat-এ a^(p-2)। p prime, a % p != 0 ধরে।"""
a %= p
if a == 0:
raise ValueError("0-এর inverse নেই")
return pow(a, p - 2, p)
def inverse_brute(a, p):
"""যাচাইয়ের জন্য সরল O(p) version।"""
a %= p
for x in range(1, p):
if (a * x) % p == 1:
return x
return None
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert mod_inverse(3, 7) == 5
assert mod_inverse(2, 7) == 4
assert mod_inverse(1, 7) == 1
assert mod_inverse(6, 7) == 6 # 6 ≡ -1, নিজেই নিজের inverse
assert mod_inverse(10, 13) == 4
# মূল যাচাই: a × inverse ≡ 1 (mod p)
for a in range(1, 7):
inv = mod_inverse(a, 7)
assert (a * inv) % 7 == 1
# brute-এর সাথে মিল (ছোট prime):
for a in range(1, 13):
assert mod_inverse(a, 13) == inverse_brute(a, 13)
# বড় prime-এ inverse-এর সংজ্ঞা যাচাই:
P = 1000000007
assert (2 * mod_inverse(2, P)) % P == 1
assert (123456789 * mod_inverse(123456789, P)) % P == 1
print(mod_inverse(3, 7)) # 5
print(mod_inverse(2, 1000000007)) # 500000004
print((3 * mod_inverse(3, 7)) % 7) # 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
a %= p
if a == 0:
raise ValueError("0-এর inverse নেই")
return pow(a, p - 2, p)
```
প্রথমে `a`-কে ঘড়িতে নামাই। যদি `a % p == 0` (a, p-এর গুণিতক), inverse নেই — তাই error তুলি, নাহলে ভুল 0 ফেরত যেত। মূল লাইন `pow(a, p - 2, p)` — Fermat-এর `a^(p−2) mod p`, যা তিন-argument `pow`-এ fast power হয়ে O(log p)।
```text
for x in range(1, p):
if (a * x) % p == 1:
return x
```
`inverse_brute`-এ সংজ্ঞা সরাসরি: প্রতিটা `x`-এ `a × x ≡ 1` কিনা দেখি; পেলে সেটাই inverse। শুধু যাচাই আর বোঝার জন্য।
```text
for a in range(1, 7):
inv = mod_inverse(a, 7)
assert (a * inv) % 7 == 1
```
এই loop প্রতিটা a-র জন্য `a × inverse ≡ 1` নিশ্চিত করছে — inverse-এর সংজ্ঞাই যাচাই। বড় prime-এও একই (`2 × inv % P == 1`)। আর `inverse_brute`-এর সাথে মিলিয়ে দ্বিগুণ নিশ্চিত। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
5
500000004
1
সব test pass!
```
প্রথম লাইন `mod_inverse(3, 7)` → 5। দ্বিতীয় `mod_inverse(2, 1000000007)` → 500000004 (2-এর inverse mod 10⁹+7, কারণ `2 × 500000004 = 10⁹+8 ≡ 1`)। তৃতীয় `(3 × inverse) % 7` → 1 (সংজ্ঞা মিলে গেল)। আগের সব `assert` (সংজ্ঞা + brute মিল) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log p)** — `pow(a, p-2, p)` ভেতরে square-and-multiply, exponent (p−2)-এর binary-তে ~log₂(p) bit। `p = 10⁹+7`-এও ~30 ধাপ। brute force O(p) (~10⁹)-এর তুলনায় বিশাল লাফ।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — `pow`-এর iterative fast power শুধু গুটিকয় variable রাখে; কোনো list/array লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **non-prime mod-এ Fermat চালানো** — `a^(p−2)` শুধু `p` prime হলে inverse দেয়। `p = 10` হলে Fermat অচল; gcd(a,p)=1 হলে Extended GCD লাগবে, gcd≠1 হলে inverse-ই নেই।
- **`a % p == 0` ভুলে যাওয়া** — 0 বা p-এর গুণিতকের inverse নেই; না ধরলে `pow` 0 ফেরত দেবে, যা ভুল।
- **`pow(a, p-1, p)` লেখা** — এটা 1 দেয় (Fermat-ই বলে), inverse নয়! inverse-এর exponent `p−2`, `p−1` নয়।
- **`pow(a, p-2)` (mod ছাড়া)** — তিন-argument `pow(a, p-2, p)` ব্যবহার করো; mod বাদ দিলে আগে অতিকায় সংখ্যা বানিয়ে তারপর mod — অর্থহীন slow।
- **inverse-কে ভাগ ভাবা** — inverse মানে গুণের সঙ্গী (`a×x≡1`), সরাসরি `1/a` নয়; mod-জগতে ভগ্নাংশ নেই।
- **negative a** — `a %= p` আগে নিলে negative-ও ঠিক হয়; না নিলে ভুল।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **035 (Modular Division)** — inverse দিয়ে গুণ করেই mod-জগতে ভাগ; এই inverse-এর সরাসরি ব্যবহার।
- **034 (nCr mod Prime)** (