032 — Modular Inverse Basic¶

mod-এর জগতে ভাগ নেই — কিন্তু "ভাগের বদলি" আছে: modular inverse। ঠিক যেমন সাধারণ গণিতে "5 দিয়ে ভাগ" মানে "1/5 দিয়ে গুণ", mod-জগতেও a-এর একটা সঙ্গী আছে যাকে দিয়ে গুণ করলে 1 হয়। এই note-এ Fermat-এর little theorem দিয়ে সেই সঙ্গী খুঁজব — a^(p−2) mod p।

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 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))

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-এ দেখবে)।

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)-তে।

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 বের করাই অসম্ভব হতো।

4. Real-life analogy¶

ভাবো একটা তালা-চাবি। a একটা তালা। তুমি এমন একটা চাবি x খুঁজছ, যেটা ঘোরালে তালা ঠিক "শুরুর অবস্থানে" (1-এ) ফিরে আসে।

সাধারণ গণিতে এই চাবি হলো 1/a — গুণ করলে 1। কিন্তু mod-জগতে ভগ্নাংশ নেই, তাই চাবিটা একটা পূর্ণসংখ্যা হতে হবে। Fermat বলে দেয়: সেই চাবি হলো a-কে (p−2) বার নিজে দিয়ে গুণ করলে যা পাও (mod p)। অদ্ভুত শোনালেও — গুণ করে মিলিয়ে দেখো, ঠিক 1 হয়। ঘড়ির গণিতের এই চাবি-বানানোই modular inverse।

5. Visual explanation¶

mod 7-এ 3-এর সব গুণফল দেখো — কোথায় 1 হয়:

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):

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 ✓

6. Example input and output¶

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 হয় না)।

7. Brute force thinking¶

inverse-এর সংজ্ঞা সরাসরি ব্যবহার করো: 1 থেকে p−1 পর্যন্ত প্রতিটা x চেষ্টা করো, যেটায় (a × x) % p == 1 সেটাই inverse।

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 লাগে — সম্পূর্ণ অসম্ভব।

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 দিয়ে এক ধাপে:

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):

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?"

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। দুই পথে একই উত্তর।

12. Python solution¶

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¶

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

    for x in range(1, p):
        if (a * x) % p == 1:
            return x

inverse_brute-এ সংজ্ঞা সরাসরি: প্রতিটা x-এ a × x ≡ 1 কিনা দেখি; পেলে সেটাই inverse। শুধু যাচাই আর বোঝার জন্য।

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

14. Output walkthrough¶

চালালে যা ছাপবে:

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

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-ও ঠিক হয়; না নিলে ভুল।

18. Harder problems that inherit this idea¶

035 (Modular Division) — inverse দিয়ে গুণ করেই mod-জগতে ভাগ; এই inverse-এর সরাসরি ব্যবহার।
034 (nCr mod Prime) (https://cp-algorithms.com/combinatorics/binomial-coefficients.html) — factorial-এর inverse লাগে; এই Fermat inverse ছাড়া অচল।
CSES — Binomial Coefficients / Exponentiation II (https://cses.fi/problemset/task/1079) — সরাসরি inverse + fast power-এর প্রয়োগ; CP-Algorithms-এর module-inverse page-এ Extended GCD রূপও দেখো (non-prime mod-এর জন্য)।

19. Pattern learned¶

Fermat modular inverse — p prime হলে a⁻¹ ≡ a^(p−2) (mod p), fast power-এ O(log p)। সংজ্ঞা: a × a⁻¹ ≡ 1। mod prime কিনা আগে দেখো; না হলে Extended GCD। এটাই mod-জগতে ভাগের চাবি।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "mod prime p-তে inverse = pow(a, p-2, p) (Fermat: a^(p−1)≡1 থেকে এক a খুলে)। সবসময় a × inv % p == 1 দিয়ে মিলিয়ে নাও। 'mod-এ ভাগ লাগছে' দেখলেই inverse মনে পড়ুক — আর mod prime কিনা যাচাই করো।"

পরের ধাপ → 033 — Fermat Little Theorem (যে theorem এই inverse-এর ভিত)। সম্পর্কিত → 029 — Modular Exponentiation, 035 — Modular Division।

ফিরে দেখা: এই 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-তে নিত্য দরকারি" লেখা।