Modular arithmetic — ঘড়ির গণিত আর modular exponentiation

১ · ঘড়ির গণিত — congruence কী

দেয়ালঘড়িতে এখন ৯টা। ৫ ঘণ্টা পরে কয়টা বাজবে? কেউ “১৪টা” বলেন না, বলেন “২টা”। ঘড়ির কাঁটা 12-এ পৌঁছে আবার শুরু থেকে গোনে, তাই ঘড়ির কাছে 14 আর 2 একই জিনিস। সপ্তাহের দিনও তাই: আজ বৃহস্পতিবার হলে ঠিক ৭ দিন, ১৪ দিন বা ৭০ দিন পরেও বৃহস্পতিবার। ট্রেনের সময়সূচি, পরীক্ষার রোল নম্বর দিয়ে বেঞ্চ ভাগ করা, প্রতি তিন দিন পরপর পালা করে বাজার করা, সবখানে আমরা আসলে একটি সংখ্যাকে কোনো নির্দিষ্ট সংখ্যা দিয়ে ভাগ করে শুধু ভাগশেষ মনে রাখি। এই হিসাবের গণিতই modular arithmetic, বাংলায় অনেকে বলেন “ঘড়ির গণিত”।

বাজারঘরে এই হিসাব সব জায়গায়। ঢাকা থেকে সিলেটে ভ্যান যায় প্রতি ১১ দিনে একবার; গ্রাহকের id-কে 16টি সার্ভারের একটিতে পাঠাতে লাগে id mod 16; অর্ডার নম্বরের শেষে একটি check digit বসে, যা টাইপের ভুল ধরে। পর্ব ২০ “বিভাজ্যতা আর মৌলিক সংখ্যা — division algorithm আর unique factorization”-এ ভাগ আর ভাগশেষের ভিত্তি তৈরি হচ্ছে, আর পর্ব ২১ “GCD আর Euclid-এর algorithm — Bézout আর extended Euclid”-এ gcd. এই পর্বে সেই ভাগশেষ দিয়ে হিসাব করার নিয়মগুলো প্রমাণসহ দাঁড় করানো হবে।

চিহ্নগুলো পড়ার নিয়ম: “∣” মানে “ভাগ করে” (m ∣ n মানে n = mk কোনো পূর্ণসংখ্যা k-এর জন্য), “∤” মানে “ভাগ করে না”, আর “≡” পড়া হয় “congruent”. উদাহরণ: 15 ≡ 3 (mod 12), কারণ 15 − 3 = 12; 100 ≡ 2 (mod 7), কারণ 98 = 7 · 14; −3 ≡ 4 (mod 7), কারণ −3 − 4 = −7; আর 17 ≢ 3 (mod 5), কারণ 14-কে 5 ভাগ করে না।

এর পাশেই আছে mod অপারেশন। Division algorithm বলে, যেকোনো পূর্ণসংখ্যা a আর ধনাত্মক m-এর জন্য একমাত্র q আর r আছে, যাতে a = qm + r আর 0 ≤ r < m. এই r-ই a mod m. এর অস্তিত্বের প্রমাণ well-ordering দিয়ে পর্ব ১১-এ হয়েছে, আর একমাত্রতার প্রমাণ পর্ব ২০-এর বিষয়। দুটি জিনিস আলাদা রাখুন: “a ≡ b (mod m)” একটি সম্পর্ক (সত্য বা মিথ্যা একটি বাক্য), আর “a mod m” একটি সংখ্যা (একটি ফাংশনের মান)।

প্রমাণ: তিনটি সমতুল্য দেখাতে (ক) ⇔ (খ) আর (ক) ⇔ (গ) দেখানোই যথেষ্ট।

1. (ক) ⇔ (খ): m ∣ (a − b) মানে কোনো k-এর জন্য a − b = km, অর্থাৎ a = b + km. দুই দিকেই একই সমীকরণ। — ∣-এর সংজ্ঞা
2. (গ) ⇒ (ক): ধরি a = q₁m + r আর b = q₂m + r, একই ভাগশেষ r. বিয়োগ করলে a − b = (q₁ − q₂)m, তাই m ∣ (a − b). — division algorithm
3. (ক) ⇒ (গ): ধরি b = qm + r, 0 ≤ r < m, আর (খ) অনুযায়ী a = b + km. তাহলে a = (q + k)m + r, যেখানে এখনো 0 ≤ r < m. — বীজগণিত
4. Division algorithm-এর ভাগশেষ একমাত্র, তাই a-এর ভাগশেষও এই r. অর্থাৎ a mod m = r = b mod m. ∎ — ভাগশেষের একমাত্রতা

রূপ (গ) প্রতিদিনের অর্থ দেয় (“একই ভাগশেষ”), রূপ (খ) প্রমাণে সবচেয়ে কাজের (“m-এর কোনো গুণিতক যোগ করলে আসে”), আর সংজ্ঞার রূপ (ক) ঋণাত্মক সংখ্যাতেও কোনো ঝামেলা ছাড়া কাজ করে।

