Problem link ও উৎস
- **Original source:** CP-Algorithms — Modular Multiplicative Inverse
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Medium
- **Pattern:** ext-gcd inverse
- **Basic idea inherited from:** 125 (Extended Euclidean Algorithm), 032 (Fermat Inverse)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো integer `a` আর `m` দেওয়া আছে। বের করতে হবে `a`-এর **modular inverse** mod `m` — মানে এমন একটা সংখ্যা `x` (0 থেকে m−1-এর মধ্যে), যাতে:
```
a · x ≡ 1 (mod m) (a·x কে m দিয়ে ভাগ করলে ভাগশেষ 1)
```
এটা যেন mod-জগতে "ভাগ করা" — সাধারণ গণিতে `1/a`-এর বদলে এখানে `x`। কিন্তু একটা শর্ত: **inverse থাকে ঠিক তখনই যখন `gcd(a, m) = 1`** (a আর m coprime)। নাহলে inverse-এর অস্তিত্বই নেই।
Level 2-এর Fermat পদ্ধতি (`a^(m−2) mod m`) শুধু **prime m**-এ চলত। এবার আমরা general রাস্তা শিখব — extended Euclid, যা coprime হলেই চলে, m prime হোক বা না হোক। মনে রেখো — এই level CP-leaning, interview-optional, তবে এই inverse-চিন্তাটা সবচেয়ে বেশি reusable।
### Input ও output {#6-example-input-and-output}
```text
input (a, m) -> inverse যাচাই (a·inv mod m)
----------------------------------------------------------------
3, 10 -> 7 3·7 = 21 ≡ 1 (mod 10) ✓ (m না prime!)
3, 11 -> 4 3·4 = 12 ≡ 1 (mod 11) ✓ (m prime, Fermat-ও চলত)
7, 26 -> 15 7·15 = 105 ≡ 1 (mod 26) ✓
10, 17 -> 12 10·12 = 120 ≡ 1 (mod 17) ✓
2, 4 -> None gcd(2,4)=2 ≠ 1 -> inverse নেই
6, 9 -> None gcd(6,9)=3 ≠ 1 -> inverse নেই
1, 13 -> 1 1·1 ≡ 1 সবসময়
```
খেয়াল করো: **gcd(a, m) ≠ 1 হলে inverse নেই** → None (যেমন (2, 4), (6, 9)) — এটাই সবচেয়ে গুরুত্বপূর্ণ edge case। আর m prime না হলেও (যেমন 10, 26) coprime হলে ext-gcd ঠিক inverse দেয়, যেখানে Fermat পারত না।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা বৃত্তাকার ঘড়ি যার `m` ঘর (mod m মানে m-ঘরের ঘড়ি)। তুমি প্রতি ধাপে `a` ঘর করে সামনে এগোও। প্রশ্ন: **ঠিক কত ধাপ (x) এগোলে তুমি ঠিক 1 ঘর সরে আছ** (a·x ≡ 1)?
- যদি a আর m-এর "তাল মেলে" (coprime), তাহলে a-ঘর করে লাফাতে লাফাতে তুমি ঘড়ির সব ঘর একে একে ছুঁয়ে ফেলবে — তাই 1 ঘরেও ঠিক একবার পৌঁছাবে। সেই ধাপসংখ্যাই inverse।
- কিন্তু যদি a আর m-এর সাধারণ গুণনীয়ক থাকে (যেমন a = 4, m = 6), তাহলে তুমি শুধু কিছু নির্দিষ্ট ঘরেই (0, 2, 4) ঘুরবে, কখনো 1-এ পৌঁছাবে না — **inverse নেই**।
তাই coprime মানে "ঘড়ির সব ঘর ছোঁয়া যায়", আর তখনই 1-এ পৌঁছানোর একটা ধাপসংখ্যা (inverse) থাকে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দুটো শিকড়:
- **125 (Extended Euclidean Algorithm)** — মূল ইঞ্জিন। `a·x + m·y = 1` থেকে x-ই inverse। 125 না বুঝলে এই general পদ্ধতি বোঝা যায় না।
- **032 (Fermat Inverse)** — পুরোনো, সীমিত পদ্ধতি (prime m-এ `a^(m−2)`)। 130 দেখায় কখন Fermat যথেষ্ট আর কখন ext-gcd লাগে।
আর এর উপরে দাঁড়িয়ে আছে **127 (CRT)** — CRT-র merge-এ `m1⁻¹ mod m2` লাগে, যা ঠিক এই inverse। তাই README-র শিকড়-শৃঙ্খলে: 125 → 130 (আর 032 পাশে)।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **inverse আসে extended Euclid থেকে**। coprime হলে (gcd = 1) ext-gcd দেয় x, y যাতে:
```
a·x + m·y = gcd(a, m) = 1
```
এখন দুপাশে mod m নিই — `m·y` অংশটা m-এর গুণিতক, তাই mod m-এ অদৃশ্য:
```
a·x ≡ 1 (mod m)
```
মানে সেই `x`-ই হলো a-এর inverse! শুধু শেষে `x % m` দিয়ে 0..m−1-এ এনে দিই। দুই পথের তুলনা: **Fermat** (`a^(m−2) mod m`) ছোট, মুখস্থ-সহজ, কিন্তু **শুধু prime m**-এ; **ext-gcd** সর্বত্রগামী, যেকোনো coprime m-এ। এই level CP-leaning হলেও idea-টা 125-এর সরাসরি ফসল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
inverse-এর সংজ্ঞা সরাসরি — **0 থেকে m−1 পর্যন্ত প্রতিটা x চেক করা**, কোনটায় `a·x % m == 1`:
```python
def mod_inverse_brute(a, m):
a %= m
for x in range(m):
if (a * x) % m == 1:
return x
return None # কোনো x নেই -> inverse নেই
```
ছোট m-এ (যেমন 10) এটা সহজেই 7 খুঁজে দেয়, আর inverse না থাকলে loop শেষে None দেয়। সংজ্ঞা থেকে একদম পরিষ্কার — শুরুর জন্য আদর্শ, আর cross-check-এ কাজে লাগবে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে ঠিক `m` বার। ছোট m-এ কিছুই না, কিন্তু m বড় হলে (CP-তে m প্রায়ই 10⁹+7) অচল:
```text
m ছোট (10): 10 বার — তাৎক্ষণিক
m = 10⁹ + 7: ~10⁹ বার loop — কয়েক সেকেন্ড থেকে মিনিট, TLE
ext-gcd: O(log m) — মুহূর্তে
Fermat (prime m): O(log m) — fast power
```
বড় m-এ brute force কার্যত অচল। অথচ ext-gcd মাত্র log m ধাপে (Euclid-এর সিঁড়ি) সরাসরি x দেয় — তাই m যত বড়ই হোক, প্রায় তাৎক্ষণিক।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **inverse খুঁজতে হয় না, extended Euclid সরাসরি দেয়।** ধাপ:
```text
1. g, x, y = ext_gcd(a, m) [a·x + m·y = g]
2. যদি g ≠ 1: inverse নেই (coprime না) -> None
3. নাহলে: inverse = x % m [a·x ≡ 1 (mod m)]
```
কেন কাজ করে: `a·x + m·y = 1`-এ mod m নিলে `m·y` অদৃশ্য, থাকে `a·x ≡ 1`। তাই x-ই inverse, শুধু `% m` দিয়ে range-এ আনি।
বিকল্প — **m prime হলে Fermat:** `a^(m−2) mod m` (fast power-এ, 029-এর binary exponentiation)। দুটোই O(log m); Fermat কোড ছোট কিন্তু prime-বন্দি, ext-gcd সর্বত্রগামী। আর Python-এ একটা bonus — `pow(a, -1, m)` সরাসরি inverse দেয় (3.8+), যা শেখার পর পুরস্কার হিসেবে ব্যবহার করা যায়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **`a·x + m·y = 1`-এ mod m নিলে m-এর অংশ মুছে যায় — তাই ext-gcd-এর x-ই সরাসরি inverse।**
brute force পুরো 0..m−1 চষছিল; tweak হলো — Euclid-এর সিঁড়ি বেয়ে `a·x + m·y = 1` বানাও, তারপর mod m নিয়ে m·y অংশটা ফেলে দাও। O(m) থেকে O(log m)-এ নেমে এল। আর দ্বিতীয় tweak: কখন কোন পথ — m prime হলে Fermat ছোট ও যথেষ্ট, m যেকোনো coprime হলে ext-gcd-ই একমাত্র সাধারণ পথ।
### ছবিতে বোঝা {#5-visual-explanation}
`3⁻¹ mod 10` বের করি — খেয়াল করো 10 prime নয়, তাই Fermat অচল, ext-gcd লাগবে:
```text
চাই: 3·x ≡ 1 (mod 10)
extended Euclid (3, 10):
10 = 3·3 + 1
3 = 1·3 + 0 -> gcd = 1 (coprime, তাই inverse আছে)
back-sub: 1 = 10 − 3·3
⇒ 3·(−3) + 10·(1) = 1
x = −3, y = 1
mod m নিই: 3·(−3) ≡ 1 (mod 10)
normalize: −3 % 10 = 7
যাচাই: 3·7 = 21 = 2·10 + 1 ≡ 1 (mod 10) ✓
inverse = 7
```
লক্ষ করো — 10 prime না হওয়ায় Fermat (`3^8 mod 10`) ভুল উত্তর দিত, কিন্তু ext-gcd ঠিক 7 দিল। আর সব congruence-এর মতো শেষে `% 10` দিয়ে negative-কে positive-এ আনলাম।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`mod_inverse(3, 10)` — ext-gcd দিয়ে:
| step | কী করছি | মান |
| --- | --- | --- |
| 1 | g, x, y = ext_gcd(3, 10) | দেখি নিচে |
| | ext_gcd(3, 10): 3%10... আসলে ext_gcd(10, 3)-এর মতো নামবে; ফল | g = 1, x = −3, y = 1 |
| 2 | g == 1? | হ্যাঁ → inverse আছে |
| 3 | inverse = x % m = −3 % 10 | 7 |
| 4 | যাচাই: 3·7 % 10 = 21 % 10 | 1 ✓ |
চূড়ান্ত: **7**। আর যদি `mod_inverse(2, 4)` দিতাম:
| step | কী করছি | মান |
| --- | --- | --- |
| 1 | g, x, y = ext_gcd(2, 4) | g = 2, x = 1, y = 0 |
| 2 | g == 1? | না (g = 2) → coprime নয় |
| 3 | return None | inverse নেই |
দেখো — coprime হলে x % m দিয়ে inverse, না হলে সোজা None।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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 mod_inverse(a, m):
"""a-এর inverse mod m (ext-gcd) — coprime না হলে None।"""
a %= m
g, x, _ = ext_gcd(a, m)
if g != 1:
return None # gcd(a, m) ≠ 1 -> inverse নেই
return x % m
def mod_inverse_fermat(a, p):
"""prime p হলে Fermat দিয়ে inverse: a^(p−2) mod p (032 থেকে)।"""
return pow(a, p - 2, p) # শুধু p prime হলে বৈধ
# --- ছোট test গুলো (সব pass করা উচিত) ---
from math import gcd
def mod_inverse_brute(a, m):
a %= m
for x in range(m):
if (a * x) % m == 1:
return x
return None
# ext-gcd version vs brute force — অনেক জোড়ায় মেলাও
for m in range(2, 60):
for a in range(1, m):
inv = mod_inverse(a, m)
if gcd(a, m) == 1:
assert inv is not None, f"inverse থাকার কথা: {a} mod {m}"
assert (a * inv) % m == 1, f"inverse ভুল: {a} mod {m} -> {inv}"
assert inv == mod_inverse_brute(a, m), f"brute অমিল: {a} mod {m}"
else:
assert inv is None, f"inverse থাকার কথা না: {a} mod {m}"
# non-prime modulus-এ ext-gcd সঠিক (Fermat যেখানে fail করত)
assert mod_inverse(3, 10) == 7
assert mod_inverse(7, 26) == 15
assert mod_inverse(10, 17) == 12
# prime modulus-এ Fermat আর ext-gcd একই উত্তর
for p in (11, 13, 17, 1000000007):
for a in (2, 3, 5, 123):
assert mod_inverse(a, p) == mod_inverse_fermat(a, p) % p
# Python built-in pow(a, -1, m)-এর সাথেও মিল
assert mod_inverse(3, 10) == pow(3, -1, 10)
assert mod_inverse(123, 1000000007) == pow(123, -1, 1000000007)
print(mod_inverse(3, 10)) # 7 (m prime নয়!)
print(mod_inverse(3, 11)) # 4
print(mod_inverse(2, 4)) # None
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def mod_inverse(a, m):
a %= m
g, x, _ = ext_gcd(a, m)
```
আগে `a %= m` দিয়ে a-কে range-এ আনি (বড় বা negative a সামলাতে)। তারপর ext-gcd থেকে g = gcd আর x পাই, যেখানে `a·x + m·y = g`।
```
if g != 1:
return None
return x % m
```
g যদি 1 না হয়, a আর m coprime নয় — inverse-এর অস্তিত্বই নেই, None। নাহলে x-ই inverse, শুধু `% m` দিয়ে 0..m−1-এ এনে দিই (x negative হতে পারে)।
```
def mod_inverse_fermat(a, p):
return pow(a, p - 2, p)
```
Fermat's little theorem: prime p-তে `a^(p−1) ≡ 1`, তাই `a^(p−2) ≡ a⁻¹`। `pow(a, p-2, p)` fast modular exponentiation (029)। **সতর্কতা:** এটা শুধু p prime হলে বৈধ — composite m-এ ভুল দেবে।
```
def mod_inverse_brute(a, m):
...
if (a * x) % m == 1: return x
```
সংজ্ঞা থেকে সরাসরি — cross-check-এর জন্য; বড় m-এ ধীর, কিন্তু সঠিক।
বাকি test অংশে 2..60 modulus-এর সব a-এর জন্য ext-gcd বনাম brute মেলানো হয়, non-prime ও prime modulus আলাদাভাবে যাচাই হয়, আর Python-এর `pow(a, -1, m)`-এর সাথেও মিল দেখা হয়। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
7
4
None
সব test pass!
```
`mod_inverse(3, 10)` → 7 (m = 10 prime নয়, তবু coprime, তাই ext-gcd কাজ করল; `3·7 ≡ 1 mod 10`)। `mod_inverse(3, 11)` → 4 (`3·4 = 12 ≡ 1 mod 11`)। `mod_inverse(2, 4)` → None (gcd 2, inverse নেই)। তার আগে শত শত জোড়ায় brute, Fermat, ও built-in pow-এর সাথে মিল — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log m)** — পুরো খরচ extended Euclid-এর (Euclid-এর সিঁড়ি)। Fermat version-ও O(log m) (fast power, ~log m গুণ)। brute force-এর O(m)-এর তুলনায় বিশাল লাফ। তাই m = 10⁹ + 7-এও inverse তাৎক্ষণিক।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(log m)** recursive ext_gcd-এর call stack-এর জন্য; iterative ext_gcd নিলে **O(1)**। Fermat version O(1) (pow in-place)। কোনো বড় array লাগে না — শুধু গুটিকয় variable।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **gcd(a, m) ≠ 1 ধরা না** — সবচেয়ে কমন। coprime না হলে inverse **নেই**; g ≠ 1 চেক বাদ দিলে অর্থহীন উত্তর। আগে g যাচাই করো।
2. **composite m-এ Fermat চালানো** — Fermat (`a^(m−2)`) শুধু **prime m**-এ বৈধ; 10 বা 26-এর মতো composite-এ ভুল। তখন ext-gcd লাগবেই।
3. **x negative রেখে দেওয়া** — ext-gcd-এর x negative হতে পারে; `% m` দিয়ে 0..m−1-এ না আনলে ভুল উত্তর।
4. **`a %= m` না করা** — বড় বা negative a সরাসরি দিলে কিছু implementation-এ গণ্ডগোল; আগে range-এ আনা নিরাপদ।
5. **`pow(a, -1, m)` সব Python-এ ভাবা** — এটা Python 3.8+; পুরোনো version-এ নিজে ext-gcd লিখতে হবে। আর শেখার পর্বে built-in নয়, নিজে লেখাই অভ্যাস।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Exponentiation II / Binomial Coefficients** (