# Modulo — ঘর, চক্র ও inverse

## Mod 5-এ 7 ধাপ এগোনো

```mermaid
flowchart LR
    A["0"] --> B["1"] --> C["2"] --> D["3"] --> E["4"] --> A
```

সম্পূর্ণ পথ: `0 → 1 → 2 → 3 → 4 → 0 → 1 → 2`। তাই `7 % 5 = 2`। ঘড়ির মতো ঘুরে আসি, মোট কয়বার ঘুরেছি সেই তথ্য আর রাখি না।

## 3⁵ mod 7: প্রতিটি binary-exponentiation ধাপ

| শুরুতে exponent | result | base | কাজের পরে result | square-এর পরে base |
| --- | --- | --- | --- | --- |
| 5 (odd) | 1 | 3 | 3 | 2 |
| 2 (even) | 3 | 2 | 3 | 4 |
| 1 (odd) | 3 | 4 | 5 | 2 |

প্রতিবার exponent-কে 2 দিয়ে integer divide করা হয়: `5 → 2 → 1 → 0`। উত্তর 5। সরাসরি `3⁵=243`, `243%7=5` দিয়েও মেলে।

## ভাগের বদলে inverse

```mermaid
flowchart LR
    A["3 × 5 = 15 ≡ 1 mod 7"] --> B["3-এর inverse হলো 5"]
    B --> C["6 / 3 mod 7 = 6 × 5 mod 7 = 2"]
    C --> D["যাচাই: 2 × 3 mod 7 = 6"]
```

`1/3 mod 7`-এর মান 5; এটি integer division-এর 0 নয়। আমরা এমন x খুঁজছি যাতে `3x ≡ 1 (mod 7)`।

Mod 6-এ 2-এর inverse নেই: `2x % 6` শুধু 0,2,4 হতে পারে, কখনো 1 নয়। তাই modular division-এর আগে `gcd(ভাজক,modulus)=1` পরীক্ষা জরুরি।

## যোগ, গুণ ও power-cycle

| হিসাব | ছোট করে হিসাব | ফল |
| --- | --- | --- |
| (9+8) mod 12 | 17 mod 12 | 5 |
| (9−11) mod 12 | −2-এর nonnegative remainder | 10 |
| (8×9) mod 5 | (3×4) mod 5 | 2 |

7-এর positive powers-এর শেষ অঙ্কের পূর্ণ cycle:

```mermaid
flowchart LR
    A["7¹: 7"] --> B["7²: 9"] --> C["7³: 3"] --> D["7⁴: 1"] --> A
```

`7⁶`-এর শেষ অঙ্ক দ্বিতীয় ঘরের 9; কারণ `(6−1)%4=1`। Exponent 0 হলে আলাদা করে `7⁰=1`।

## nCr-এর তিন ধাপ: C(5,2) mod 7

```mermaid
flowchart LR
    A["numerator: 5! mod 7 = 1"] --> C["1 × inverse(5) mod 7"]
    B["denominator: 2! × 3! mod 7 = 5"] --> C
    C --> D["inverse(5)=3; উত্তর 3"]
```

সরাসরি `C(5,2)=10`, `10%7=3`। এই factorial পদ্ধতিতে `n<p` রাখা হয়েছে।

## ছোট rolling hash: একই remainder হলে collision হতে পারে

ধরি A=1, B=2, base=3, modulus=7; প্রতিটি অক্ষরে `h=(h*3+value)%7`।

| string | প্রথম state | পরের state | hash |
| --- | --- | --- | --- |
| AB | 1 | (1×3+2)%7 | 5 |
| BA | 2 | (2×3+1)%7 | 0 |

Hash ছোট range-এ অনেক string-কে বসায়; এটি দ্রুত প্রার্থী খোঁজে, সমতার নিশ্চয়তা দেয় না।

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