বিভাজ্যতা আর মৌলিক সংখ্যা — division algorithm আর unique factorization

১ · বিভাজ্যতা — সংজ্ঞা আর ধর্ম

বাজারঘরের গুদামে ৩৬টি চায়ের প্যাকেট আছে। বাক্সে ৬টি করে ভরলে ৬টি বাক্স পুরো ভরে, কিছু বাকি থাকে না। ৫টি করে ভরলে ৭টি বাক্স ভরে, আর ১টি প্যাকেট পড়ে থাকে। প্রথম ক্ষেত্রে বলি ৬ দিয়ে ৩৬ নিঃশেষে বিভাজ্য। সংখ্যাতত্ত্ব (number theory) এই সরল প্রশ্ন থেকেই শুরু: কোন সংখ্যা কোন সংখ্যাকে নিঃশেষে ভাগ করে। এই মডিউলের সাতটি পর্ব শেষে একই প্রশ্ন থেকে আমরা পৌঁছাব check digit, hashing আর মডিউল ৫-এর cryptography-তে।

চিহ্নটি খাড়া দাগ “∣”, ভগ্নাংশের “/” নয়। a ∣ b একটি বাক্য (সত্য বা মিথ্যা), আর a/b একটি সংখ্যা। যেমন 3 ∣ 12 সত্য, 5 ∤ 12, আর −4 ∣ 12 (কারণ 12 = (−4)(−3)). প্রতিটি a ≠ 0-এর জন্য a ∣ 0, কারণ 0 = a · 0. আবার 1 ∣ b আর b ∣ b (b ≠ 0) সবসময় সত্য। কিছু বই 0 ∣ 0-কেও সত্য ধরে; আমরা a ≠ 0 শর্ত রাখছি, যাতে ভাজক নিয়ে কথা সবসময় অর্থবহ থাকে।

প্রমাণ:

1. (ক) সংজ্ঞা অনুযায়ী b = as আর c = at কোনো পূর্ণসংখ্যা s, t-এর জন্য। তাহলে b + c = a(s + t), আর s + t পূর্ণসংখ্যা। — সংজ্ঞা, বণ্টন নিয়ম
2. (খ) b = as হলে bx = a(sx), আর sx পূর্ণসংখ্যা। — সংজ্ঞা
3. (গ) b = as আর c = bt হলে c = a(st). — গুণের সংযোগ নিয়ম
4. (ঘ) (খ) থেকে a ∣ bx আর a ∣ cy; তারপর (ক) থেকে a ∣ bx + cy. — (ক), (খ)
5. (ঙ) b = as আর b ≠ 0, তাই s ≠ 0, অর্থাৎ |s| ≥ 1. ফলে |b| = |a||s| ≥ |a|. — পূর্ণসংখ্যার পরম মান
6. (চ) b = 0 হলে b ∣ a সংজ্ঞায়িতই নয় (ভাজক অশূন্য), তাই a, b দুটিই অশূন্য। (ঙ) দুই দিকে লাগিয়ে |a| ≤ |b| আর |b| ≤ |a|, তাই |a| = |b|. ∎

(ঘ)-এর bx + cy ধাঁচের রাশিকে বলে b আর c-এর linear combination. “যে সংখ্যা দুটিকে ভাগ করে, সে তাদের যেকোনো linear combination-কেও ভাগ করে”, এই একটি বাক্যই পরের পর্ব ২১ “GCD আর Euclid-এর algorithm — Bézout আর extended Euclid”-এর মেরুদণ্ড। একটি সতর্কতা: উল্টোটা সত্য নয়। 6 ∣ 4 + 8, কিন্তু 6 ∤ 4 আর 6 ∤ 8.

২ · Division algorithm — ভাগফল আর ভাগশেষ কেন একটিই

সব ভাগ নিঃশেষ হয় না। ৩৬টি প্যাকেট ৫টি করে ভরলে 36 = 5 · 7 + 1. স্কুলে শেখা এই ভাগের নিয়মটি গাণিতিকভাবে লিখলে:

উপপাদ্যের দুটি অংশ: এমন q, r আছে (existence), আর তারা একটিই (uniqueness). অস্তিত্বের প্রমাণ well-ordering দিয়ে পর্ব ১১-এ করা হয়েছে (উপপাদ্য ৮.১): S = {n − dq ≥ 0}-এর ক্ষুদ্রতম সদস্যই r. এখানে বাকি অংশটি প্রমাণ করি। পর্ব ০৯-এর uniqueness proof-এর ছাঁচ: দুটি সমাধান ধরে দেখাই তারা সমান।

প্রমাণ (uniqueness):

1. ধরি n = dq + r = dq′ + r′, যেখানে 0 ≤ r < d আর 0 ≤ r′ < d. — দুটি সমাধান অনুমান
2. বিয়োগ করে d(q − q′) = r′ − r. তাই d ∣ r′ − r. — বিভাজ্যতার সংজ্ঞা
3. দুই অসমতা থেকে −d < r′ − r < d, অর্থাৎ |r′ − r| < d. — অসমতা যোগ
4. যদি r′ − r ≠ 0 হতো, তবে উপপাদ্য ১.২(ঙ) অনুযায়ী d ≤ |r′ − r|, যা ধাপ ৩-এর বিরোধী। তাই r′ = r. — contradiction
5. তখন d(q − q′) = 0, আর d ≠ 0, তাই q = q′. ∎ — শূন্য গুণফলের নিয়ম

