# Level 10 — Advanced Number Theory (সংখ্যাতত্ত্বের গভীরে)

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> ⚠️ **আগে পড়ো:** এই level (আর level 11) big-tech **interview-এর জন্য optional** — interview-তে extended Euclid বা Miller-Rabin প্রায় আসে না। এগুলো **competitive programming-এর জন্য deep** material। তাই চাইলে এখন skip করে মূল DS topic গুলোতে (02-13) চলে যাও, সেগুলো শেষ করার পরেও এখানে ফিরে আসা যায় — কিছুই হারাবে না। আর CP-তে আগ্রহ থাকলে — স্বাগতম, এখানে সংখ্যার সবচেয়ে সুন্দর গল্পগুলো অপেক্ষা করছে।

## এই level এ কী শিখবে?

Level 1-2-তে gcd, mod, prime-এর হাতেখড়ি হয়েছিল। এবার সেই hatiyar গুলোকে শান দেওয়ার পালা — শুধু "gcd কত" নয়, "gcd-টা **কীভাবে বানানো হলো**" (extended Euclid); শুধু "prime কি না" নয়, "10¹⁸ পর্যন্ত সংখ্যায় কয়েক microsecond-এ prime check" (Miller-Rabin)।

মূল idea গুলো:

- **Extended Euclid** — `ax + by = gcd(a, b)`-এর x, y খুঁজে বের করা; Euclid-এর সিঁড়ি বেয়ে নিচে নেমে back-substitution-এ উপরে ওঠা
- **Linear Diophantine** — `ax + by = c` solvable ⟺ `gcd(a, b) | c`; এক solution থেকে অসীম solution-এর পরিবার
- **CRT (Chinese Remainder Theorem)** — দুটো আলাদা ঘড়ির reading মিলিয়ে আসল সময় বের করা; modulus merge
- **Totient advanced** — φ multiplicative; prime factorization থেকে এক লাইনে φ(n)
- **Mobius function (μ)** — inclusion-exclusion-কে একটা function-এ encode করা; "ঠিক gcd 1" ঘরানার গোনায় জাদু
- **Modular inverse (general)** — prime modulus না হলেও ext-gcd দিয়ে inverse, যতক্ষণ `gcd(a, m) = 1`
- **Matrix exponentiation** — recurrence-কে matrix-এ বদলে binary exponentiation; Fibonacci-র n-তম পদ O(log n)-এ
- **Fast doubling** — Fibonacci-র জন্য matrix-এরও shortcut: F(2k)-এর সরাসরি formula
- **Miller-Rabin** — probabilistic primality test; 64-bit-এর জন্য নির্দিষ্ট base-এ deterministic
- **Pollard rho** — বড় সংখ্যার factorization; birthday paradox-এর উপর দাঁড়ানো cycle-খোঁজা
- **Sieve variants** — smallest prime factor (SPF) sieve, linear sieve, আর segmented sieve — একই ছাঁকনির তিন রূপ

## কেন এই level দরকার?

**Competitive programming (CP) এ:** Codeforces Div 2 D/E আর Div 1-এ number theory নিয়মিত মুখ। CRT, Mobius, matrix exponentiation — এগুলো ছাড়া অনেক problem-এর দরজাই খোলে না। আর CSES-এর Mathematics section পুরোটাই এই level-এর খেলার মাঠ।

**Interview এ:** সরাসরি খুব কম — তবে modular inverse আর fast exponentiation-এর চিন্তাভঙ্গি (divide and conquer on exponent) মাঝে মাঝে কাজে লাগে। আবারও মনে করিয়ে দিই: interview target হলে এই level **পরে করলেও চলবে**।

**পরের level গুলোতে:** Level 11-এর matrix power on graphs (147) সরাসরি 131-এর উপর দাঁড়ানো; আর Mobius-এর inclusion-exclusion চিন্তা 148-এ ফিরবে।

## Prerequisites

- Level 1-2 ভালোভাবে ঝালাই — বিশেষ করে:
  - gcd / Euclid (problem 018, 019) — extended Euclid এর সরাসরি extension
  - Modular arithmetic, Fermat inverse (problem 032), binary exponentiation (problem 029)
  - Basic totient (problem 023), sieve (problem 015), trial division primality (problem 013)
