# Concept Notes — Divisibility, Prime, GCD, LCM

## সহজ করে শুরু: ভাগ যায় কি না থেকে সাধারণ গুণনীয়ক

একটি সংখ্যার factor জোড়ায় আসে: 36-এর জন্য (1,36), (2,18), (3,12), (4,9), (6,6)। তাই একটি সংখ্যা prime কি না দেখতে square root পর্যন্ত পরীক্ষা যথেষ্ট। অনেক সংখ্যা একসঙ্গে লাগলে sieve; দুটি সংখ্যার সাধারণ factor লাগলে Euclid-এর GCD।

**প্রোগ্রামে কোথায় ব্যবহার করবে:** ভগ্নাংশ ছোট করা, সমান আকারে জিনিস ভাগ করা এবং দুটি নির্দিষ্ট বিরতির কাজ আবার কখন একসঙ্গে ঘটবে—এসবে GCD/LCM লাগে।

**কৌশল বাছার আগে শর্ত:** 1 prime নয়। square সংখ্যার মাঝের factor একবার গুনবে। দুটি সংখ্যাই 0 হলে LCM আলাদাভাবে সামলাও; বড় গুণফল এড়াতে আগে GCD দিয়ে ভাগ করো।

পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও।

> Level 0-এর মতোই নিয়ম: প্রতিটা snippet-এর mini dry run খাতায় নিজে হাতে করো। এই level-এ ছবিগুলো আরও জরুরি — sieve-এর grid, GCD-র সিঁড়ি — এগুলো একবার চোখে দেখলে আর ভোলা যায় না।

## 1. Divisor মানে ভাগ মিলে যাওয়া

`b` যদি `a`-কে নিঃশেষে ভাগ করে — মানে remainder 0 — তাহলে বলি b হলো a-এর divisor (বা factor)। Code-এ এক লাইন:

```python
a, b = 12, 4
print(a % b == 0)   # True -> 4 divides 12
```

**Mini dry run:** `12 % 4` — 12 = 4×3 + 0, remainder 0 → divisor। আবার `12 % 5` — 12 = 5×2 + 2, remainder 2 → divisor না।

Analogy: 12টা লাড্ডু 4 জনকে দিলে কারো মন খারাপ হয় না — প্রত্যেকে 3টা করে, হাতে কিছু থাকে না। 5 জনকে দিলে 2টা লাড্ডু নিয়ে ঝগড়া — remainder-ই সেই ঝগড়ার লাড্ডু। **Divisibility মানে ঝগড়াহীন ভাগ।**

কিছু চেনা divisibility rule (কেন কাজ করে, Level 2-তে mod দিয়ে প্রমাণ দেখব):

```
2  -> last digit even        3 -> digit sum 3 দিয়ে ভাগ যায়
5  -> last digit 0 বা 5      9 -> digit sum 9 দিয়ে ভাগ যায় (digital root!)
10 -> last digit 0
```

## 2. Factor pair — কেন √n পর্যন্ত খুঁজলেই হয়

36-এর সব divisor লিখে একটা মজার জিনিস দেখো:

```
1 × 36    2 × 18    3 × 12    4 × 9    6 × 6   <- ঠিক মাঝখানে, √36 = 6
36 × 1   18 × 2    12 × 3    9 × 4              এরপর জোড়াগুলোই উল্টে আসে!
```

Divisor রা **জোড়ায়** আসে: `d` যদি divisor হয়, `n // d`-ও divisor। আর প্রতিটা জোড়ার ছোট জনটা সবসময় √n-এর এপারে থাকে (দুজনেই √n-এর চেয়ে বড় হলে গুণফল n ছাড়িয়ে যেত!)। তাই √n পর্যন্ত খুঁজে প্রতিবার **জোড়াসুদ্ধ** তুলে নিলেই সব divisor পাওয়া যায়।

```python
def count_factors(n):
    count = 0
    i = 1
    while i * i <= n:
        if n % i == 0:
            count += 2          # i আর n//i — জোড়া
            if i * i == n:
                count -= 1      # perfect square: 6×6 একই জন, একবার গোনো
        i += 1
    return count
```

