Skip to content

130 — Modular Inverse Advanced

Level 2-এ Fermat দিয়ে inverse শিখেছিলে — কিন্তু সেটা শুধু prime modulus-এ চলত। এই note-এ আমরা সেই সীমা ভেঙে যেকোনো coprime modulus-এ inverse বের করব, extended Euclid দিয়ে। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — তবে এর মধ্যে modular inverse আর fast exponentiation-এর চিন্তা interview-তেও মাঝে মাঝে কাজে লাগে। 125 (ext-Euclid) আর 032 (Fermat inverse) ঝালাই থাকলে এটা মসৃণ লাগবে।

Source

  • Original source: CP-Algorithms — Modular Multiplicative Inverse
  • Platform: CP-Algorithms — https://cp-algorithms.com/algebra/module-inverse.html
  • 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)

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।

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-এর সরাসরি ফসল।

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 পাশে)।

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) থাকে।

5. Visual explanation

3⁻¹ mod 10 বের করি — খেয়াল করো 10 prime নয়, তাই Fermat অচল, ext-gcd লাগবে:

চাই: 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-এ আনলাম।

6. Example input and output

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 পারত না।

7. Brute force thinking

inverse-এর সংজ্ঞা সরাসরি — 0 থেকে m−1 পর্যন্ত প্রতিটা x চেক করা, কোনটায় a·x % m == 1:

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) অচল:

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 সরাসরি দেয়। ধাপ:

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-ই একমাত্র সাধারণ পথ।

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।

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 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!।

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!।

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 নয়, নিজে লেখাই অভ্যাস।

18. Harder problems that inherit this idea

  • CSES — Exponentiation II / Binomial Coefficients (https://cses.fi/problemset/task/1079) — nCr mod p গুনতে factorial-এর inverse, যা সরাসরি এই inverse।
  • Codeforces — modular fraction / division problems (https://codeforces.com/problemset) — mod-জগতে "ভাগ" করতে inverse, প্রায়ই non-prime বা composite modulus।
  • 127 (CRT) — এই repo-রই সঙ্গী; CRT-র merge-এ m1⁻¹ mod m2 ঠিক এই inverse। আর 125 (ext-Euclid) এর ভিত্তি।

19. Pattern learned

Modular inverse via extended Euclid — a·x + m·y = 1 (coprime হলে) থেকে inverse = x % m; coprime না হলে inverse নেই। বড় শিক্ষা: mod-জগতে "ভাগ" মানে inverse দিয়ে গুণ — আর সেই inverse Fermat (prime m) বা ext-gcd (যেকোনো coprime m) থেকে আসে; কখন কোনটা, সেটাই আসল সিদ্ধান্ত।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "inverse mod m আছে ⟺ gcd(a,m)=1; ext-gcd-এর x % m-ই inverse (যেকোনো coprime m); m prime হলে Fermat a^(m−2)-ও চলে; Python-এ pow(a, -1, m)।" Signal: "mod-জগতে ভাগ করতে হবে" বা "1/a mod m" — দেখলেই এই inverse pattern মনে পড়বে।

পরের ধাপ → 131 — Matrix Exponentiation (binary expo-র matrix রূপ)। ভিত্তি → 125 — Extended Euclidean Algorithm, 032 (Fermat Inverse); সঙ্গী → 127 — CRT।

ফিরে দেখা: এই 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।