সমীকরণটিকে d দিয়ে ভাগ করলে n/d = q + r/d, আর 0 ≤ r/d < 1. তাই q ঠিক n/d-এর নিচের পূর্ণসংখ্যা: q = ⌊n/d⌋, আর r = n − d⌊n/d⌋. ⌊ ⌋ হলো পর্ব ১৬-এর floor function. উদাহরণ: n = −17, d = 5 হলে −17/5 = −3.4, তাই q = ⌊−3.4⌋ = −4 আর r = −17 − 5(−4) = 3. অর্থাৎ −17 = 5 · (−4) + 3. গণিতের সংজ্ঞায় ভাগশেষ কখনো ঋণাত্মক নয়।

ঋণাত্মক সংখ্যা — Python বনাম C

প্রোগ্রামিং ভাষাগুলো এখানে একমত নয়। Python-এর // নিচের দিকে গোল করে (floor), তাই d > 0 হলে n % d সবসময় 0 থেকে d − 1-এর মধ্যে, ঠিক গণিতের r. একে বলে floored division. C (C99 থেকে), C++ আর Java ভাগফলকে শূন্যের দিকে কেটে ফেলে (truncated division), তাই সেখানে -17 / 5 হয় −3 আর -17 % 5 হয় −2. দুটিই n = dq + r মানে, কিন্তু শুধু প্রথমটি 0 ≤ r < d মানে। Python-এ // আর %-এর বিস্তারিত Python কোর্সের পর্ব ০৭-এ।

নিচের ব্লক চারটি উদাহরণে দুই নিয়ম পাশাপাশি দেখায়, −60 থেকে 60 পর্যন্ত প্রতিটি n আর 1 থেকে 12 পর্যন্ত প্রতিটি d-তে সব সম্ভাব্য q খুঁজে দেখে (q, r) ঠিক একটি কি না, তারপর উপপাদ্য ১.২-এর (গ) আর (ঘ) এলোমেলো সংখ্যায় পরীক্ষা করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
random.seed(20)

def c_style(a, b):          # C, C++, Java: the quotient is cut toward zero
    q = abs(a) // abs(b)
    if (a < 0) != (b < 0):
        q = -q
    return q, a - b * q

for a, b in [(45, 7), (-17, 5), (17, -5), (-7, 3)]:
    print(f"{a:>4} by {b:>2}   Python divmod: {str(divmod(a, b)):9}  C-style: {c_style(a, b)}")

def all_qr(n, d):           # every (q, r) with n = d*q + r and 0 <= r < d
    return [(q, n - d * q) for q in range(-abs(n) - 1, abs(n) + 2)
            if 0 <= n - d * q < d]

bad = [(n, d) for n in range(-60, 61) for d in range(1, 13)
       if all_qr(n, d) != [divmod(n, d)]]
print("pairs (n, d) without exactly one (q, r):", len(bad), "of", 121 * 12)

trans = comb = 0
for _ in range(3000):
    a = random.choice([i for i in range(-30, 31) if i != 0])
    k, m, x, y = (random.randint(-30, 30) for _ in range(4))
    b, c = a * k, a * k * m                       # so a | b and b | c
    trans += c % a == 0                           # claim: a | c
    c2 = a * m                                    # a | b and a | c2
    comb += (b * x + c2 * y) % a == 0             # claim: a | bx + c2*y
print("a|b, b|c gave a|c:", trans, "of 3000;  a|bx+cy:", comb, "of 3000")

  45 by  7   Python divmod: (6, 3)     C-style: (6, 3)
 -17 by  5   Python divmod: (-4, 3)    C-style: (-3, -2)
  17 by -5   Python divmod: (-4, -3)   C-style: (-3, 2)
  -7 by  3   Python divmod: (-3, 2)    C-style: (-2, -1)
pairs (n, d) without exactly one (q, r): 0 of 1452
a|b, b|c gave a|c: 3000 of 3000;  a|bx+cy: 3000 of 3000

৩ · মৌলিক সংখ্যা আর √n পর্যন্ত trial division

প্রথম কয়েকটি মৌলিক সংখ্যা 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. 2 একমাত্র জোড় মৌলিক, কারণ বাকি প্রতিটি জোড় সংখ্যাকে 2 ভাগ করে। পর্ব ০৮-এর Lemma ৬.১-এ দেখেছেন, 1-এর চেয়ে বড় প্রতিটি পূর্ণসংখ্যার অন্তত একটি মৌলিক ভাজক আছে। এখন প্রশ্ন: একটি সংখ্যা মৌলিক কি না, তা কীভাবে বুঝব? সরল উত্তর: 2 থেকে n − 1 পর্যন্ত প্রতিটি দিয়ে ভাগ করে দেখা। কিন্তু অর্ধেক কাজও লাগে না, এমনকি তার চেয়ে অনেক কম।

প্রমাণ:

1. n যৌগিক, তাই n = ab, যেখানে 1 < a ≤ b < n (ছোট গুণনীয়কটিকে a বলি)। — যৌগিকের সংজ্ঞা
2. যদি a > √n হতো, তবে b ≥ a > √n, তাই ab > √n · √n = n, যা ab = n-এর বিরোধী। তাই a ≤ √n. — contradiction
3. a > 1, তাই a-এর একটি মৌলিক ভাজক p আছে, আর উপপাদ্য ১.২(ঙ) অনুযায়ী p ≤ a ≤ √n. — পর্ব ০৮-এর Lemma ৬.১
4. p ∣ a আর a ∣ n, তাই p ∣ n. ∎ — উপপাদ্য ১.২(গ), transitivity

এই উপপাদ্যের ওপর দাঁড়ানো পদ্ধতির নাম trial division: d = 2, 3, 4, … করে d² ≤ n পর্যন্ত ভাগ করে দেখা, আর প্রতিবার ভাজক পেলে তা দিয়ে ভাগ করে আবার চালানো। শুধু মৌলিক d দিয়ে ভাগ করলেই যথেষ্ট: 9 যদি n-কে ভাগ করত, তবে 3-ও করত, আর 3 আগেই ধরা পড়ত। নিচের stepper বাজারঘরের একটি অর্ডার id 391-কে এভাবে ভাঙে।

1n = 391, √391 ≈ 19.772d = 2, 3, 53d = 7, 114d = 135d = 176বাকি 23: √23 ≈ 4.8

কিন্তু “কম কাজ” কতটা কম? √n পর্যন্ত ভাগ মানে মোটামুটি √n ধাপ। k অঙ্কের সংখ্যায় √n প্রায় 10^k/2, তাই প্রতি দুটি অঙ্ক বাড়লে কাজ প্রায় দশ গুণ বাড়ে। অঙ্কের সংখ্যার তুলনায় এই বৃদ্ধি exponential. নিচের ব্লক বাজারঘরের কয়েকটি (কাল্পনিক) অর্ডার id ভাঙে আর প্রতিটিতে কয়টি ভাগ লাগল তা গোনে; 2-এর পর শুধু বিজোড় d দেখে। শেষ লাইনে একটি ১৯ অঙ্কের সংখ্যার জন্য দরকারি ভাগের সংখ্যা শুধু হিসাব করা হয়েছে, চালানো হয়নি।

from math import isqrt

def factorize(n):
    """Trial division. Returns (prime factors, number of divisions tried)."""
    factors, tries, d = [], 0, 2
    while d * d <= n:
        tries += 1
        if n % d == 0:
            factors.append(d)
            n //= d
        else:
            d += 1 if d == 2 else 2      # after 2, only odd candidates
    if n > 1:
        factors.append(n)                 # no divisor up to its square root: prime
    return factors, tries

orders = [391, 2310, 65536, 9991, 1000003, 100160063, 2147483647]
for oid in orders:
    f, t = factorize(oid)
    shown = " x ".join(f"{p}^{f.count(p)}" if f.count(p) > 1 else str(p)
                       for p in sorted(set(f)))
    print(f"order {oid:>10} = {shown:<20} tries {t:>6}   isqrt {isqrt(oid)}")