- Level 3-এর inclusion-exclusion (problem 044) — Mobius বুঝতে লাগবে
- Recursion-এ স্বচ্ছন্দ — extended Euclid আর fast doubling দুটোই recursive ভাবলে সহজ

## Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

- [ ] Extended Euclid-এ back-substitution-এর সিঁড়িটা একটা ছোট উদাহরণে (যেমন gcd(30, 18)) হাতে চালাতে পারি
- [ ] `ax + by = c` কখন solvable — শর্তটা আর তার কারণ বলতে পারি
- [ ] CRT-র "দুটো ঘড়ি মেলানো" গল্পটা একটা সংখ্যার উদাহরণে দেখাতে পারি
- [ ] φ(n) prime factorization থেকে বের করার formula জানি, আর φ multiplicative মানে কী বুঝি
- [ ] μ(n)-এর তিনটা মান (1, −1, 0) কখন হয় — মুখস্থ না, যুক্তিসহ জানি
- [ ] Modular inverse-এর দুই পথ (Fermat আর ext-gcd) — কখন কোনটা লাগে জানি
- [ ] Fibonacci-র matrix form `[[1,1],[1,0]]` কেন কাজ করে — এক ধাপ গুণ করে দেখাতে পারি
- [ ] Miller-Rabin-এ "witness" মানে কী, আর কেন কয়েকটা নির্দিষ্ট base-এ 64-bit deterministic হয় — ধারণা আছে
- [ ] SPF sieve দিয়ে O(log n)-এ factorization করতে পারি, আর segmented sieve কখন লাগে জানি

## Problem list

মোট 14টা problem — 6টা Medium, 8টা Hard। (Easy নেই — এটা advanced level!)

### Medium

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 125 | [Extended Euclidean Algorithm](problems/125-extended-euclidean.md) | back substitution | CP-Algorithms — <https://cp-algorithms.com/algebra/extended-euclid-algorithm.html> |
| 126 | [Linear Diophantine Equation](problems/126-linear-diophantine.md) | gcd divisibility | CP-Algorithms — <https://cp-algorithms.com/algebra/linear-diophantine-equation.html> |
| 128 | [Euler Totient Advanced](problems/128-euler-totient-advanced.md) | multiplicative phi | CP-Algorithms — <https://cp-algorithms.com/algebra/phi-function.html> |
| 130 | [Modular Inverse Advanced](problems/130-modular-inverse-advanced.md) | ext-gcd inverse | CP-Algorithms — <https://cp-algorithms.com/algebra/module-inverse.html> |
| 134 | [Primality Test Advanced](problems/134-primality-test-advanced.md) | beyond trial division | CP-Algorithms — <https://cp-algorithms.com/algebra/primality_tests.html> |
| 137 | [Sieve Variants](problems/137-sieve-variants.md) | SPF / linear sieve | CP-Algorithms — <https://cp-algorithms.com/algebra/prime-sieve-linear.html> |