২ · Congruence class আর ℤ_m

সপ্তাহের হিসাবে দিন 4, 11, 18, 25, আর পেছনের দিকে −3, −10, সবাই একই বার। ঘড়ির চোখে এরা একটি দল। প্রতিটি পূর্ণসংখ্যা ঠিক একটি দলে পড়ে, আর দল আছে ঠিক ৭টি। গণিতের ভাষায় এটি বলে, ≡ (mod m) একটি equivalence relation: এমন সম্পর্ক যা reflexive, symmetric আর transitive. Relation-এর এই ধর্মগুলো প্রমাণসহ পর্ব ৫২ “Relation আর তার ধর্ম — reflexive, symmetric, transitive”-এ, আর equivalence relation কীভাবে একটি সেটকে partition করে তা পর্ব ৫৫ “Equivalence relation আর partition”-এ আসবে। এখানে congruence-এর জন্য সরাসরি প্রমাণ দেখি।

প্রমাণ:

1. (ক) a − a = 0 = 0 · m, তাই m ∣ 0. — ∣-এর সংজ্ঞা, k = 0
2. (খ) a − b = km হলে b − a = (−k)m. — দুই পাশে −1 দিয়ে গুণ
3. (গ) a − b = km আর b − c = lm হলে যোগ করে a − c = (k + l)m. ∎ — দুটি সমীকরণ যোগ

প্রমাণ:

1. প্রতিটি পূর্ণসংখ্যা কোনো একটিতে আছে: যেকোনো x-এর জন্য r = x mod m নিলে 0 ≤ r ≤ m − 1 আর উপপাদ্য ১.২(গ) অনুযায়ী x ≡ r, তাই x ∈ [r]. — division algorithm
2. এই m-টি class আলাদা: 0 ≤ r < s ≤ m − 1 হলে 0 < s − r < m, তাই m ∤ (s − r), অর্থাৎ r ≢ s আর r ∉ [s]. — m-এর চেয়ে ছোট ধনাত্মক সংখ্যাকে m ভাগ করে না
3. দুটি class হয় সমান, নয়তো একেবারে আলাদা: z যদি [r] আর [s] দুটিতেই থাকে, তবে z ≡ r আর z ≡ s, তাই symmetric আর transitive ধর্মে r ≡ s, যা ধাপ ২-এর সঙ্গে বিরোধ। ∎ — উপপাদ্য ২.১, contradiction

প্রতিটি class থেকে একটি করে প্রতিনিধি নিলে পাওয়া যায় একটি complete residue system; সবচেয়ে প্রচলিত বাছাই 0, 1, …, m − 1, যাদের বলে least non-negative residue. কিন্তু অন্য বাছাইও বৈধ: mod 7-এ {−3, −2, −1, 0, 1, 2, 3} একটি complete residue system, আর ঋণাত্মক প্রতিনিধি অনেক সময় হিসাব ছোট করে (যেমন 6 ≡ −1). নিচের ছবিতে mod 7-এর ঘড়ি: সাতটি ঘর সাতটি class, আর বাজারঘরের ১১ দিনের ভ্যান-রুট প্রতিবার কাঁটাকে ৪ ঘর এগিয়ে দেয়, কারণ 11 ≡ 4 (mod 7).

এখানে একটি সূক্ষ্ম প্রশ্ন লুকিয়ে আছে। [a] + [b] = [a + b] লিখতে গেলে নিশ্চিত হতে হবে যে ফল প্রতিনিধি বাছাইয়ের ওপর নির্ভর করে না: mod 7-এ [4] + [5]-এর জন্য 4 আর 5 নিলে 9 ∈ [2], আর 11 আর −2 নিলেও 9 ∈ [2] পাওয়া চাই। গণিতে একে বলে অপারেশনটি well-defined. পরের অংশের উপপাদ্য ঠিক এই নিশ্চয়তাটুকু দেয়।

৩ · mod m-এ যোগ, বিয়োগ আর গুণ — কোনটি চলে, কোনটি চলে না

প্রমাণ: উপপাদ্য ১.২(খ) অনুযায়ী a = b + km আর c = d + lm কোনো পূর্ণসংখ্যা k, l-এর জন্য।

1. (ক) a + c = (b + d) + (k + l)m, তাই m ∣ ((a + c) − (b + d)). — যোগ আর বণ্টন
2. (খ) a − c = (b − d) + (k − l)m. — একইভাবে
3. (গ) ac = (b + km)(d + lm) = bd + (bl + kd + klm)m. বন্ধনীর রাশি একটি পূর্ণসংখ্যা, তাই ac ≡ bd. ∎ — গুণ খুলে m সাধারণ নেওয়া