big = 1000000016000000063               # (10**9 + 7) * (10**9 + 9)
print("for", big, "about", isqrt(big) // 2, "odd tries would be needed")

order        391 = 17 x 23              tries      9   isqrt 19
order       2310 = 2 x 3 x 5 x 7 x 11   tries      7   isqrt 48
order      65536 = 2^16                 tries     15   isqrt 256
order       9991 = 97 x 103             tries     49   isqrt 99
order    1000003 = 1000003              tries    500   isqrt 1000
order  100160063 = 10007 x 10009        tries   5004   isqrt 10007
order 2147483647 = 2147483647           tries  23170   isqrt 46340
for 1000000016000000063 about 500000003 odd tries would be needed

৪ · Unique factorization — পাটিগণিতের মৌলিক উপপাদ্য

391 = 17 · 23 আর 2310 = 2 · 3 · 5 · 7 · 11. কেউ কি অন্য কোনো মৌলিক সংখ্যার গুণফল হিসেবে 2310 লিখতে পারবেন? স্কুল থেকে আমরা ধরে নিই, না। কিন্তু “ধরে নেওয়া” আর “প্রমাণ” আলাদা, আর একটু পরেই দেখবেন এমন সংখ্যা-জগৎ আছে যেখানে এই কথা মিথ্যা।

“ক্রম বাদ দিলে একটিই” মানে দুটি গুণফলে প্রতিটি মৌলিক সমান সংখ্যকবার আসে; 2 · 3 · 2 আর 2 · 2 · 3 একই factorization. অস্তিত্বের অংশ strong induction দিয়ে পর্ব ১১-এ প্রমাণিত (উপপাদ্য ৩.১)। এখানে uniqueness প্রমাণ করব। বেশিরভাগ বই এর জন্য আগে Euclid-এর lemma প্রমাণ করে, যার প্রমাণে লাগে Bézout-এর অভেদ (পর্ব ২১-এ)। আমরা অন্য পথে যাব: পর্ব ১১-এর minimal counterexample কৌশলে সরাসরি uniqueness, তারপর তা থেকে Euclid-এর lemma. ফলে এই পর্ব নিজেই সম্পূর্ণ।

প্রমাণ (uniqueness, minimal counterexample): ধরি দাবি মিথ্যা। তাহলে যেসব n ≥ 2-এর দুটি ভিন্ন factorization আছে, তাদের সেট অশূন্য, আর well-ordering অনুযায়ী তার একটি ক্ষুদ্রতম সদস্য n আছে:

n = p₁p₂⋯p_r = q₁q₂⋯q_s

দুটি তালিকাই ছোট থেকে বড় সাজানো (p₁ ≤ p₂ ≤ ⋯, q₁ ≤ q₂ ≤ ⋯), আর তালিকা দুটি ভিন্ন।

1. n মৌলিক নয়। n = p মৌলিক হলে যেকোনো factorization p = q₁⋯q_s-এ q₁ ∣ p আর q₁ > 1, তাই q₁ = p, আর বাকি গুণফল 1, অর্থাৎ s = 1. তখন factorization একটিই, যা অনুমানের বিরোধী। তাই n যৌগিক, আর r ≥ 2, s ≥ 2. — মৌলিকের সংজ্ঞা
2. দুই তালিকায় কোনো সাধারণ মৌলিক নেই। যদি কোনো p_i = q_j = p হতো, দুই পাশ থেকে p কেটে দিলে n/p-এর দুটি ভিন্ন factorization পেতাম (প্রতিটি তালিকায় অন্তত একটি মৌলিক থাকে, কারণ r, s ≥ 2), আর 2 ≤ n/p < n. এটি n-এর ক্ষুদ্রতমতার বিরোধী। — minimality
3. বিশেষত p₁ ≠ q₁. দুই পাশের নাম বদলে ধরে নিই p₁ < q₁. — without loss of generality
4. m = n − p₁q₂⋯q_s নিই। একদিকে m = (q₁ − p₁)q₂⋯q_s > 0, আর p₁q₂⋯q_s ≥ 2 বলে m < n. অন্যদিকে m = p₁(p₂⋯p_r − q₂⋯q_s), তাই p₁ ∣ m, আর m ≥ p₁ ≥ 2. — বণ্টন নিয়ম, উপপাদ্য ১.২(ঙ)
5. m-এর factorization X: p₁, তারপর m/p₁-এর যেকোনো factorization (m/p₁ = 1 হলে শুধু p₁). X-এ p₁ আছে। — অস্তিত্ব, পর্ব ১১
6. m-এর factorization Y: q₁ − p₁-এর একটি factorization (এটি 1 হলে কিছু নয়), তারপর q₂, …, q_s. ধাপ ২ অনুযায়ী p₁ কোনো q_j নয়। আর p₁ যদি q₁ − p₁-এর factorization-এ থাকত, তবে p₁ ∣ q₁ − p₁, আর উপপাদ্য ১.২(ক) অনুযায়ী p₁ ∣ (q₁ − p₁) + p₁ = q₁; কিন্তু q₁ মৌলিক আর 1 < p₁ < q₁, অসম্ভব। তাই Y-তে p₁ নেই। — বিভাজ্যতার ধর্ম
7. X আর Y তাহলে m-এর দুটি ভিন্ন factorization, আর 2 ≤ m < n. এটি n-এর ক্ষুদ্রতমতার বিরোধী। তাই কোনো counterexample নেই। ∎ — proof by contradiction

লক্ষ করুন, ধাপ ৪-এ একটি বিয়োগ আছে, আর ধাপ ৬-এ বিয়োগফলের factorization নিয়েছি। এই বিয়োগ যে জগতে চলে না, সেখানে প্রমাণও চলে না। এই ধাঁচের প্রমাণ ১৯২০ আর ১৯৩০-এর দশকে কয়েকজন গণিতবিদ (Hasse, Lindemann, Zermelo প্রমুখ) প্রায় স্বাধীনভাবে প্রকাশ করেন বলে উল্লেখিত।

প্রমাণ:

1. a = 0 বা b = 0 হলে p তাকে ভাগ করে, শেষ। চিহ্ন বদলালে বিভাজ্যতা বদলায় না, তাই ধরি a, b > 0. a = 1 হলে p ∣ b, আর b = 1 হলে p ∣ a; তাই ধরি a, b ≥ 2. — সহজ ক্ষেত্র আলাদা করা
2. ab = pk কোনো k ≥ 1-এর জন্য। p, তারপর k-এর factorization (k = 1 হলে কিছু নয়) হলো ab-এর একটি factorization, যাতে p আছে। — অস্তিত্ব
3. a-এর factorization আর b-এর factorization পাশাপাশি লিখলে ab-এর আরেকটি factorization. উপপাদ্য ৪.১ অনুযায়ী দুটি একই, তাই এতেও p আছে: p হলো a-এর বা b-এর কোনো মৌলিক গুণনীয়ক। — uniqueness
4. তাই p ∣ a অথবা p ∣ b. ∎

শর্ত “p মৌলিক” বাদ দেওয়া যায় না: 6 ∣ 4 · 9 = 36, কিন্তু 6 ∤ 4 আর 6 ∤ 9. প্রথাগত পথে (পর্ব ২১-এ) Euclid-এর lemma আগে Bézout দিয়ে প্রমাণ হয়, তারপর তা দিয়ে uniqueness আসে “কেটে দেওয়ার” যুক্তিতে। নিচের stepper সেই যুক্তি একটি উদাহরণে দেখায়। দুটি পথই বৈধ, শর্ত শুধু একটি: যে পথে যাবেন, সেখানে Euclid-এর lemma আর uniqueness-এর কোনোটিকে অন্যটি দিয়ে প্রমাণ করে আবার উল্টোটা করা চলবে না, নইলে যুক্তি চক্রাকার হয়ে যায়।

1A: 2 · 2 · 3 · 3 · 5 · 72B: 3 · 7 · 2 · 5 · 3 · 23p ∣ q₁q₂⋯ ⇒ p ∣ কোনো qⱼ4qⱼ মৌলিক ⇒ p = qⱼ5দুই পাশ থেকে কেটে দিন6H = {1, 5, 9, 13, …}

H-এর এই উদাহরণ (Hilbert-এর নামে পরিচিত বলে উল্লেখিত) দেখায়, unique factorization “স্পষ্ট” নয়, ℤ-এর একটি বিশেষ ধর্ম। আমাদের প্রমাণের ধাপ ৪-এ m = n − p₁q₂⋯q_s নেওয়া হয়েছিল। H-এ 441 − 9 · 21 = 252 = 12 · 21, আর 252 বা 12 কোনোটিই H-এ নেই। বিয়োগে H বন্ধ নয়, আর সেখানেই প্রমাণ ভেঙে পড়ে।

৫ · Eratosthenes-এর ছাঁকনি — একসঙ্গে অনেক মৌলিক

একটি সংখ্যা যাচাইয়ের জন্য trial division ঠিক আছে। কিন্তু ধরুন বাজারঘরের hash table-এর আকার বাছাইয়ের জন্য এক লাখ পর্যন্ত সব মৌলিক সংখ্যার তালিকা দরকার। প্রতিটিতে আলাদা trial division-এর বদলে প্রাচীন একটি কৌশল অনেক দ্রুত: চালুনিতে চাল ছাঁকার মতো যৌগিক সংখ্যাগুলো ঝেড়ে ফেলা।

কেন সঠিক: (১) কোনো মৌলিক কখনো কাটা পড়ে না, কারণ কাটা প্রতিটি সংখ্যা kp আকারের, যেখানে k ≥ p ≥ 2, তাই যৌগিক। (২) N পর্যন্ত প্রতিটি যৌগিক m কাটা পড়ে: উপপাদ্য ৩.২ অনুযায়ী তার ক্ষুদ্রতম মৌলিক ভাজক p ≤ √m ≤ √N, আর m = pk যেখানে k ≥ p (কারণ k-এর প্রতিটি মৌলিক ভাজক ≥ p), তাই m ≥ p², আর p-এর পালায় m কাটা পড়ে। p² থেকে শুরু করা যায় কারণ p-এর ছোট গুণিতক kp (k < p)-এর একটি মৌলিক ভাজক p-এর চেয়ে ছোট, তাই সেগুলো আগেই কাটা।

12 … 50, √50 ≈ 7.072p = 2: 4, 6, 8, …, 503p = 3: 9, 12, 15, …, 484p = 5: 25, 30, …, 505p = 7: 496p = 11: 121 > 50, থামুন

খরচ: p-এর পালায় প্রায় N/p-টি কাটা, তাই মোট কাজ প্রায় N(1/2 + 1/3 + 1/5 + ⋯), যোগফল √N পর্যন্ত মৌলিকগুলোর ওপর। মৌলিক সংখ্যার উল্টোগুলোর যোগফল খুব ধীরে বাড়ে, মোটামুটি ln ln N-এর মতো (Mertens-এর একটি উপপাদ্য; প্রমাণ এখানে দেওয়া হলো না), তাই ছাঁকনির খরচ প্রায় N ln ln N ধাপ, প্রায় রৈখিক। এর বিপরীতে N পর্যন্ত প্রতিটি সংখ্যায় আলাদা trial division-এ প্রায় N√N-এর মাপে কাজ। Linear sieve, segmented sieve আর প্রতিটি সংখ্যার ক্ষুদ্রতম মৌলিক ভাজক রাখার কৌশল, কোডসহ, DSA কোর্সের পর্ব ৬২-এ। নিচের ব্লক 10⁵ পর্যন্ত ছাঁকনি চালায়, কাটার ধাপ গোনে, আর পরের অংশের জন্য মৌলিক সংখ্যার গণনার একটি ছক বানায়।

from math import log, isqrt

N = 100_000
is_p = bytearray([1]) * (N + 1)
is_p[0] = is_p[1] = 0
crossings = 0
for p in range(2, isqrt(N) + 1):
    if is_p[p]:
        for m in range(p * p, N + 1, p):     # start at p*p: smaller multiples are done
            is_p[m] = 0
            crossings += 1
primes = [i for i in range(N + 1) if is_p[i]]
print("primes up to", N, ":", len(primes), "  last three:", primes[-3:])
print("cross-out steps:", crossings, "  N ln ln N =", round(N * log(log(N))))

print(f"{'x':>7} {'pi(x)':>6} {'x/ln x':>8} {'ratio':>6} {'sum 1/ln k':>11}")
i, s, k = 0, 0.0, 2
for x in [10, 100, 1000, 10_000, 100_000]:
    while i < len(primes) and primes[i] <= x:
        i += 1
    while k <= x:
        s += 1 / log(k)
        k += 1
    print(f"{x:>7} {i:>6} {x / log(x):>8.1f} {i / (x / log(x)):>6.3f} {s:>11.1f}")

primes up to 100000 : 9592   last three: [99971, 99989, 99991]
cross-out steps: 193078   N ln ln N = 244347
      x  pi(x)   x/ln x  ratio  sum 1/ln k
     10      4      4.3  0.921         6.1
    100     25     21.7  1.151        30.0
   1000    168    144.8  1.161       177.4
  10000   1229   1085.7  1.132      1245.9
 100000   9592   8685.9  1.104      9629.6

৬ · মৌলিক সংখ্যার বণ্টন — অসীম, বিরল আর বড় ফাঁক

পর্ব ০৮-এ Euclid-এর প্রমাণ দেখেছেন: সসীম তালিকা p₁, …, p_k ধরে নিলে N = p₁⋯p_k + 1-এর একটি মৌলিক ভাজক থাকে, যা তালিকার কোনোটি হতে পারে না, কারণ প্রতিটি p_i দিয়ে ভাগ করলে ভাগশেষ 1. তাই মৌলিক সংখ্যা অসীম। কিন্তু উপরের ছক দেখায় তারা ক্রমশ বিরল: প্রথম ১০০-তে ২৫টি (চারটিতে একটি), প্রথম এক লাখে ৯,৫৯২টি (প্রায় দশটিতে একটি)। কত দ্রুত বিরল হয়?

“~” চিহ্নটি সাবধানে পড়ুন: পার্থক্য ছোট হয় এমন নয়, শুধু অনুপাত 1-এর দিকে যায়। ছকে x = 10⁵-এ পার্থক্য প্রায় ৯০৬, তবু অনুপাত 1.104. গ্রহণযোগ্য অনুভূতি: x-এর কাছাকাছি একটি “এলোমেলো” সংখ্যা মৌলিক হওয়ার সম্ভাবনা মোটামুটি 1/ln x, আর পাশাপাশি দুটি মৌলিকের গড় দূরত্ব প্রায় ln x. ln 10⁵ ≈ 11.5, আর বাস্তবে 10⁵/9592 ≈ 10.4. শেষ কলামের ∑ 1/ln k এই সম্ভাবনা-ভাবনারই যোগফল, আর সেটি আরও ভালো অনুমান দেয়।

যত খুশি বড় ফাঁক

মৌলিক গড়ে ln x দূরে দূরে, কিন্তু ফাঁক কখনো কখনো অনেক বড় হয়। পরপর দুটি মৌলিকের পার্থক্যকে বলে prime gap. কোনো ঊর্ধ্বসীমা কি আছে? না।

প্রমাণ:

1. 2 ≤ k ≤ n যেকোনো একটি k নিই। n! = 1 · 2 ⋯ n-এর একটি গুণনীয়ক k, তাই k ∣ n!. — factorial-এর সংজ্ঞা
2. k ∣ k, তাই উপপাদ্য ১.২(ক) অনুযায়ী k ∣ n! + k. — বিভাজ্যতার ধর্ম
3. 1 < k < n! + k, তাই n! + k-এর একটি ভাজক আছে যা 1-ও নয়, সংখ্যাটি নিজেও নয়। তাই n! + k যৌগিক। ∎ — যৌগিকের সংজ্ঞা

যেমন n = 5: 122, 123, 124, 125, চারটি টানা যৌগিক, যাদের ভাজক যথাক্রমে 2, 3, 4, 5. তাই যত বড় ফাঁক চান, তত বড় n নিন। তবে n! বিশাল, আর বাস্তবে একই দৈর্ঘ্যের ফাঁক অনেক আগেই আসে। অন্যদিকে ফাঁক খুব বেশি বড়ও হতে পারে না: Bertrand-এর postulate বলে প্রতিটি n ≥ 1-এর জন্য n < p ≤ 2n সীমায় একটি মৌলিক আছে (Chebyshev ১৮৫২ সালের দিকে প্রমাণ করেন বলে উল্লেখিত)। নিচের ব্লক তিনটি factorial-দৌড় যাচাই করে, তারপর এক লাখ পর্যন্ত প্রতিটি নতুন রেকর্ড ফাঁক, twin prime জোড়ার সংখ্যা আর ছোট সংখ্যায় Goldbach-এর দাবি পরীক্ষা করে।

from math import factorial, isqrt

def spf(m):                         # smallest prime factor, by trial division
    for d in range(2, isqrt(m) + 1):
        if m % d == 0:
            return d
    return m

for n in [5, 7, 10]:
    start = factorial(n) + 2
    run = [spf(start + i) for i in range(n - 1)]
    print(f"n={n}: {start}..{start + n - 2}  smallest factors {run}")

N = 100_000
s = bytearray([1]) * (N + 1)
s[0] = s[1] = 0
for p in range(2, isqrt(N) + 1):
    if s[p]:
        s[p * p::p] = bytearray(len(range(p * p, N + 1, p)))
primes = [i for i in range(N + 1) if s[i]]

best = 0
for a, b in zip(primes, primes[1:]):
    if b - a > best:
        best = b - a
        print(f"record gap {best:>2}: {a} .. {b}")
twins = sum(1 for a, b in zip(primes, primes[1:]) if b - a == 2)
print("twin prime pairs below", N, ":", twins)
ps = set(primes)
ok = all(any(n - p in ps for p in primes if p <= n // 2) for n in range(4, 10_001, 2))
print("every even n in 4..10000 is p + q with p, q prime:", ok)

n=5: 122..125  smallest factors [2, 3, 2, 5]
n=7: 5042..5047  smallest factors [2, 3, 2, 5, 2, 7]
n=10: 3628802..3628810  smallest factors [2, 3, 2, 5, 2, 7, 2, 3, 2]
record gap  1: 2 .. 3
record gap  2: 3 .. 5
record gap  4: 7 .. 11
record gap  6: 23 .. 29
record gap  8: 89 .. 97
record gap 14: 113 .. 127
record gap 18: 523 .. 541
record gap 20: 887 .. 907
record gap 22: 1129 .. 1151
record gap 34: 1327 .. 1361
record gap 36: 9551 .. 9587
record gap 44: 15683 .. 15727
record gap 52: 19609 .. 19661
record gap 72: 31397 .. 31469
twin prime pairs below 100000 : 1224
every even n in 4..10000 is p + q with p, q prime: True

৭ · খোলা প্রশ্ন — যা এখনো কেউ প্রমাণ করেননি

মৌলিক সংখ্যার প্রশ্নগুলো বলতে সহজ, প্রমাণে ভয়ংকর কঠিন। পর্ব ০৯-এ দেখেছেন, হাজার হাজার উদাহরণে যাচাই কোনো প্রমাণ নয়; এখানে দুটি বিখ্যাত উদাহরণ সংক্ষেপে।

• Twin prime conjecture: p আর p + 2 দুটিই মৌলিক, এমন জোড়া (যেমন 11, 13 বা 29, 31) অসীম সংখ্যক। এক লাখের নিচে ১,২২৪টি জোড়া আছে, কিন্তু অসীম কি না জানা নেই। ২০১৩ সালে Yitang Zhang প্রমাণ করেন, কোনো একটি নির্দিষ্ট সীমার (সাত কোটির নিচে) ছোট ফাঁক অসীমবার আসে; পরে James Maynard আর একটি সম্মিলিত অনলাইন গবেষণা প্রকল্প (Polymath) সেই সীমা নামিয়ে 246-এ আনেন বলে উল্লেখিত। 2-এ নামানোই twin prime conjecture.
• Goldbach conjecture: ২-এর চেয়ে বড় প্রতিটি জোড় সংখ্যা দুটি মৌলিকের যোগফল। ব্লকটি 10,000 পর্যন্ত যাচাই করেছে; কম্পিউটারে প্রায় 4 × 10¹⁸ পর্যন্ত যাচাইয়ের ফল প্রকাশিত হয়েছে বলে জানা যায়। দুর্বলতর রূপ (৫-এর চেয়ে বড় প্রতিটি বিজোড় সংখ্যা তিনটি মৌলিকের যোগফল) ২০১৩ সালে Harald Helfgott প্রমাণ করেছেন বলে দাবি করা হয়, আর সেটি ব্যাপকভাবে গৃহীত বলে উল্লেখিত।

আরেকটি সহজে বলা যায় এমন open problem: প্রতিটি n ≥ 1-এর জন্য n² আর (n + 1)²-এর মাঝে কি সবসময় একটি মৌলিক আছে (Legendre-এর অনুমান)? এটিও আজ পর্যন্ত অপ্রমাণিত। এই প্রশ্নগুলো থেকে শিক্ষা: বিশাল যাচাই আস্থা দেয়, কিন্তু উপপাদ্য হয় শুধু প্রমাণে।

৮ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই বিষয়ের যে ধাঁচের অঙ্ক আসে, তার চারটি পূর্ণ সমাধান। প্রতিটি সংখ্যা scratch-এ Python দিয়ে মেলানো।

অঙ্ক ১: 997 আর 1001 মৌলিক কি না যাচাই করুন

1. √997 ≈ 31.6, তাই 31 পর্যন্ত মৌলিক দেখলেই হয়: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, মোট ১১টি। কোনোটিই 997-কে ভাগ করে না (যেমন 997 = 7 · 142 + 3, 997 = 31 · 32 + 5). তাই 997 মৌলিক।
2. 1001: 7 · 143 = 1001, আর 143 = 11 · 13. তাই 1001 = 7 · 11 · 13, যৌগিক। ভাজক পেলেই থামা যায়; বাকি ভাগ লাগে না।

অঙ্ক ২: n = −101, d = 7-এর q আর r বের করুন; C-তে -101 % 7 কত?

−101/7 ≈ −14.43, তাই q = ⌊−14.43⌋ = −15, আর r = −101 − 7(−15) = −101 + 105 = 4. যাচাই: 7 · (−15) + 4 = −101, আর 0 ≤ 4 < 7. Python-এর divmod(-101, 7)-ও (-15, 4). C-তে ভাগফল শূন্যের দিকে কাটা হয়, −14, তাই -101 % 7 = −101 − 7(−14) = −3.

অঙ্ক ৩: 720-এর কয়টি ধনাত্মক ভাজক?

1. Factorization: 720 = 2⁴ · 3² · 5.
2. d ∣ 720 হলে d-এর প্রতিটি মৌলিক ভাজক 720-কেও ভাগ করে, আর unique factorization অনুযায়ী d = 2^a3^b5^c, যেখানে 0 ≤ a ≤ 4, 0 ≤ b ≤ 2, 0 ≤ c ≤ 1. উল্টোভাবে এমন প্রতিটি সংখ্যা 720-কে ভাগ করে, আর ভিন্ন (a, b, c) ভিন্ন সংখ্যা দেয় (আবারও uniqueness).
3. তাই ভাজকের সংখ্যা (4 + 1)(2 + 1)(1 + 1) = 30. সাধারণ সূত্র: n = p₁^a₁⋯p_k^a_k হলে ভাজকের সংখ্যা (a₁ + 1)⋯(a_k + 1).

অঙ্ক ৪: 100!-এর শেষে কয়টি শূন্য?

1. প্রতিটি শেষ শূন্য একটি 10 = 2 · 5 গুণনীয়ক। unique factorization অনুযায়ী শূন্যের সংখ্যা = min(100!-এ 2-এর ঘাত, 5-এর ঘাত), আর 5 কম আসে।
2. 1 থেকে 100-এ 5-এর গুণিতক ⌊100/5⌋ = 20টি, আর তাদের মধ্যে 25-এর গুণিতক ⌊100/25⌋ = 4টি একটি বাড়তি 5 দেয়। 125 > 100, তাই থামি।
3. মোট 20 + 4 = 24টি শূন্য। এই নিয়মটি (Legendre-এর সূত্র) একইভাবে দেয় 50!-এ 2-এর ঘাত 25 + 12 + 6 + 3 + 1 = 47.

প্রমাণের ভুল ধরুন: “d ∣ a² হলে d ∣ a”

একজন লিখলেন: “দাবি: d ≥ 2 আর d ∣ a² হলে d ∣ a. প্রমাণ: d-এর প্রতিটি মৌলিক ভাজক p, a² = a · a-কে ভাগ করে, তাই Euclid-এর lemma অনুযায়ী p ∣ a. d-এর সব মৌলিক ভাজক a-কে ভাগ করে, তাই d ∣ a. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: শেষ বাক্যে। “d-এর প্রতিটি মৌলিক ভাজক a-কে ভাগ করে” থেকে d ∣ a আসে না, কারণ একটি মৌলিক d-তে কতবার আছে (ঘাত) তা ভুলে যাওয়া হয়েছে। Counterexample: d = 4, a = 2. 4 ∣ 4 = a², d-এর একমাত্র মৌলিক ভাজক 2 আর 2 ∣ 2, অথচ 4 ∤ 2. সঠিক দাবি: d squarefree (কোনো মৌলিকের বর্গ d-কে ভাগ করে না) হলে d ∣ a² ⇒ d ∣ a; আর সাধারণভাবে p মৌলিক হলে p ∣ a² ⇒ p ∣ a.

৯ · AI-এর যুগে — মৌলিক সংখ্যার দাবি আর প্রমাণ যাচাই

“এই সংখ্যাটি কি মৌলিক?” বা “এই উপপাদ্য প্রমাণ করুন” প্রশ্নে AI সহকারী আত্মবিশ্বাসী উত্তর দেয়। কিন্তু সংখ্যাতত্ত্বে ছোট ভুল পুরো উত্তর উল্টে দেয়, আর কিছু ভুল নিয়মিত আসে:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• দাবি করা factorization নিজে গুণ করে মিলিয়েছি, আর প্রতিটি গুণনীয়ক মৌলিক কি না যাচাই করেছি
• √n-এর সীমায় off-by-one নেই; মৌলিকের বর্গ দিয়ে কোড পরীক্ষা করেছি
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত (মৌলিক, d > 0, a ≠ 0) মিলিয়েছি
• প্রমাণে কোনো ফল নিজেকেই প্রমাণে ব্যবহার করেনি, আর কোনো ধাপে ঘাত বা গুণিতা হারায়নি
• ঋণাত্মক সংখ্যার ভাগশেষ সংজ্ঞা আর ভাষা দুই দিক থেকে মিলিয়েছি
• ছোট উদাহরণে brute force চালিয়েছি, আর সাল ও রেকর্ড বিশ্বস্ত উৎসে মিলিয়েছি

সবচেয়ে সস্তা প্রথম পরীক্ষা: AI যে factorization বা মৌলিক তালিকা দিল, তা §৩-এর factorize বা §৫-এর ছাঁকনিতে নিজে চালিয়ে মেলান। একটি অমিলই পুরো উত্তরকে সন্দেহজনক করে।