# Advanced number theory — হিসাবের দৃশ্যমান ধাপ

## Extended Euclid: gcd(99,78)=3

| নিচে নামা: remainder | ওপরে ওঠা: substitution |
| --- | --- |
| 99 = 1×78 + 21 | 3 = 14×78 − 11×99 |
| 78 = 3×21 + 15 | 3 = 3×78 − 11×21 |
| 21 = 1×15 + 6 | 3 = 3×15 − 2×21 |
| 15 = 2×6 + 3 | 3 = 15 − 2×6 |
| 6 = 2×3 + 0 | এখান থেকে ওপরে পড়ো |

শেষে `x=-11, y=14`। সরাসরি যাচাই: `99×(-11)+78×14=-1089+1092=3`। শুধু remainder নয়, পুরোনো সংখ্যার linear combination-ও ধরে রেখেছি।

## CRT: দুটি ভাগশেষের মিল

`x % 3 = 2`, `x % 5 = 3`; 0 থেকে 14-এর মধ্যে:

| শর্ত | মেলে এমন সব মান |
| --- | --- |
| mod 3-এ 2 | 2,5,8,11,14 |
| mod 5-এ 3 | 3,8,13 |
| দুই তালিকার ছেদ | 8 |

3 ও 5 coprime, তাই সমাধান `x = 8 + 15k`, integer k-এর জন্য। প্রথম তিনটি nonnegative উত্তর 8,23,38।

## Matrix power: 13টি transition

```mermaid
flowchart LR
    A["T: 1 ধাপ"] -->|"square"| B["T²: 2 ধাপ"]
    B -->|"square"| C["T⁴: 4 ধাপ"]
    C -->|"square"| D["T⁸: 8 ধাপ"]
    D --> E["T¹³ = T⁸ × T⁴ × T"]
```

13-এর binary 1101; জ্বলা bit-এর powers নিই। Fibonacci-তে `T=[[1,1],[1,0]]`, initial column `[F1,F0]=[1,0]`; এক ধাপে `[1,1]`, দুই ধাপে `[2,1]`, তিন ধাপে `[3,2]`। State-এর order বদলালে matrix-ও বদলাবে।

## Segmented sieve: [10,20]

√20 পর্যন্ত prime হলো 2 ও 3। 2 কাটে 10,12,14,16,18,20; 3 নতুন করে কাটে 15। অবশিষ্ট prime 11,13,17,19। প্রথম কাটার স্থান `max(p*p, ceil(L/p)*p)`—এতে range-এর মধ্যে p থাকলেও p নিজে বাদ পড়ে না। 0 ও 1 থাকলে আলাদাভাবে বাদ দিতে হবে।

## Diophantine সমাধানের পরিবার

`99x+78y=3`-এর একটি সমাধান (−11,14)। GCD=3 বলে `x=-11+26t`, `y=14-33t`।

| t | x | y | 99x+78y |
| --- | --- | --- | --- |
| −1 | −37 | 47 | 3 |
| 0 | −11 | 14 | 3 |
| 1 | 15 | −19 | 3 |

`ax+by=c`-এ gcd(a,b) যদি c-কে ভাগ না করে, integer সমাধান নেই।

## Möbius-এর তিন রকম ফল

| n | prime factorization | μ(n) |
| --- | --- | --- |
| 1 | কোনো prime factor নেই | 1 |
| 6 | 2×3, দুটি ভিন্ন prime | +1 |
| 30 | 2×3×5, তিনটি ভিন্ন prime | −1 |
| 12 | 2²×3, square factor আছে | 0 |

Totient-এর 12-এর উদাহরণ [মৌলিক number theory চিত্রে](../01-divisibility-prime-gcd-lcm/visualization-ideas.md) আছে। μ একই সংখ্যা গোনা inclusion–exclusion-এর sign সংগঠিত করতে সাহায্য করে।

## Miller–Rabin: একটি base-এর ফল কী বোঝায়

| n | n−1 = d×2ˢ | base 2-এ প্রথম x=2ᵈ mod n | পরের square | সিদ্ধান্ত |
| --- | --- | --- | --- | --- |
| 13 | 3×2² | 8 | 12 = n−1 | এই base-এ pass |
| 21 | 5×2² | 11 | 16, n−1 নয় | composite নিশ্চিত |

একটি base-এ pass মানেই prime নিশ্চিত নয়। প্রথম x=1 বা n−1 হলেও pass; অন্যথায় নির্ধারিত square-গুলোর কোনোটি n−1 হতে হবে। Deterministic ফলের জন্য পরীক্ষিত base set ও তার integer সীমা মানতে হবে।

## Pollard rho: পুরো n-এ সমান হওয়ার আগেই factor মেলে

`n=91`, `f(x)=(x²+1)%91`, দুজনের শুরু x=y=2।

```mermaid
flowchart LR
    A["শুরু: 2"] --> B["f(2)=5"] --> C["f(5)=26"]
    B --> D["কচ্ছপ x=5"]
    C --> E["খরগোশ y=26"]
    D --> F["gcd(abs(5-26),91)=7"]
    E --> F
```

5 ও 26 modulo 7-এ সমান, তাই factor 7 পাওয়া গেল। gcd=1 হলে চালাই; gcd=n হলে এই চেষ্টা ব্যর্থ, অন্য seed/constant নিয়ে শুরু করি।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)