**Mini dry run (n = 36):** i = 1 → জোড়া (1,36), count=2। i=2 → (2,18), count=4। i=3 → (3,12), count=6। i=4 → (4,9), count=8। i=5 → 36%5≠0। i=6 → 6×6=36, count=10, কিন্তু perfect square তাই −1 → **9**। মিলিয়ে দেখো: 1,2,3,4,6,9,12,18,36 — ঠিক 9টা।

এটাই এই level-এর সবচেয়ে বড় শিক্ষা: **O(n) loop-কে O(√n) এ নামানো।** n = 10¹² হলে n-loop অসম্ভব, কিন্তু √n = 10⁶ — এক লহমায় শেষ।

## 3. Prime check — trial division

Prime মানে যার ঠিক **দুটো** divisor: 1 আর সে নিজে। (তাই 1 prime না — তার divisor মোটে একটা!) Check করার সরল উপায়: 2 থেকে √n পর্যন্ত কেউ ভাগ করে কি না দেখো —

```python
def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False        # ভাগ মিলে গেছে -> composite
        i += 1
    return True
```

**Mini dry run (n = 91):** i=2 → 91 odd। i=3 → digit sum 10, ভাগ যায় না। i=4 → না। i=5 → last digit 1, না। i=6 → না। i=7 → 91 = 7×13 → **False!** 91 দেখতে prime-এর মতো, কিন্তু না — এজন্যই check লাগে। আর n = 97 হলে i = 2..9 কেউ ভাগ করে না, i=10-এ 10×10 > 97 → True।

কেন √n যথেষ্ট? Section 2-এর সেই জোড়ার যুক্তি: n-এর কোনো divisor থাকলে তার জোড়ার একজন √n-এর এপারে অবশ্যই আছে।

## 4. Sieve of Eratosthenes — multiples কেটে ফেলা

এক-একটা সংখ্যা আলাদা করে prime check করলে n পর্যন্ত সব prime বের করতে অনেক সময় লাগে। প্রাচীন গ্রিক Eratosthenes-এর কৌশল উল্টো: **prime খুঁজো না, composite-দের কেটে ফেলো — যারা বেঁচে থাকবে তারাই prime।**

2 থেকে 30-এর grid-এ খেলাটা দেখো:

```
 2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

ধাপ 1: 2 বাঁচল, 2-এর multiple সব কাটো (4,6,8,...):
 2  3  x  5  x  7  x  9  x
11  x 13  x 15  x 17  x 19  x
21  x 23  x 25  x 27  x 29  x

ধাপ 2: 3 বাঁচল, 3-এর multiple কাটো (9 থেকে শুরু — 6 আগেই কাটা):
 2  3  x  5  x  7  x  x  x
11  x 13  x  x  x 17  x 19  x
 x  x 23  x 25  x  x  x 29  x

ধাপ 3: 5 বাঁচল, 25 কাটো। 7-এ গিয়ে 7×7=49 > 30 — খেলা শেষ!
বেঁচে রইল: 2 3 5 7 11 13 17 19 23 29 -> এরাই prime
```

Code:

```python
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:
        if is_prime[i]:                  # i বেঁচে আছে মানে prime
            for j in range(i * i, n + 1, i):
                is_prime[j] = False      # i-এর multiple কাটো
        i += 1
    return [x for x in range(n + 1) if is_prime[x]]
```

**Mini dry run (n = 20):** i=2 → কাটা পড়ে 4,6,8,...,20। i=3 → কাটা পড়ে 9,15 (12,18 আগেই কাটা, তবু আবার False করলে ক্ষতি নেই)। i=4 → is_prime[4] False, skip। i=5 → 5×5=25 > 20, থামো। বেঁচে: 2,3,5,7,11,13,17,19।

দুটো সূক্ষ্ম জিনিস: (1) marking শুরু `i * i` থেকে — কারণ `i`-এর ছোট multiple-রা (2i, 3i, ...) আরও ছোট prime-এর হাতে আগেই কাটা পড়েছে; (2) total কাজ `n/2 + n/3 + n/5 + ...` ≈ **O(n log log n)** — প্রায় linear, আশ্চর্য দ্রুত। Sieve হলো "একবার কারখানা বানাও, তারপর হাজারটা query free" — এই precompute pattern পুরো CP জুড়ে চলবে।