### Hard

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 127 | [Chinese Remainder Theorem Basic](problems/127-crt-basic.md) | modulus merge | CP-Algorithms — <https://cp-algorithms.com/algebra/chinese-remainder-theorem.html> |
| 129 | [Mobius Function Intro](problems/129-mobius-function-intro.md) | IE encoding | Wikipedia — <https://en.wikipedia.org/wiki/M%C3%B6bius_function> |
| 131 | [Matrix Exponentiation](problems/131-matrix-exponentiation.md) | recurrence as matrix | Classic CP technique (USACO Guide — <https://usaco.guide/plat/matrix-expo>) |
| 132 | [Fibonacci using Matrix Exponentiation](problems/132-fibonacci-matrix-expo.md) | matrix power | CP-Algorithms Fibonacci — <https://cp-algorithms.com/algebra/fibonacci-numbers.html> |
| 133 | [Fast Doubling Fibonacci](problems/133-fast-doubling-fibonacci.md) | F(2k) formulas | CP-Algorithms Fibonacci page |
| 135 | [Miller-Rabin Intro](problems/135-miller-rabin-intro.md) | probabilistic test | CP-Algorithms primality tests page |
| 136 | [Pollard Rho Intro](problems/136-pollard-rho-intro.md) | cycle factoring | CP-Algorithms — <https://cp-algorithms.com/algebra/factorization.html> |
| 138 | [Segmented Sieve](problems/138-segmented-sieve.md) | windowed sieve | CP-Algorithms sieve page — <https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html> |

পুরো tracker table (status সহ) আছে [problems/README.md](problems/README.md)-তে।

## Recommended order

1. **125 → 126 → 130** — extended Euclid trilogy: আগে x, y বের করা শেখো, তারপর Diophantine, তারপর তা দিয়ে inverse
2. **127** — CRT; 125-এর সরাসরি প্রয়োগ, তাই এর ঠিক পরে
3. **128 → 129** — totient ঝালাই, তারপর Mobius; দুটোই multiplicative function-এর জগৎ
4. **131 → 132 → 133** — matrix exponentiation trilogy: general কাঠামো → Fibonacci → fast doubling shortcut
5. **134 → 135 → 136** — primality trilogy: trial division-এর সীমা → Miller-Rabin → Pollard rho
6. **137 → 138** — sieve variants দিয়ে শেষ; এগুলো বাকি সবার toolbox

## Common mistakes (সাধারণ ভুল)

1. **Extended Euclid-এ x, y-এর update rule গুলিয়ে ফেলা** — recursion থেকে ফেরার সময় `x, y = y1, x1 − (a // b) * y1` — একটা ছোট উদাহরণে হাতে verify না করে কখনো use কোরো না।
2. **Diophantine-এ `gcd | c` check না করেই solution খোঁজা** — solvability শর্তটাই প্রথম লাইন; না মিললে সোজা "no solution"।
3. **CRT-তে moduli coprime কি না না দেখা** — basic CRT coprime moduli ধরে নেয়; coprime না হলে আলাদা merge-নিয়ম (general CRT) লাগে।
4. **Modular inverse-এ `gcd(a, m) ≠ 1` ধরা না** — inverse-এর অস্তিত্বই নেই তখন; Fermat শুধু prime m-এ চলে, ext-gcd চলে coprime হলেই।
5. **Matrix exponentiation-এ matrix গুণের ক্রম উল্টে ফেলা** — matrix multiplication commutative না; base case (identity matrix) আর গুণের order ঠিক রাখো।
6. **Miller-Rabin-এ `n − 1 = 2^s · d` decompose করতে ভুল** — d বিজোড় হওয়া পর্যন্ত 2 দিয়ে ভাগ; s গোনায় off-by-one মানেই ভুল রায়।
7. **Pollard rho-তে n prime কি না আগে check না করা** — rho prime-এ অনন্ত ঘুরবে; আগে Miller-Rabin, তারপর rho।
8. **Segmented sieve-এ window-এর শুরু থেকে multiple-এর offset ভুল করা** — `max(p*p, ((L + p − 1) // p) * p)` — এই ceiling-multiple হিসাবটা খাতায় একবার করে নাও।
9. **Python-এ এসব লাগবে না ভেবে `sympy.isprime` দিয়েই চালানো** — শেখার সময় নিজে লেখো; contest-এ library allowed হলে তখন আলাদা কথা।

## পরের level এ যাওয়ার আগে checklist

- [ ] 14টা problem-ই অন্তত একবার নিজে solve করেছি
- [ ] gcd(30, 18)-এর extended Euclid টা না দেখে খাতায় নামাতে পারি (x, y সহ)
- [ ] একটা CRT উদাহরণ (যেমন x ≡ 2 mod 3, x ≡ 3 mod 5) হাতে মিলিয়েছি
- [ ] μ(1) থেকে μ(12) পর্যন্ত table টা যুক্তিসহ বানিয়েছি
- [ ] Fibonacci matrix-এর এক ধাপ গুণ হাতে করে F(2), F(3) মিলিয়েছি
- [ ] Miller-Rabin একটা composite-এ (যেমন 561 — Carmichael number!) চালিয়ে দেখেছি
- [ ] SPF array দিয়ে 60-এর factorization O(log n)-এ trace করেছি

সব টিক দিতে পারলে — চলো [Level 11: Hard Mixed CP Patterns](../11-hard-mixed-cp-patterns/README.md)-এ। (আর interview-পথের পথিক হলে — মূল DS topic গুলো শেষ; এখানে যা শিখলে তা bonus মশলা।)

## Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে [source-map.md](source-map.md)-তে।