প্রমাণ: k-এর ওপর mathematical induction (পর্ব ১০)। ভিত্তি: a⁰ = 1 ≡ 1 = b⁰. ধাপ: a^k ≡ b^k ধরে নিলে উপপাদ্য ৩.১(গ)-এ a^k · a ≡ b^k · b, অর্থাৎ a^k+1 ≡ b^k+1. Polynomial-এর জন্য প্রতিটি পদ c_iaⁱ ≡ c_ibⁱ, তারপর উপপাদ্য ৩.১(ক) দিয়ে পদগুলো যোগ। শেষ দাবিটি এসেছে a ≡ a mod m থেকে। ∎

এর ব্যবহারিক অর্থ বিশাল: হিসাবের যেকোনো মাঝপথে ভাগশেষ নিয়ে সংখ্যা ছোট রাখা যায়, ফল বদলায় না। বাজারঘরের তিনটি অর্ডারের মোট পরিমাণ 98,765 + 43,217 + 55,555 টাকা; মোট পরিমাণ mod 9 জানতে যোগফল না করেও প্রতিটির ভাগশেষ (8, 8, 7) যোগ করে 23 ≡ 5 (mod 9) পাওয়া যায়। কিন্তু দুটি জায়গায় সাধারণ বীজগণিতের অভ্যাস এখানে ভুল করায়।

নিচের ব্লক ℤ₆ আর ℤ₇-এর ছক ছাপে, তারপর m = 2 থেকে 12 পর্যন্ত দেখে গুণের ছকের কয়টি সারিতে 1 আছে আর কোথায় zero divisor (এমন দুটি অশূন্য সংখ্যা, যাদের গুণফল 0) আছে। শেষে নির্দিষ্ট seed-এ ১০,০০০টি এলোমেলো উদাহরণে উপপাদ্য ৩.১ পরীক্ষা করে, ঋণাত্মক সংখ্যাসহ। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
random.seed(22)

def show(m, op, sym):
    print(f"{sym}_{m} | " + " ".join(str(j) for j in range(m)))
    print("-" * (2 * m + 6))
    for i in range(m):
        print(f"  {i}  | " + " ".join(str(op(i, j) % m) for j in range(m)))

show(6, lambda a, b: a + b, "+")
show(6, lambda a, b: a * b, "·")
show(7, lambda a, b: a * b, "·")

for m in range(2, 13):
    units = [a for a in range(1, m) if any(a * x % m == 1 for x in range(m))]
    zd = [(a, b) for a in range(1, m) for b in range(a, m) if a * b % m == 0]
    print(f"m={m:2}: 1 আছে {len(units):2}/{m-1:2} সারিতে;",
          "শূন্য-ভাজক যেমন", zd[0] if zd else "নেই")

ok = 0                                  # Theorem 3.1 on random data
for _ in range(10000):
    m = random.randint(2, 50)
    a, c = random.randint(-999, 999), random.randint(-999, 999)
    b = a + m * random.randint(-50, 50)     # b ≡ a (mod m)
    d = c + m * random.randint(-50, 50)     # d ≡ c (mod m)
    ok += ((a + c) - (b + d)) % m == 0 and (a * c - b * d) % m == 0
print("a≡b, c≡d ⇒ a+c≡b+d আর ac≡bd:", ok, "of 10000")

+_6 | 0 1 2 3 4 5
------------------
  0  | 0 1 2 3 4 5
  1  | 1 2 3 4 5 0
  …
  5  | 5 0 1 2 3 4
·_6 | 0 1 2 3 4 5
------------------
  0  | 0 0 0 0 0 0
  1  | 0 1 2 3 4 5
  2  | 0 2 4 0 2 4
  3  | 0 3 0 3 0 3
  4  | 0 4 2 0 4 2
  5  | 0 5 4 3 2 1
·_7 | 0 1 2 3 4 5 6
  …
  3  | 0 3 6 2 5 1 4
  …
m= 2: 1 আছে  1/ 1 সারিতে; শূন্য-ভাজক যেমন নেই
m= 3: 1 আছে  2/ 2 সারিতে; শূন্য-ভাজক যেমন নেই
m= 4: 1 আছে  2/ 3 সারিতে; শূন্য-ভাজক যেমন (2, 2)
m= 5: 1 আছে  4/ 4 সারিতে; শূন্য-ভাজক যেমন নেই
m= 6: 1 আছে  2/ 5 সারিতে; শূন্য-ভাজক যেমন (2, 3)
m= 7: 1 আছে  6/ 6 সারিতে; শূন্য-ভাজক যেমন নেই
m= 8: 1 আছে  4/ 7 সারিতে; শূন্য-ভাজক যেমন (2, 4)
m= 9: 1 আছে  6/ 8 সারিতে; শূন্য-ভাজক যেমন (3, 3)
m=10: 1 আছে  4/ 9 সারিতে; শূন্য-ভাজক যেমন (2, 5)
m=11: 1 আছে 10/10 সারিতে; শূন্য-ভাজক যেমন নেই
m=12: 1 আছে  4/11 সারিতে; শূন্য-ভাজক যেমন (2, 6)
a≡b, c≡d ⇒ a+c≡b+d আর ac≡bd: 10000 of 10000