## 5. Prime factorization — ছোট prime দিয়ে খোসা ছাড়ানো

প্রতিটা সংখ্যার একটা unique "DNA" আছে — prime-দের গুণফল হিসেবে লেখা রূপ। যেমন `360 = 2³ × 3² × 5`। বের করার কৌশল: পেঁয়াজের খোসার মতো, সবচেয়ে ছোট prime দিয়ে যতবার পারো ভাগ করো, তারপর পরেরটা।

```python
def factorize(n):
    factors = {}
    p = 2
    while p * p <= n:
        while n % p == 0:       # এক prime নিঃশেষে ছাড়াও
            factors[p] = factors.get(p, 0) + 1
            n //= p
        p += 1
    if n > 1:                   # যা বাকি, সে নিজেই একটা বড় prime
        factors[n] = factors.get(n, 0) + 1
    return factors
```

**Mini dry run (n = 360):**

| p | ভাগ চলে? | n হয়ে যায় | factors |
| --- | --- | --- | --- |
| 2 | 360→180→90→45 | 45 | {2: 3} |
| 3 | 45→15→5 | 5 | {2: 3, 3: 2} |
| 4 | 5 % 4 ≠ 0 | 5 | — |
| 5 | 5×5 > 5, loop শেষ | — | — |
| শেষে | n = 5 > 1 | — | {2: 3, 3: 2, 5: 1} |

দেখো — p prime কি না check করারও দরকার পড়েনি! কারণ p = 4-এ পৌঁছানোর আগে 2 সব নিঃশেষ করে গেছে; composite-এর পালা কখনো আসেই না। আর শেষের `if n > 1` — এটাই সবচেয়ে ভোলা অংশ: `n = 2 × 7919` হলে loop-এ শুধু 2 ধরা পড়বে, 7919 (বড় prime) পড়ে থাকবে।

**SPF (smallest prime factor) sieve:** অনেকগুলো সংখ্যা factorize করতে হলে sieve চালানোর সময় প্রতিটা ঘরে লিখে রাখো "তোমাকে প্রথম কে কাটল" — সেটাই তার smallest prime factor। পরে যেকোনো n-কে factorize করতে শুধু `spf[n]` দিয়ে ভাগ করতে করতে নামো — প্রতি ধাপে অন্তত অর্ধেক হয়, তাই **O(log n)** প্রতি query! খোঁজাখুঁজি নেই, সিঁড়ি ready।

```python
spf = list(range(n + 1))            # শুরুতে সবাই নিজের spf
for i in range(2, int(n**0.5) + 1):
    if spf[i] == i:                 # i prime
        for j in range(i * i, n + 1, i):
            if spf[j] == j:         # আগে কেউ কাটেনি
                spf[j] = i
```

## 6. Euclid-এর GCD — `gcd(a, b) = gcd(b, a % b)`

GCD (greatest common divisor) = দুটো সংখ্যাকেই ভাগ করে এমন সবচেয়ে বড় সংখ্যা। Euclid-এর ২৩০০ বছরের পুরোনো আবিষ্কার: **gcd(a, b) = gcd(b, a % b)** — বড় জোড়াকে ছোট জোড়ায় নামাতে থাকো।

Intuition-টা tile দিয়ে ভাবো: 48 × 18 মেঝেতে সবচেয়ে বড় square tile বসাতে চাও যাতে কাটাকাটি না লাগে। 18 × 18 tile বসালে 48 = 18+18+12 — শেষে 12 × 18 ফালি বাকি। এখন সমস্যা ছোট হয়ে গেল: 18 × 12 ফালিতে একই প্রশ্ন! আবার: 12 × 12 বসাও, বাকি 12 × 6। আবার: 6 × 6 বসাও — মিলে গেল, কিছু বাকি নেই। **উত্তর: 6।**

