Problem link ও উৎস
- **Original source:** CP-Algorithms — module-inverse page (Fermat's little theorem অংশ)
- **Platform:** CP-Algorithms module-inverse page —
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Medium
- **Pattern:** a^(p−1) ≡ 1 (Fermat's little theorem)
- **Basic idea inherited from:** 029 — Modular Exponentiation (a^(p−1) fast power-এ যাচাই)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **prime** `p` আর একটা সংখ্যা `a` (যেন `p`-এর গুণিতক না হয়) দেওয়া। যাচাই করতে হবে Fermat's little theorem:
`a^(p−1) % p == 1`
মানে: prime `p`-এর জন্য, যেকোনো non-multiple `a`-কে `(p−1)` বার নিজে দিয়ে গুণ করলে ঘড়িতে ঠিক **1**-এ ফিরে আসে। আমরা এটা ছোট prime-এ সব `a`-র জন্য মিলিয়ে দেখব, আর কোথায় এটা **ভেঙে পড়ে** (p prime না হলে) সেটাও দেখব।
### Input ও output {#6-example-input-and-output}
```text
a p (prime) -> a^(p-1) % p theorem ঠিক?
----------------------------------------------------
2 5 -> 1 হ্যাঁ
3 7 -> 1 হ্যাঁ
10 13 -> 1 হ্যাঁ
2 1000000007 -> 1 হ্যাঁ (বড় prime-এও)
ভাঙার কেস (p prime নয়):
a p -> a^(p-1) % p theorem ঠিক?
----------------------------------------------------
2 6 -> 2 না (6 composite)
3 8 -> ... সাধারণত না
```
inverse-এর সাথে যোগসূত্র: যেহেতু `a × a^(p−2) ≡ 1`, তাই `a^(p−1) = a × a^(p−2) ≡ a × inverse(a) ≡ 1` — এই note আর 032 একই সত্যের দুই মুখ।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **বৃত্তাকার দৌড়ের ট্র্যাক**, যাতে `p` ঘর (0 থেকে p−1)। তুমি শুরু করো ঘর 1-এ। প্রতি লাফে তুমি ঘর সংখ্যা `a` গুণ করো (mod p) — মানে এক ধরনের নির্দিষ্ট নিয়মে লাফাও।
Fermat বলে: prime ট্র্যাকে, এই লাফানো ঠিক `(p−1)` লাফে (বা তার ভাগে) আবার শুরুর ঘর 1-এ ফিরিয়ে আনে — কখনো ফাঁকি দেয় না, কখনো আটকে যায় না। যেন ট্র্যাকটা এমনভাবে বানানো যে নির্দিষ্টসংখ্যক লাফে তুমি বাড়ি ফিরবেই। prime না হলে ট্র্যাকে ফাটল — কোনো ঘর থেকে শুরু করলে আর বাড়ি ফেরা হয় না (theorem ভাঙে)।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **029 — Modular Exponentiation** থেকে। `a^(p−1) mod p` যাচাই করতে fast power লাগে (`p` বড় হলে exponent বিশাল)। 029 না থাকলে এই power বের করাই কঠিন।
আর concept-notes-এর **cyclicity** (section 5: last digit চক্র) এর গভীর রূপ এটা — সেখানে দেখেছ power-এর remainder ঘুরে ঘুরে ফেরে; Fermat বলে prime mod-এ সেই চক্রের দৈর্ঘ্য সবসময় `(p−1)`-কে ভাগ করে, তাই `a^(p−1)` ঠিক 1। 036 (cyclic pattern) আর এই note তাই যমজ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **Fermat's little theorem**:
`a^(p−1) ≡ 1 (mod p)`, যখন `p` prime আর `gcd(a, p) = 1`
কেন? একটা সুন্দর যুক্তি: prime `p`-তে `a`-এর গুণফলের সারি `{a×1, a×2, ..., a×(p−1)} mod p` আসলে `{1, 2, ..., p−1}`-এরই একটা reshuffle (কারণ a invertible, কোনো দুটো একই ঘরে পড়ে না)। দুই সেটের গুণফল সমান:
`a^(p−1) × (1×2×...×(p−1)) ≡ (1×2×...×(p−1)) (mod p)`
দুই পাশের `(p−1)!` কাটাকাটি (এটা invertible) → `a^(p−1) ≡ 1`। এটাই section 5-এর cyclicity-র theorem-রূপ: power একসময় 1-এ ফেরে, আর prime-এ সেই চক্র `(p−1)`-কে ভাগ করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
theorem যাচাই সরাসরি: `a`-কে `(p−1)` বার গুণো (প্রতি step-এ mod), দেখো 1 হয় কিনা।
```python
def fermat_check_brute(a, p):
result = 1
for _ in range(p - 1):
result = result * a % p # p-1 বার গুণ
return result == 1
```
ছোট prime-এ স্পষ্ট আর সঠিক। সমস্যা শুধু — loop চলে p−1 বার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে p−1 বার। `p = 10⁹+7` হলে প্রায় 1 বিলিয়ন গুণ — একটা যাচাইয়েই সেকেন্ড গড়ায়। অনেক `a`-র জন্য বা CP-র লুপে এটা অচল।
```text
p = 10^9+7 হলে:
brute (O(p)): ~10^9 বার গুণ -> সেকেন্ড লাগে
fast power (O(log p)): ~30 বার গুণ -> ঝটপট
```
মূল শিক্ষা: `(p−1)` বার এক এক গুণ না করে, 029-এর square-and-multiply দিয়ে `a^(p−1)` সরাসরি O(log p)-তে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
fast power দিয়ে `a^(p−1) mod p` বের করে 1-এর সাথে মেলাও:
```python
def fermat_check(a, p):
return pow(a, p - 1, p) == 1
```
আর theorem-টা আসলে inverse-এর সাথে কীভাবে জড়িত সেটা দেখাতে — `a^(p−1) = a × a^(p−2)`:
```python
def fermat_via_inverse(a, p):
inv = pow(a, p - 2, p) # 032-এর Fermat inverse
return (a * inv) % p == 1 # a × a^(p-2) = a^(p-1) ≡ 1
```
দুটোই O(log p)। প্রথমটা সরাসরি theorem, দ্বিতীয়টা দেখায় কেন inverse = `a^(p−2)`।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **prime mod-এ power একটা বদ্ধ চক্রে ঘোরে যেটা ঠিক `(p−1)`-এ (বা তার ভাগে) 1-এ ফেরে — তাই `a^(p−1)` সবসময় 1।** এটাই 036-এর last-digit cyclicity-র সাধারণ রূপ, শুধু mod 10-এর জায়গায় mod p।
সবচেয়ে দামি tweak: এই 1-এ-ফেরা থেকেই inverse আসে — `a × a^(p−2) ≡ 1` মানে `a^(p−2)` হলো inverse। তাই Fermat little theorem আর modular inverse আলাদা দুটো জিনিস নয়, **একই সত্য**। theorem বুঝলে inverse মুখস্থ করতে হয় না।
### ছবিতে বোঝা {#5-visual-explanation}
`p = 5`-এ সব `a`-র জন্য `a^4 % 5` (p−1 = 4):
```text
a a^(p-1) = a^4 a^4 % 5
------------------------------------
1 1 1
2 16 1 <- 16 = 5×3 + 1
3 81 1 <- 81 = 5×16 + 1
4 256 1 <- 256 = 5×51 + 1
^^^
সবাই 1-এ ফেরে — Fermat সত্যি!
```
কোথায় ভাঙে — `p = 6` (prime নয়), `a = 2`:
```text
2^(6-1) = 2^5 = 32 -> 32 % 6 = 2 (1 নয়!)
^
6 prime না, তাই Fermat অচল — theorem ভেঙে গেল
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`fermat_check(3, 7)` = `3^6 % 7 == 1?`, fast power-এ (6 = 110₂):
| step | b (binary) | last bit | result | a (square হয়ে) |
| --- | --- | --- | --- | --- |
| শুরু | 110 | — | 1 | 3 % 7 = 3 |
| 1 | 110 | 0 | 1 | 3×3 % 7 = 2 |
| 2 | 11 | 1 | 1×2 % 7 = 2 | 2×2 % 7 = 4 |
| 3 | 1 | 1 | 2×4 % 7 = 1 | 4×4 % 7 = 2 |
`b` এখন 0, `3^6 % 7 = 1` ✓ — theorem মিলল! Check সরাসরি: 3^6 = 729 = 7×104 + 1, তাই `729 % 7 = 1` ✓।
এবার ভাঙার dry run `2^5 % 6` (p=6 prime নয়):
```text
2^5 = 32, 32 % 6 = 2 (1 নয়) -> Fermat ভেঙে গেল, কারণ 6 composite
```
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def fermat_check(a, p):
"""Fermat যাচাই: a^(p-1) % p == 1 (p prime, a % p != 0 ধরে)।"""
return pow(a, p - 1, p) == 1
def fermat_via_inverse(a, p):
"""একই theorem inverse দিয়ে: a × a^(p-2) = a^(p-1) ≡ 1।"""
inv = pow(a, p - 2, p)
return (a * inv) % p == 1
def is_prime(n):
"""ছোট helper — যাচাইয়ের জন্য prime চেক।"""
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
# --- theorem ঠিক হওয়া উচিত সব prime-এ, সব non-multiple a-র জন্য ---
for p in [2, 3, 5, 7, 11, 13, 97]:
for a in range(1, p): # a কখনো p-এর গুণিতক নয় এখানে
assert pow(a, p - 1, p) == 1 # Fermat সত্যি
assert fermat_check(a, p) is True
assert fermat_via_inverse(a, p) is True # inverse-রূপও মেলে
# বড় prime-এ:
P = 1000000007
assert fermat_check(2, P) is True
assert fermat_check(123456789, P) is True
# ভাঙার কেস: p composite হলে অন্তত কিছু a-তে theorem ফেল করবে
def some_fail(p):
return any(pow(a, p - 1, p) != 1 for a in range(2, p) if is_prime(p) is False)
assert pow(2, 5, 6) == 2 # 6 composite -> 1 নয়
assert fermat_check(2, 6) is False # ভেঙে গেল
assert some_fail(6) is True # composite-এ ফেল আছে
print(fermat_check(3, 7)) # True
print(pow(3, 6, 7)) # 1
print(fermat_check(2, 6)) # False (6 prime নয়)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def fermat_check(a, p):
return pow(a, p - 1, p) == 1
```
মূল যাচাই — `a^(p−1) mod p` (fast power) কি 1? prime p-তে সবসময় হ্যাঁ। এক লাইনেই পুরো theorem।
```text
def fermat_via_inverse(a, p):
inv = pow(a, p - 2, p)
return (a * inv) % p == 1
```
দেখায় theorem আর inverse একই: `a^(p−2)` হলো inverse, আর `a × inverse = a^(p−1) ≡ 1`। মানে 032-এর inverse এই theorem থেকেই জন্মায়।
```text
for p in [2, 3, 5, 7, 11, 13, 97]:
for a in range(1, p):
assert pow(a, p - 1, p) == 1
```
এই দুই-স্তর loop **একাধিক prime-এ, প্রতিটা non-multiple a-র জন্য** theorem মিলিয়ে দেখছে — এটাই hands-on যাচাই। `a` সবসময় 1 থেকে p−1, তাই p-এর গুণিতক নয়।
```text
assert pow(2, 5, 6) == 2
assert fermat_check(2, 6) is False
```
composite p (=6)-এ theorem ভেঙে পড়া দেখাচ্ছে — `2^5 % 6 = 2 ≠ 1`। এটাই বোঝায় কেন "p অবশ্যই prime"। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
True
1
False
সব test pass!
```
প্রথম লাইন `fermat_check(3, 7)` → True (3^6 ≡ 1 mod 7)। দ্বিতীয় `pow(3, 6, 7)` → 1 (সেই power-ই)। তৃতীয় `fermat_check(2, 6)` → False (6 prime নয়, তাই theorem ভাঙে)। আগের সব `assert` (একাধিক prime + composite-ভাঙা সহ) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log p)** প্রতি যাচাই — `pow(a, p-1, p)` square-and-multiply, exponent (p−1)-এর ~log₂(p) bit। brute force O(p)-এর তুলনায় বিশাল লাফ। (test-এ ছোট prime-এর double loop O(p) ঘুরছে যাচাইয়ের জন্য, কিন্তু মূল check নিজে O(log p)।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — `pow` iterative, শুধু গুটিকয় variable। কোনো list/array লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **`a` যদি `p`-এর গুণিতক** — তখন `a ≡ 0`, আর `0^(p−1) ≡ 0 ≠ 1`; Fermat-এর শর্ত `gcd(a, p) = 1` ভাঙে। theorem শুধু non-multiple a-তে।
- **p prime না ধরে চালানো** — composite p-তে theorem সাধারণত ভাঙে (যেমন `2^5 % 6 = 2`); inverse/nCr-এ এটা ভুল উত্তরের উৎস।
- **`a^p ≡ a` রূপ গুলিয়ে ফেলা** — Fermat-এর আরেক রূপ `a^p ≡ a (mod p)` সব a-তে (গুণিতক সহ) সত্যি; কিন্তু `a^(p−1) ≡ 1` শুধু non-multiple a-তে। দুটো মিলিয়ে ফেলো না।
- **exponent `p` বনাম `p−1`** — `a^(p−1)` দেয় 1, `a^p` দেয় a। ভুল exponent → ভুল উপসংহার।
- **`pow(a, p-1)` mod ছাড়া** — তিন-argument `pow(a, p-1, p)` ব্যবহার করো; নাহলে অতিকায় সংখ্যা।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **032 (Modular Inverse Basic)** + **035 (Modular Division)** — দুটোই সরাসরি এই theorem থেকে inverse নেয়।
- **Fermat primality test** — এই theorem উল্টে ব্যবহার করে সম্ভাব্য prime চেনা (`a^(n−1) % n != 1` হলে n নিশ্চিত composite); Miller-Rabin-এর ভিত। (Carmichael সংখ্যা-র ব্যতিক্রম জেনে রাখো।)
- **CSES — Exponentiation II** (