৪ · বিভাজ্যতার পরীক্ষা — 3, 9 আর 11 কেন কাজ করে

স্কুলে শেখা নিয়ম: “অঙ্কগুলোর যোগফল 9 দিয়ে বিভাজ্য হলে সংখ্যাটিও 9 দিয়ে বিভাজ্য।” কিন্তু কেন? অনুসিদ্ধান্ত ৩.২ এর পুরো ব্যাখ্যা দেয়, আর একই যুক্তি 11-এর পরীক্ষাও দেয়। এগুলোকে বলে divisibility test.

প্রমাণ:

1. 10 − 1 = 9, তাই 10 ≡ 1 (mod 9). অনুসিদ্ধান্ত ৩.২-এ প্রতিটি i-তে 10ⁱ ≡ 1ⁱ = 1 (mod 9). — ঘাতে congruence টিকে থাকে
2. উপপাদ্য ৩.১-এ d_i10ⁱ ≡ d_i, আর সব পদ যোগ করে n ≡ ∑ d_i (mod 9). 3 ∣ 9, তাই mod 9-এর যেকোনো congruence mod 3-এও সত্য, ফলে mod 3-এর দাবিও আসে। — উপপাদ্য ৩.১, আর 3 ∣ 9
3. 10 − (−1) = 11, তাই 10 ≡ −1 (mod 11), আর 10ⁱ ≡ (−1)ⁱ. একইভাবে n ≡ ∑ (−1)ⁱd_i (mod 11). — অনুসিদ্ধান্ত ৩.২
4. n ≡ s (mod m) হলে m ∣ n ⇔ m ∣ s, কারণ n − s m-এর গুণিতক। ∎ — উপপাদ্য ১.২

লক্ষ করুন, উপপাদ্যটি শুধু “বিভাজ্য কি না” নয়, ভাগশেষও দেয়: 918082-এর অঙ্কের যোগফল 28, আর 28 ≡ 1 (mod 9), তাই 918082 mod 9 = 1. ভাগশেষের এই রূপটিই পুরোনো “নয় বাদ দেওয়া” (casting out nines) পদ্ধতির ভিত্তি: হাতে করা গুণ বা যোগ মেলানোর জন্য দুই পাশের অঙ্ক-যোগফল mod 9 মেলানো। নিচের stepper একই সংখ্যায় 11-এর পরীক্ষা ধাপে ধাপে দেখায়।

1n = 918082210 ≡ −1 (mod 11)310^i ≡ (−1)^i4অঙ্ক (ডান থেকে): 2 8 0 8 1 95চিহ্ন:            + − + − + −6n ≡ 2−8+0−8+1−9 = −227mod 9: অঙ্ক-যোগ 28 ≡ 1

একই ধারণা 7 আর 13-এর জন্যও একটি পরীক্ষা দেয়, শুধু একক অঙ্কের বদলে তিন অঙ্কের দলে। 1001 = 7 · 11 · 13, তাই 1000 ≡ −1 (mod 7), (mod 11) আর (mod 13). ফলে সংখ্যাটিকে ডান থেকে তিন অঙ্ক করে দলে ভাগ করে একান্তর চিহ্নে যোগ করলে যে সংখ্যা আসে, তা মূল সংখ্যার সঙ্গে এই তিনটি modulus-এই congruent. যেমন 135792468: 468 − 792 + 135 = −189 = −27 · 7, তাই 7 ∣ 135792468. নিচের ব্লক এই সব পরীক্ষা অঙ্ক থেকে (সংখ্যাটিকে string হিসেবে পড়ে) চালায় আর হাজার হাজার সংখ্যায় সরাসরি %-এর সঙ্গে মেলায়।

import random
random.seed(22)

def digits(n):                     # least significant digit first
    return [int(c) for c in reversed(str(n))]

def alt_sum(n):                    # d0 - d1 + d2 - d3 + ...
    return sum(d if k % 2 == 0 else -d for k, d in enumerate(digits(n)))

def test3(n):  return sum(digits(n)) % 3 == 0
def test9(n):  return sum(digits(n)) % 9 == 0
def test11(n): return alt_sum(n) % 11 == 0

def group_sum(n):                  # 1000 ≡ -1 (mod 7, 11, 13)
    s, sign = 0, 1
    while n:
        s, n, sign = s + sign * (n % 1000), n // 1000, -sign
    return s

