033 — Fermat Little Theorem¶
032-এ inverse বের করতে এই theorem-টা ব্যবহার করেছ, কিন্তু চোখে দেখোনি কেন সত্যি। এই note-এ Fermat's little theorem-কে হাতে-কলমে যাচাই করব —
a^(p−1) ≡ 1 (mod p)সত্যিই হয় কিনা ছোট prime-এ মিলিয়ে দেখব, আর কেন এটা cyclicity-রই আরেক রূপ সেটা বুঝব। এটা theorem-টার অন্তর্দৃষ্টি গড়ার note।
Source¶
- Original source: CP-Algorithms — module-inverse page (Fermat's little theorem অংশ)
- Platform: CP-Algorithms module-inverse page — https://cp-algorithms.com/algebra/module-inverse.html
- 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-এ যাচাই)
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 না হলে) সেটাও দেখব।
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)-কে ভাগ করে।
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 তাই যমজ।
4. Real-life analogy¶
ভাবো একটা বৃত্তাকার দৌড়ের ট্র্যাক, যাতে p ঘর (0 থেকে p−1)। তুমি শুরু করো ঘর 1-এ। প্রতি লাফে তুমি ঘর সংখ্যা a গুণ করো (mod p) — মানে এক ধরনের নির্দিষ্ট নিয়মে লাফাও।
Fermat বলে: prime ট্র্যাকে, এই লাফানো ঠিক (p−1) লাফে (বা তার ভাগে) আবার শুরুর ঘর 1-এ ফিরিয়ে আনে — কখনো ফাঁকি দেয় না, কখনো আটকে যায় না। যেন ট্র্যাকটা এমনভাবে বানানো যে নির্দিষ্টসংখ্যক লাফে তুমি বাড়ি ফিরবেই। prime না হলে ট্র্যাকে ফাটল — কোনো ঘর থেকে শুরু করলে আর বাড়ি ফেরা হয় না (theorem ভাঙে)।
5. Visual explanation¶
p = 5-এ সব a-র জন্য a^4 % 5 (p−1 = 4):
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:
6. Example input and output¶
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 একই সত্যের দুই মুখ।
7. Brute force thinking¶
theorem যাচাই সরাসরি: a-কে (p−1) বার গুণো (প্রতি step-এ mod), দেখো 1 হয় কিনা।
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-র লুপে এটা অচল।
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-এর সাথে মেলাও:
আর theorem-টা আসলে inverse-এর সাথে কীভাবে জড়িত সেটা দেখাতে — a^(p−1) = a × a^(p−2):
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 মুখস্থ করতে হয় না।
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 নয়):
12. Python solution¶
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¶
মূল যাচাই — a^(p−1) mod p (fast power) কি 1? prime p-তে সবসময় হ্যাঁ। এক লাইনেই পুরো theorem।
দেখায় theorem আর inverse একই: a^(p−2) হলো inverse, আর a × inverse = a^(p−1) ≡ 1। মানে 032-এর inverse এই theorem থেকেই জন্মায়।
এই দুই-স্তর loop একাধিক prime-এ, প্রতিটা non-multiple a-র জন্য theorem মিলিয়ে দেখছে — এটাই hands-on যাচাই। a সবসময় 1 থেকে p−1, তাই p-এর গুণিতক নয়।
composite p (=6)-এ theorem ভেঙে পড়া দেখাচ্ছে — 2^5 % 6 = 2 ≠ 1। এটাই বোঝায় কেন "p অবশ্যই prime"। সব ঠিক থাকলে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম লাইন 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!।
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 ছাড়া — তিন-argumentpow(a, p-1, p)ব্যবহার করো; নাহলে অতিকায় সংখ্যা।
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 (https://cses.fi/problemset/task/1712) — tower power-এ exponent mod (p−1) নেওয়া; Fermat-এর সরাসরি প্রয়োগ।
19. Pattern learned¶
Fermat's little theorem — p prime, gcd(a,p)=1 হলে a^(p−1) ≡ 1 (mod p)। এটাই cyclicity-র theorem-রূপ আর modular inverse-এর জন্ম (a^(p−2))। যাচাই: pow(a, p-1, p) == 1। composite mod-এ ভাঙে — তাই mod prime কিনা সবসময় দেখো।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "prime p-তে a^(p−1) ≡ 1 (a, p-এর গুণিতক না হলে) — power একটা চক্রে ঘুরে 1-এ ফেরে; এখান থেকেই inverse = a^(p−2)। theorem আর inverse একই সত্য। mod prime না হলে ভাঙে — তাই আগে prime যাচাই।"
পরের ধাপ → 034 — nCr mod Prime (factorial + inverse pipeline, এই theorem-এর মুকুট)। সম্পর্কিত → 032 — Modular Inverse Basic, 036 — Cyclic Remainder Pattern।
ফিরে দেখা: এই 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-তে নিত্য দরকারি" লেখা।