```
48 × 18 মেঝে:
+------------------+------------------+------------+
|                  |                  |            |
|     18 × 18      |     18 × 18      |  18 × 12   | <- বাকি ফালি
|                  |                  |            |    = নতুন সমস্যা
+------------------+------------------+------------+
   48 % 18 = 12  ->  এবার 18 × 12 নিয়ে একই খেলা -> 12 % 18... 
   ধাপে ধাপে: (48,18) -> (18,12) -> (12,6) -> (6,0) -> উত্তর 6
```

কেন কাজ করে? যে সংখ্যা a আর b দুটোকেই ভাগ করে, সে `a − b`-কেও করে (আর তাই `a % b`-কেও) — মানে (a, b) আর (b, a%b)-এর common divisor-এর তালিকা **হুবহু একই**। তালিকা একই হলে তার সবচেয়ে বড়টাও একই।

```python
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
```

**Mini dry run (gcd(48, 18)):**

| step | a | b | a % b |
| --- | --- | --- | --- |
| 1 | 48 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 |
| 4 | 6 | 0 | b=0, থামো |

উত্তর **6** — tile-এর গল্পের সাথে হুবহু মিলল। প্রতি দুই ধাপে সংখ্যা অন্তত অর্ধেক হয়, তাই complexity **O(log min(a, b))** — 10¹⁸ size-এর সংখ্যাতেও ৯০-এর কম ধাপ!

**Extended GCD-র এক ঝলক:** Euclid-এর ধাপগুলো উল্টোদিকে হাঁটলে (back-substitution) এমন x, y পাওয়া যায় যাতে `a·x + b·y = gcd(a, b)`। যেমন `48·(−1) + 18·3 = 6`। এখন শুধু এটুকু জানো যে এটা সম্ভব — Level 2-তে modular inverse বের করতে এই কৌশলই কাজে লাগবে।

## 7. LCM আর coprime — GCD-র দুই আত্মীয়

**LCM** (least common multiple) = দুটো সংখ্যারই multiple এমন সবচেয়ে ছোট সংখ্যা। সূত্র: `gcd × lcm = a × b`। কেন? Factorization দিয়ে ভাবো — gcd নেয় প্রতিটা prime-এর **min** power, lcm নেয় **max** power; আর min + max = দুটোর যোগফল, তাই গুণফল মিলে যায়।

```python
def lcm(a, b):
    return a // gcd(a, b) * b   # আগে ভাগ! a*b আগে করলে অযথা বিশাল সংখ্যা
```

**Mini dry run (lcm(12, 18)):** gcd(12, 18) = 6 → `12 // 6 = 2` → `2 × 18 = 36`। Check: 36 = 12×3 = 18×2 — দুজনেরই multiple, আর এর ছোট কেউ নেই।

**Coprime** মানে gcd(a, b) = 1 — দুজনের মাঝে কোনো common factor নেই (1 ছাড়া)। যেমন 8 আর 15: `8 = 2³`, `15 = 3×5` — কোনো prime মেলে না। মজার ব্যাপার, 8 আর 15 কেউই নিজে prime না, তবু coprime! Coprime-এর ধারণা Level 2-তে modular inverse-এর শর্ত হয়ে ফিরবে — inverse আছে কি না, gcd = 1 দিয়েই নির্ধারিত হয়।

```python
def is_coprime(a, b):
    return gcd(a, b) == 1
```

## 8. Euler phi — n-এর coprime বন্ধু কয়জন?

φ(n) = 1 থেকে n-এর মধ্যে কয়টা সংখ্যা n-এর সাথে coprime। যেমন φ(12): তালিকা 1,2,...,12-এর মধ্যে 12-এর সাথে gcd 1 হয় শুধু **1, 5, 7, 11** — তাই φ(12) = 4।

হাতে গোনা ছাড়া formula আছে, factorization থেকে: n-এর প্রতিটা distinct prime p-এর জন্য n-কে `(1 − 1/p)` গুণ করো —

```
φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4
```

Intuition: 1..12-এর মধ্যে অর্ধেক 2-এর ভাগে কাটা পড়ে (×1/2 টিকে থাকে), টিকে থাকাদের এক-তৃতীয়াংশ 3-এর ভাগে কাটা পড়ে (×2/3 টিকে থাকে) — sieve-এর crossing-out-এরই ভগ্নাংশ-রূপ!