n = 918082
print(n, ": digit sum", sum(digits(n)), " alternating sum", alt_sum(n))
print("test3/test9/test11:", test3(n), test9(n), test11(n), "  918082 // 11 =", n // 11)
n = 135792468
print(n, ": 3-digit group sum", group_sum(n), "  % 7 =", group_sum(n) % 7, "  % 13 =", group_sum(n) % 13)

nums = [random.randrange(1, 10**12) for _ in range(20000)] + list(range(1, 3000))
bad = dict.fromkeys(["3", "9", "11", "7", "13"], 0)
for x in nums:
    bad["3"] += test3(x) != (x % 3 == 0)
    bad["9"] += test9(x) != (x % 9 == 0)
    bad["11"] += test11(x) != (x % 11 == 0)
    for d in (7, 13):
        bad[str(d)] += (group_sum(x) % d == 0) != (x % d == 0)
print(len(nums), "numbers checked; mismatches:", bad)

918082 : digit sum 28  alternating sum -22
test3/test9/test11: False False True   918082 // 11 = 83462
135792468 : 3-digit group sum -189   % 7 = 0   % 13 = 6
22999 numbers checked; mismatches: {'3': 0, '9': 0, '11': 0, '7': 0, '13': 0}

৫ · Modular exponentiation — বারবার বর্গ করে বিশাল ঘাত

বাজারঘরের নিরাপত্তা দল জানতে চায় 7²²² mod 1000. সরল পথ: 7²²² পুরোটা হিসাব করে 1000 দিয়ে ভাগ। কিন্তু 7²²² একটি ১৮৮ অঙ্কের সংখ্যা, আর cryptography-তে ঘাত হয় শত শত অঙ্কের, যেখানে পুরো সংখ্যাটি লেখার মতো জায়গা মহাবিশ্বেও নেই। অনুসিদ্ধান্ত ৩.২ বলে প্রতিটি গুণের পরেই mod 1000 নেওয়া যায়, তাই সংখ্যা কখনো 1000 × 1000-এর বেশি হয় না। বাকি সমস্যা গুণের সংখ্যা: 221টি গুণ ছোট ঘাতে চলে, কিন্তু 10¹⁰⁰ ঘাতে অসম্ভব। সমাধান পর্ব ১৩-এ দেখা binary exponentiation, প্রতিটি ধাপে mod নিয়ে। একে বলে modular exponentiation, আর পদ্ধতিটির প্রচলিত নাম repeated squaring বা square-and-multiply.

প্রমাণ: L = ⌊log₂ b⌋, অর্থাৎ b-এর binary রূপে L + 1টি অঙ্ক: b = ∑ 2ⁱ (যেসব i-তে bit 1), 0 ≤ i ≤ L.

1. x₀ = a mod m, আর x_i = x_i−1² mod m (1 ≤ i ≤ L). Induction-এ x_i ≡ a²ⁱ (mod m), কারণ (a²ⁱ⁻¹)² = a²ⁱ. এখানে ঠিক L-টি বর্গ। — অনুসিদ্ধান্ত ৩.২, ঘাতের নিয়ম
2. ঘাতের নিয়মে a^b = ∏ a²ⁱ, গুণফল নেওয়া হয় যেসব i-তে bit 1. উপপাদ্য ৩.১(গ) দিয়ে a^b ≡ ∏ x_i (mod m). — a^s+t = a^sa^t
3. b-তে 1-bit আছে বড়জোর L + 1টি, তাই এদের গুণফলে বড়জোর L-টি গুণ (k-টি সংখ্যা গুণ করতে k − 1টি গুণ লাগে)। — গোনা
4. মোট বড়জোর L + L = 2⌊log₂ b⌋. প্রতিবার গুণের পরে mod m নেওয়া হয়, তাই প্রতিটি উপাদান 0 থেকে m − 1-এর মধ্যে, আর গুণফল m²-এর কম। ∎

লুপের সঠিকতা, অর্থাৎ invariant r · x^e ≡ a^b, পর্ব ১৩-এ 3¹³-এ প্রমাণ করা হয়েছে; mod নেওয়াতে প্রমাণে শুধু “=”-এর জায়গায় “≡” বসে। 10¹⁰⁰-এর মতো ঘাতে L = 332, তাই বড়জোর ৬৬৪টি গুণ। নিচের stepper একটি ছোট উদাহরণ দেখায়: 3²⁰⁰ mod 13.

1200 = 11001000 (binary)2    = 128 + 64 + 83x_i = x_(i−1)² mod 134bit 1: r = r · x_i mod 1353^200 mod 13 = r6যাচাই: 3³ = 27 ≡ 1

এবার মূল প্রশ্ন, 7²²² mod 1000. নিচের ব্লক ডান থেকে বাঁয়ে bit পড়ে, প্রতিটি ধাপের e, bit, x আর r ছাপে, আর গুণ গোনে। প্রথম গুণটি (1 দিয়ে) গোনা হয়নি আর শেষের অপ্রয়োজনীয় বর্গটি করাই হয়নি, যাতে সংখ্যাটি উপপাদ্যের হিসাবের সঙ্গে মেলে। তারপর Python-এর নিজস্ব pow(a, b, m)-এর সঙ্গে মেলায়। Python-এর int যেকোনো আকারের হতে পারে, তাই 7²²² পুরোটাও হিসাব করে দেখা যায়।

def pow_mod_trace(a, b, m):
    """right-to-left repeated squaring; prints one row per bit of b"""
    r, x, e = 1, a % m, b
    sq = mul = 0
    started = False
    print("   e  bit  x = a^(2^i) mod m    r")
    while e > 0:
        bit = e & 1
        if bit:
            mul += started          # the first factor needs no multiplication
            r, started = r * x % m, True
        print(f"{e:4}   {bit}   {x:6}            {r:4}")
        e >>= 1
        if e:                       # the last square is never needed
            x, sq = x * x % m, sq + 1
    return r, sq, mul

r, sq, mul = pow_mod_trace(7, 222, 1000)
print("7^222 mod 1000 =", r, "   pow(7, 222, 1000) =", pow(7, 222, 1000))
print("squarings:", sq, " multiplications:", mul, " total:", sq + mul,
      " (naive: 221)")
big = 7 ** 222
print("7^222 itself has", len(str(big)), "digits, ends in", str(big)[-3:])

b = 10 ** 100                       # a googol as the exponent
print("bits in b:", b.bit_length(), "  7^b mod 1000 =", pow(7, b, 1000))

   e  bit  x = a^(2^i) mod m    r
 222   0        7               1
 111   1       49              49
  55   1      401             649
  27   1      801             849
  13   1      601             249
   6   0      201             249
   3   1      401             849
   1   1      801              49
7^222 mod 1000 = 49    pow(7, 222, 1000) = 49
squarings: 7  multiplications: 5  total: 12  (naive: 221)
7^222 itself has 188 digits, ends in 049
bits in b: 333   7^b mod 1000 = 1

৬ · শেষ অঙ্ক, সপ্তাহের দিন আর বাজারঘরের ডেলিভারি-চক্র

“7²⁰²⁶-এর শেষ অঙ্ক কত?” এই প্রশ্নের মানে 7²⁰²⁶ mod 10. শেষ দুই অঙ্ক মানে mod 100. এমন প্রশ্নে সাধারণত একটি চক্র খুঁজলেই হয়: 7¹ = 7, 7² = 49, 7³ = 343, 7⁴ = 2401. শেষ অঙ্ক 7, 9, 3, 1, তারপর আবার 7. আরও ভালো, 7⁴ = 2401 ≡ 1 (mod 100). তাই 2026 = 4 · 506 + 2 থেকে

7²⁰²⁶ = (7⁴)⁵⁰⁶ · 7² ≡ 1⁵⁰⁶ · 49 = 49 (mod 100)

অর্থাৎ শেষ দুই অঙ্ক 49, শেষ অঙ্ক 9. যুক্তির প্রতিটি ধাপ অনুসিদ্ধান্ত ৩.২: 7⁴ ≡ 1 হলে তার যেকোনো ঘাতও ≡ 1. লক্ষ করুন, এখানে ঘাত 2026-কে 4 দিয়ে ভাগ করা হয়েছে, কারণ 7⁴ ≡ 1; এটি “ঘাত mod m” নয়, যা §৩-এর ফাঁদ ২-এ নিষেধ করা হয়েছে।

সপ্তাহের দিনের অঙ্কে modulus 7. দিনগুলোকে রবি = 0, সোম = 1, …, শনি = 6 সংখ্যা দিলে “আজ d বার, n দিন পরে কী বার?” প্রশ্নের উত্তর (d + n) mod 7. আজ বৃহস্পতিবার (4) হলে ১০০ দিন পরে (4 + 100) mod 7 = 104 mod 7 = 6, শনিবার; কারণ 100 = 14 · 7 + 2. দশ লক্ষ দিন পরে? 10⁶ mod 7 হিসাবে 10 ≡ 3, 10² ≡ 2, 10³ ≡ 6 ≡ −1, তাই 10⁶ ≡ (−1)² = 1, আর উত্তর শুক্রবার। বাজারঘরের ১১ দিনের ভ্যান-রুটের প্রশ্নগুলো নিচের stepper-এ।

1রবি=0 সোম=1 … শনি=62দিন 0 = বৃহস্পতি = 4311 ≡ 4 (mod 7)4k-তম ডেলিভারি: (4 + 4k) mod 754k ≡ 0 (mod 7) ⇒ 7 ∣ k6lcm(7, 11) = 77

নিচের ব্লক এই অংশের সব দাবি এক জায়গায় পরীক্ষা করে: শেষ অঙ্কের চক্র, 7²⁰²⁶-এর শেষ দুই অঙ্ক, stepper-এর বারগুলো, আর §৭-এর একটি প্রমাণের দাবি ছোট n-এ।

print("7^k mod 10, k = 1..8:", [pow(7, k, 10) for k in range(1, 9)])
print("7^2026: mod 10 =", pow(7, 2026, 10), "  mod 100 =", pow(7, 2026, 100))
print("2^100 mod 7 =", pow(2, 100, 7), "   3^1000 mod 100 =", pow(3, 1000, 100))

days = ["রবি", "সোম", "মঙ্গল", "বুধ", "বৃহস্পতি", "শুক্র", "শনি"]
today = 4                                  # day 0 is a Thursday
for k in [0, 1, 2, 3, 7, 20]:
    print(f"delivery {k:2}: day {11 * k:3} -> {days[(today + 11 * k) % 7]}")
again = [k for k in range(1, 30) if 11 * k % 7 == 0]
print("same weekday again at k =", again, "-> every", 11 * again[0], "days")
meet = [d for d in range(1, 250) if d % 7 == 0 and d % 11 == 0]
print("weekly and 11-day routes meet on days", meet)
print("10**6 days after Thursday:", days[(today + 10**6) % 7])

claim = all((3**(2*n + 1) + 2**(n + 2)) % 7 == 0 for n in range(500))
print("7 | 3^(2n+1) + 2^(n+2) for n = 0..499:", claim)
print("n^2 mod 4 over n = 0..999:", sorted({n * n % 4 for n in range(1000)}))

7^k mod 10, k = 1..8: [7, 9, 3, 1, 7, 9, 3, 1]
7^2026: mod 10 = 9   mod 100 = 49
2^100 mod 7 = 2    3^1000 mod 100 = 1
delivery  0: day   0 -> বৃহস্পতি
delivery  1: day  11 -> সোম
delivery  2: day  22 -> শুক্র
delivery  3: day  33 -> মঙ্গল
delivery  7: day  77 -> বৃহস্পতি
delivery 20: day 220 -> রবি
same weekday again at k = [7, 14, 21, 28] -> every 77 days
weekly and 11-day routes meet on days [77, 154, 231]
10**6 days after Thursday: শুক্র
7 | 3^(2n+1) + 2^(n+2) for n = 0..499: True
n^2 mod 4 over n = 0..999: [0, 1]

৭ · পরীক্ষার অঙ্ক, একটি ভুল প্রমাণ আর প্রয়োগের ঝলক

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

অঙ্ক ১: 2¹⁰⁰-কে 7 দিয়ে ভাগ করলে ভাগশেষ কত?

1. ছোট ঘাত দেখি: 2³ = 8 = 7 + 1, তাই 2³ ≡ 1 (mod 7).
2. 100 = 3 · 33 + 1, তাই 2¹⁰⁰ = (2³)³³ · 2 ≡ 1³³ · 2 = 2 (mod 7). উত্তর 2.

অঙ্ক ২: 57x23 একটি পাঁচ অঙ্কের সংখ্যা, x একটি অঙ্ক। এটি 9 দিয়ে বিভাজ্য হলে x কত? তখন সংখ্যাটি 11 দিয়েও বিভাজ্য কি?

1. অঙ্কের যোগফল 5 + 7 + x + 2 + 3 = 17 + x. 9 ∣ (17 + x) আর 0 ≤ x ≤ 9 থেকে 17 + x = 18, তাই x = 1. সংখ্যাটি 57123 = 9 × 6347.
2. একান্তর যোগফল, ডান থেকে: 3 − 2 + 1 − 7 + 5 = 0, তাই 11 ∣ 57123 (57123 = 11 × 5193). 9 আর 11-এর কোনো সাধারণ ভাজক নেই, তাই 99 ∣ 57123: 57123 = 99 × 577 (এই শেষ ধাপের যুক্তি পর্ব ২১-এর gcd থেকে)।

অঙ্ক ৩: প্রমাণ করুন, প্রতিটি n ≥ 0-তে 7 ∣ 3²ⁿ⁺¹ + 2ⁿ⁺²

1. 3²ⁿ⁺¹ = 3 · 9ⁿ, আর 9 ≡ 2 (mod 7), তাই অনুসিদ্ধান্ত ৩.২-এ 3²ⁿ⁺¹ ≡ 3 · 2ⁿ. — ভিত্তি mod 7 করা
2. 2ⁿ⁺² = 4 · 2ⁿ. যোগ করে 3²ⁿ⁺¹ + 2ⁿ⁺² ≡ 3 · 2ⁿ + 4 · 2ⁿ = 7 · 2ⁿ ≡ 0 (mod 7). ∎ — উপপাদ্য ৩.১

একই দাবি induction দিয়েও প্রমাণ করা যায়, কিন্তু congruence-এর পথ দুই লাইনের। §৬-এর ব্লক n = 0 থেকে 499-এ দাবিটি পরীক্ষা করেছে।

অঙ্ক ৪: 7²²² mod 1000 repeated squaring দিয়ে, আর কয়টি গুণ লাগল?

222 = 11011110₂. বর্গগুলো mod 1000: x₀ … x₇ = 7, 49, 401, 801, 601, 201, 401, 801. 1-bit যেখানে: i = 1, 2, 3, 4, 6, 7. ক্রমে গুণ: 49 · 401 ≡ 649, · 801 ≡ 849, · 601 ≡ 249, · 401 ≡ 849, · 801 ≡ 49. উত্তর 49; বর্গ ৭টি, গুণ ৫টি, মোট ১২ (§৫-এর ব্লকের সারণির সঙ্গে প্রতিটি মান মেলে)।

প্রমাণের ভুল ধরুন: “mod m-এ কাটাকাটি সবসময় চলে”

একজন লিখলেন: “দাবি: ac ≡ bc (mod m) আর c ≢ 0 (mod m) হলে a ≡ b (mod m). প্রমাণ: ac ≡ bc মানে m ∣ (a − b)c. c ≢ 0, তাই দুই পাশকে c দিয়ে ভাগ করলে m ∣ (a − b). ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: “m ∣ (a − b)c থেকে c দিয়ে ভাগ করে m ∣ (a − b)” ধাপটি অবৈধ। m-এর কিছু মৌলিক উৎপাদক c-এর ভেতরে থাকতে পারে। Counterexample: m = 10, c = 2, a = 3, b = 8: 10 ∣ (3 − 8) · 2 = −10, কিন্তু 10 ∤ −5. সঠিক দাবি: gcd(c, m) = 1 হলে a ≡ b (mod m); সাধারণভাবে a ≡ b (mod m/gcd(c, m)). উদাহরণে m/gcd = 5, আর সত্যিই 3 ≡ 8 (mod 5). প্রমাণ পর্ব ২৩-এ। শিক্ষা: “ভাগ করা” ধাপ দেখলেই জিজ্ঞেস করুন, কী দিয়ে ভাগ, আর সেটি কেন বৈধ।

প্রয়োগের ঝলক

এই পর্বের নিয়মগুলো বাজারঘরের তিনটি কাজের সরাসরি ভিত্তি, যাদের বিস্তারিত পর্ব ২৬ “সংখ্যাতত্ত্বের প্রয়োগ — check digit, hashing আর pseudorandom সংখ্যা”-এ আসবে। (১) Hash function h(k) = k mod m গ্রাহকের id-কে m-টি তাকের একটিতে পাঠায়, আর m কেমন হলে id-গুলো সমানভাবে ছড়ায়, তার উত্তর congruence class থেকেই আসে (বাস্তবায়ন DSA কোর্সের পর্ব ৩২-এ)। (২) Invoice-এর check digit একটি weighted যোগফল mod 10 বা mod 11, যা §৪-এর পরীক্ষার মতোই টাইপের ভুল ধরে। (৩) Linear congruential generator x_n+1 = (ax_n + c) mod m নামের সূত্র এলোমেলো-দেখতে সংখ্যা বানায়, ঘড়ির কাঁটা ঘোরার মতো একটি চক্রে।

৮ · AI-এর যুগে — modular হিসাব আর প্রমাণ যাচাই

AI সহকারী “3²⁰⁰ mod 13” বা “শেষ দুই অঙ্ক কত” প্রশ্নের উত্তর আত্মবিশ্বাসের সঙ্গে দেয়, আর প্রায়ই ঠিকও দেয়। কিন্তু বড় সংখ্যায় মাঝের একটি ভাগশেষ ভুল হলেই পুরো উত্তর ভুল, আর ভুল উত্তরও একই আত্মবিশ্বাসে আসে। কিছু ভুল নিয়মিত দেখা যায়:

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

• চূড়ান্ত সংখ্যাটি নিজে pow(a, b, m) বা % দিয়ে মিলিয়েছি
• কোথাও ঘাতকে mod m করা হয়নি; ঘাত কমানো হলে aⁿ ≡ 1-এর প্রমাণ আছে
• প্রতিটি কাটাকাটির আগে gcd(c, m) = 1 দেখানো হয়েছে
• ঋণাত্মক সংখ্যার ভাগশেষ কোন সংজ্ঞায়, তা স্পষ্ট
• প্রমাণের দাবিটি ছোট n-এ brute force দিয়ে পরীক্ষা করেছি, আর একটি counterexample খুঁজেছি
• উল্লেখিত উপপাদ্যের শর্ত (মৌলিক modulus, gcd = 1) আর ইতিহাসের সাল বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

সবচেয়ে সস্তা প্রথম পরীক্ষা: AI যে সংখ্যা দিল, সেটি §৫-এর pow_mod_trace দিয়ে চালান। সারণির একটি ঘরের অমিলই দেখিয়ে দেয় ভুলটি কোন ধাপে।