```python
def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p   # result × (1 - 1/p), integer-এ
        p += 1
    if n > 1:
        result -= result // n
    return result
```

**Mini dry run (n = 12):** p=2 ভাগ যায় → n হয়ে যায় 3, `result = 12 − 12//2 = 6`। p=3: 3×3 > 3, loop শেষ; n = 3 > 1 → `result = 6 − 6//3 = 4`। φ(12) = **4** — হাতে গোনার সাথে মিলল। (লক্ষ করো `result -= result // p` — float এড়ানোর কৌশল।) φ পরে Fermat/Euler theorem-এ (Level 2) প্রধান চরিত্র।

## 9. Divisor count আর sum — exponent থেকে formula

Factorization জানা থাকলে divisor গুনতে আর loop লাগে না। `n = p1^e1 × p2^e2 × ...` হলে —

**Divisor count = (e1+1) × (e2+1) × ...**

কেন? একটা divisor বানাতে প্রতিটা prime থেকে "কয়টা নেবে" বেছে নিতে হয়: p1 থেকে 0 থেকে e1 টা — মোট **(e1+1) রকম** choice। প্রতিটা prime-এর choice independent, তাই গুণ। (এটা আসলে Level 3-এর multiplication principle-এর আগাম দর্শন!)

```
360 = 2³ × 3² × 5¹
2-এর power বাছো: 2⁰,2¹,2²,2³ -> 4 রকম
3-এর power বাছো: 3⁰,3¹,3²   -> 3 রকম
5-এর power বাছো: 5⁰,5¹      -> 2 রকম
মোট divisor = 4 × 3 × 2 = 24
```

**Mini dry run:** 36 = 2² × 3² → (2+1)(2+1) = 9 — section 2-এর হাতে-গোনা 9-এর সাথে হুবহু মিলে গেল!

**Divisor sum**-ও একই যুক্তি, শুধু "কয় রকম" এর জায়গায় "সবগুলো যোগ করলে কত":

```
sum = (p1⁰ + p1¹ + ... + p1^e1) × (p2⁰ + ... + p2^e2) × ...

36 = 2² × 3²:
sum = (1 + 2 + 4) × (1 + 3 + 9) = 7 × 13 = 91
check: 1+2+3+4+6+9+12+18+36 = 91 ✓
```

```python
def divisor_count_and_sum(n):
    count, total = 1, 1
    p = 2
    while p * p <= n:
        if n % p == 0:
            e, power_sum, pw = 0, 1, 1
            while n % p == 0:
                n //= p
                e += 1
                pw *= p
                power_sum += pw     # 1 + p + p² + ...
            count *= (e + 1)
            total *= power_sum
        p += 1
    if n > 1:
        count *= 2
        total *= (1 + n)
    return count, total
```

**Mini dry run (n = 12):** p=2 → e=2, power_sum = 1+2+4 = 7 → count=3, total=7। p=3-এ পৌঁছানোর আগে n = 3, loop শেষ → n>1: count = 3×2 = **6**, total = 7×4 = **28**। Check: 12-এর divisor 1,2,3,4,6,12 — সংখ্যায় 6, যোগে 28 ✓।

## এক নজরে (cheat sheet)

```
a % b == 0          -> b divides a
i*i <= n loop       -> O(√n): factor, prime check
sieve               -> multiples কেটে ফেলো, O(n log log n)
factorize           -> ছোট prime দিয়ে খোসা ছাড়াও; শেষে n>1 হলে সে-ও prime
spf[n] দিয়ে নামো    -> O(log n) factorization (precompute-এর পরে)
gcd(a,b)=gcd(b,a%b) -> Euclid, O(log) ধাপ; gcd(a,0)=a
lcm = a//g * b      -> আগে ভাগ, পরে গুণ
coprime             -> gcd == 1
φ(n) = n·∏(1-1/p)   -> coprime বন্ধু গোনা
d(n) = ∏(eᵢ+1)      -> divisor count, exponent থেকে
```

পরের ধাপ: [problems/](problems/README.md)-এর 15টা problem। তারপর Level 2-তে — যেখানে দেখব `%` শুধু remainder বের করার tool না, একটা আস্ত **গণিতের জগৎ**।