Fermat-এর ছোট উপপাদ্য আর Euler-এর totient

১ · ঘাতের ভাগশেষে চক্র — প্রশ্নটা কোথা থেকে আসে

বাজারঘর প্রতিদিন একটি “লাকি কুপন” দেয়। কুপন নম্বর বানানোর নিয়ম সহজ: আগের দিনের নম্বরকে 3 দিয়ে গুণ করে 7 দিয়ে ভাগশেষ নেওয়া হয়, শুরু 1 থেকে। তাহলে দিনগুলোর নম্বর 3, 2, 6, 4, 5, 1, তারপর আবার 3, 2, 6, … ঠিক ছয় দিন পরপর চক্রটি ফিরে আসে। প্রশ্ন জাগে: এটা কি কাকতালীয়? 3-এর জায়গায় 2 নিলে কী হয়? 7-এর জায়গায় 31 বা 100 নিলে? আর এক লক্ষতম দিনের কুপন কত, সেটা কি এক লক্ষবার গুণ না করে বলা যায়?

এই পর্বের সব উপপাদ্য এই এক প্রশ্নের উত্তর: a-এর ঘাতগুলোকে m দিয়ে ভাগ করলে ভাগশেষ কোন চক্রে ঘোরে, আর চক্রের দৈর্ঘ্য কত? উত্তরটি সুন্দর আর কাজের। এর ওপর দাঁড়িয়ে আছে বিশাল ঘাতের দ্রুত হিসাব, মৌলিক সংখ্যা চেনার পরীক্ষা, আর পরের মডিউলের RSA (পর্ব ২৮ “RSA-এর গণিত — key, encryption আর কেন কাজ করে”).

ছবিটিতে দুটি জিনিস লক্ষ করুন। প্রথমত, “3 দিয়ে গুণ করে mod 7” একটি permutation: {1, …, 6}-এর প্রতিটি সংখ্যা ঠিক একবার তীরের মাথায় আসে, অর্থাৎ পর্ব ১৬ “ফাংশন — one-to-one, onto, inverse আর composition”-এর ভাষায় এটি একটি bijection. দ্বিতীয়ত, 1 থেকে তীর ধরে হাঁটলে কুপনের ক্রমটিই পাওয়া যায়, আর ছয় ধাপে 1-এ ফেরা মানে 3⁶ ≡ 1 (mod 7). Fermat-এর উপপাদ্যের প্রমাণ ঠিক প্রথম পর্যবেক্ষণটিকে কাজে লাগায়।

আগের পর্বগুলো থেকে যা লাগবে, এক জায়গায়: a ≡ b (mod m) মানে m ∣ (a − b), আর যোগ-গুণ এই congruence মেনে চলে (পর্ব ২২ “Modular arithmetic — ঘড়ির গণিত আর modular exponentiation”). gcd(a, m) = 1 হলে a আর m সহমৌলিক (coprime), আর তখন a-এর একটি modular inverse থাকে, অর্থাৎ এমন b যাতে ab ≡ 1 (mod m) (পর্ব ২৩ “Linear congruence আর Chinese Remainder Theorem”). তাই সহমৌলিক সংখ্যাকে congruence-এর দুই পাশ থেকে “কাটা” যায়: ac ≡ bc আর gcd(c, m) = 1 হলে a ≡ b. আর Euclid-এর lemma: মৌলিক p যদি ab-কে ভাগ করে, তবে p ∣ a বা p ∣ b (পর্ব ২১ “GCD আর Euclid-এর algorithm — Bézout আর extended Euclid”). এই তিনটি হাতিয়ারেই পুরো পর্ব চলবে।

২ · Fermat-এর ছোট উপপাদ্য — বিবৃতি আর প্রমাণ

দুটি শর্তই জরুরি। p ∣ a হলে a^p−1 ≡ 0, 1 নয় (যেমন 7⁶ ≡ 0 (mod 7)). আর p মৌলিক না হলে ফলটি সাধারণত ভাঙে: 2¹⁴ mod 15 = 4, 1 নয়। নামের “ছোট” শব্দটি Fermat-এর বিখ্যাত “শেষ উপপাদ্য” (Fermat's Last Theorem) থেকে আলাদা করার জন্য; এটি গুরুত্বে মোটেই ছোট নয়।

প্রমাণ: S = {1, 2, …, p − 1} নিন, আর প্রতিটি k ∈ S-কে a দিয়ে গুণ করে mod p নিন।

1. প্রতিটি ak mod p শূন্য নয়। কারণ p ∣ ak হলে Euclid-এর lemma অনুযায়ী p ∣ a বা p ∣ k; প্রথমটি শর্তে নিষিদ্ধ, আর দ্বিতীয়টি অসম্ভব কারণ 1 ≤ k ≤ p − 1. তাই ak mod p ∈ S. — Euclid-এর lemma, p মৌলিক
2. ভিন্ন k থেকে ভিন্ন ভাগশেষ আসে। ধরুন ai ≡ aj (mod p), যেখানে i, j ∈ S. তাহলে p ∣ a(i − j), আর আবার Euclid-এর lemma-য় p ∣ (i − j). কিন্তু |i − j| < p, তাই i = j. — Euclid-এর lemma
3. ধাপ ১ আর ২ মিলে k ↦ ak mod p হলো S থেকে S-এ একটি one-to-one ফাংশন। সসীম সেটে one-to-one ফাংশন onto-ও (pigeonhole), তাই {a · 1, a · 2, …, a(p − 1)}-এর ভাগশেষগুলো ঠিক 1, 2, …, p − 1, শুধু অন্য ক্রমে। — সসীম সেটে injection = bijection
4. দুটি তালিকার সব সংখ্যা গুণ করুন। ক্রম বদলালে গুণফল বদলায় না, তাই (a · 1)(a · 2)⋯(a(p − 1)) ≡ 1 · 2 ⋯ (p − 1), অর্থাৎ a^p−1 · (p − 1)! ≡ (p − 1)! (mod p). — গুণ congruence মানে
5. (p − 1)!-এর প্রতিটি উৎপাদক p-এর চেয়ে ছোট, তাই Euclid-এর lemma-য় p ∤ (p − 1)!, অর্থাৎ gcd((p − 1)!, p) = 1. দুই পাশ থেকে (p − 1)! কেটে দিলে a^p−1 ≡ 1 (mod p). ∎ — সহমৌলিক উৎপাদক কাটা যায়

নিচের stepper এই পাঁচ ধাপ p = 7, a = 3-এ হুবহু অনুসরণ করে, উপরের ছবির সংখ্যাগুলো দিয়েই।

1p = 7, a = 3, 7 ∤ 32S = {1, 2, 3, 4, 5, 6}33S = {3, 6, 9, 12, 15, 18}4mod 7: {3, 6, 2, 5, 1, 4}53⁶ · 6! ≡ 6! (mod 7)66! = 720 ≡ 6, gcd(6!, 7) = 17⇒ 3⁶ ≡ 1 (mod 7)

উপপাদ্যটি থেকে দুটি কাজের corollary সরাসরি আসে।

প্রমাণ:

1. (ক) p ∤ a হলে উপপাদ্য ২.১-এর দুই পাশকে a দিয়ে গুণ করলেই a^p ≡ a. — গুণ congruence মানে
2. p ∣ a হলে দুই পাশই ≡ 0 (mod p), তাই a^p ≡ a এখানেও সত্য। — case-ভিত্তিক প্রমাণ
3. (খ) a · a^p−2 = a^p−1 ≡ 1 (mod p), আর inverse-এর সংজ্ঞাই এটি। ∎

(খ) একটি দ্বিতীয় পথ দেয় inverse বের করার: extended Euclid-এর বদলে একটি ঘাত। ঘাতটি দ্রুত বের হয় repeated squaring দিয়ে, যার loop invariant পর্ব ১৩ “Program-এর সঠিকতা — loop invariant আর Hoare logic-এর ধারণা”-এ প্রমাণ করা হয়েছে (binary exponentiation, প্রায় log₂ b-টি গুণ). Python-এর pow(a, b, m) ঠিক এই কাজটি করে, আর Python-এর int যত বড় দরকার তত বড় হতে পারে (Python কোর্সের পর্ব ০৭). কনটেস্টে mod 10⁹ + 7-এ এভাবে inverse নেওয়ার কৌশল DSA কোর্সের পর্ব ৬২-এ আছে।

এবার পরীক্ষা। নিচের ব্লক 200-এর নিচের প্রতিটি মৌলিক p আর প্রতিটি 1 ≤ a ≤ p − 1-এ উপপাদ্যটি যাচাই করে, Corollary ২.২-এর দুই অংশ দেখে, আর একটি যৌগিক modulus-এ কী ভাঙে তা দেখায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from math import gcd

def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))

primes = [p for p in range(2, 200) if is_prime(p)]
checks = fails = 0
for p in primes:
    for a in range(1, p):                 # every a with p ∤ a, 1 ≤ a ≤ p-1
        checks += 1
        fails += pow(a, p - 1, p) != 1
print("primes below 200:", len(primes), "  checks:", checks, "  failures:", fails)

# corollary a^p ≡ a (mod p) holds even when p divides a
print("a^7 ≡ a (mod 7) for a = 0..49:", all(pow(a, 7, 7) == a % 7 for a in range(50)))

# inverse by Fermat: a^(p-2) mod p
p = 13
inv = [pow(a, p - 2, p) for a in range(1, p)]
print("inverses mod 13 for a = 1..12:", inv)
print("same as pow(a, -1, 13):", inv == [pow(a, -1, p) for a in range(1, p)])

# a composite modulus: the pattern breaks
n = 15
bad = [a for a in range(1, n) if gcd(a, n) == 1 and pow(a, n - 1, n) != 1]
print("n = 15, coprime a with a^14 mod 15 != 1:", bad)
print("but a^phi(15) = a^8:", [pow(a, 8, 15) for a in (1, 2, 4, 7, 8, 11, 13, 14)])

primes below 200: 46   checks: 4181   failures: 0
a^7 ≡ a (mod 7) for a = 0..49: True
inverses mod 13 for a = 1..12: [1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12]
same as pow(a, -1, 13): True
n = 15, coprime a with a^14 mod 15 != 1: [2, 7, 8, 13]
but a^phi(15) = a^8: [1, 1, 1, 1, 1, 1, 1, 1]

৩ · Euler-এর totient φ(n) — সহমৌলিক সংখ্যা গোনা

কয়েকটি ছোট মান হাতে গুনে দেখুন: φ(1) = 1 (gcd(1, 1) = 1), φ(10) = 4 (1, 3, 7, 9), φ(12) = 4 (1, 5, 7, 11), φ(15) = 8 (1, 2, 4, 7, 8, 11, 13, 14). মৌলিক p-তে 1 থেকে p − 1 সবাই সহমৌলিক, তাই φ(p) = p − 1, আর তখন Fermat-এর ঘাত p − 1 ঠিক φ(p). বড় n-এ এভাবে গোনা ধীর; তার বদলে n-কে মৌলিক উৎপাদকে ভাঙতে হয় (fundamental theorem of arithmetic, পর্ব ২০ “বিভাজ্যতা আর মৌলিক সংখ্যা — division algorithm আর unique factorization”).

প্রমাণ:

1. (ক) 1 থেকে p^k-এর মধ্যে একটি সংখ্যা p^k-এর সঙ্গে সহমৌলিক নয় ঠিক তখন, যখন তার আর p^k-এর একটি সাধারণ মৌলিক উৎপাদক আছে; p^k-এর একমাত্র মৌলিক উৎপাদক p, তাই এরা ঠিক p-এর গুণিতকগুলো: p, 2p, …, p^k−1 · p, মোট p^k−1টি। বাকি p^k − p^k−1টি সহমৌলিক। — গণনায় বিয়োগের নিয়ম
2. (খ) পর্ব ২৩-এর Chinese Remainder Theorem বলে, gcd(m, n) = 1 হলে x mod mn ↦ (x mod m, x mod n) ফাংশনটি {0, …, mn − 1} থেকে সব জোড়ার সেটে একটি bijection. — CRT, পর্ব ২৩
3. gcd(x, mn) = 1 ⇔ gcd(x, m) = 1 এবং gcd(x, n) = 1, কারণ mn-এর মৌলিক উৎপাদক মানে m বা n-এর মৌলিক উৎপাদক। আর gcd(x, m) শুধু x mod m-এর ওপর নির্ভর করে। — gcd(x, m) = gcd(x mod m, m)
4. তাই bijection-টি mod mn-এর সহমৌলিক ভাগশেষগুলোকে ঠিক সেই জোড়াগুলোতে পাঠায়, যার প্রথম অংশ mod m-এ সহমৌলিক আর দ্বিতীয় অংশ mod n-এ সহমৌলিক। এমন জোড়া φ(m) · φ(n)টি, তাই φ(mn) = φ(m)φ(n). — গুণের নিয়ম
5. (গ) বিভিন্ন মৌলিক সংখ্যার ঘাত পরস্পর সহমৌলিক, তাই (খ) বারবার লাগিয়ে φ(n) = ∏ φ(p_i^e_i) = ∏ p_i^e_i(1 − 1/p_i) = n ∏ (1 − 1/p_i). ∎ — (ক), (খ) আর r-এর ওপর induction

এখানে ∏ মানে গুণফল, যেমন ∑ মানে যোগফল। (খ)-এর শর্ত gcd(m, n) = 1 ভুলবেন না: φ(4) · φ(6) = 2 · 2 = 4, অথচ φ(24) = 8. ধাপ ২–৪ পুরো গঠনমূলক প্রমাণের একটি সংক্ষিপ্ত রূপ; CRT-এর bijection প্রমাণসহ পর্ব ২৩-এ আছে। একটি ছোট উদাহরণে ধাপ ২–৪ চোখে দেখুন: m = 3, n = 4, mn = 12. mod 12-এর সহমৌলিক ভাগশেষ 1, 5, 7, 11, আর এদের (mod 3, mod 4) জোড়া যথাক্রমে (1, 1), (2, 1), (1, 3), (2, 3). প্রথম অংশ শুধু 1 বা 2 (φ(3) = 2টি বিকল্প), দ্বিতীয় অংশ শুধু 1 বা 3 (φ(4) = 2টি বিকল্প), আর চারটি সম্ভাব্য জোড়ার প্রতিটি ঠিক একবার এসেছে: φ(12) = 2 · 2 = 4. (ক)-এর সাধারণ যুক্তিটির ভাষায় সূত্রটির একটি সহজ ব্যাখ্যা আছে: 1 থেকে n-এর মধ্যে মোটামুটি 1/p অংশ p দিয়ে বিভাজ্য, তাই প্রতিটি মৌলিক উৎপাদক “(1 − 1/p) অংশ রেখে বাকিটা বাদ দেয়”। নিচের stepper φ(360) এভাবে বের করে।

1360 = 2³ · 3² · 52φ(2³) = 8 − 43φ(3²) = 9 − 34φ(5) = 5 − 15φ(360) = 4 · 6 · 46যাচাই: 360·(1/2)(2/3)(4/5)

সূত্রটি নির্ভুল কি না, সেটি নিজে যাচাই করুন। নিচের ব্লক φ-এর দুটি সংস্করণ লেখে, সংজ্ঞা থেকে গোনা (brute force) আর মৌলিক উৎপাদকের সূত্র, তারপর ১,০০০ পর্যন্ত মেলায়, multiplicative ধর্ম আর তার শর্ত পরীক্ষা করে, আর একটি বিখ্যাত অভেদ দেখায়: n-এর সব ভাজক d-এর জন্য φ(d)-এর যোগফল n.

from math import gcd

def phi_brute(n):                      # count k in 1..n with gcd(k, n) = 1
    return sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)

def phi_formula(n):                    # n times (1 - 1/p) for each prime p | n
    result, m, p = n, n, 2
    while p * p <= m:
        if m % p == 0:
            while m % p == 0:
                m //= p
            result -= result // p
        p += 1
    if m > 1:
        result -= result // m
    return result

print("formula == brute force, n = 1..1000:",
      all(phi_formula(n) == phi_brute(n) for n in range(1, 1001)))
print("phi(360) =", phi_formula(360), "  phi(1001) =", phi_formula(1001),
      "  phi(97) =", phi_formula(97))

mult = all(phi_formula(m * n) == phi_formula(m) * phi_formula(n)
           for m in range(1, 80) for n in range(1, 80) if gcd(m, n) == 1)
print("phi(mn) == phi(m) phi(n) whenever gcd(m, n) = 1:", mult)
print("phi(4) * phi(6) =", phi_formula(4) * phi_formula(6),
      "  but phi(24) =", phi_formula(24))

gauss = all(sum(phi_formula(d) for d in range(1, n + 1) if n % d == 0) == n
            for n in range(1, 500))
print("sum of phi(d) over divisors d of n equals n (n < 500):", gauss)

formula == brute force, n = 1..1000: True
phi(360) = 96   phi(1001) = 720   phi(97) = 96
phi(mn) == phi(m) phi(n) whenever gcd(m, n) = 1: True
phi(4) * phi(6) = 4   but phi(24) = 8
sum of phi(d) over divisors d of n equals n (n < 500): True

৪ · Euler-এর উপপাদ্য আর বিশাল ঘাত ছোট করা

ব্লক ১-এর শেষ লাইন যা ইঙ্গিত দিয়েছিল, Euler সেটিই প্রমাণ করেন: মৌলিক modulus লাগে না, শুধু a আর m সহমৌলিক হলেই চলে, আর ঘাত হবে φ(m).

প্রমাণ: r₁, r₂, …, r_φ(m) হোক 1 থেকে m-এর মধ্যে m-এর সঙ্গে সহমৌলিক সংখ্যাগুলো। Fermat-এর প্রমাণটিই এখানে চলে, শুধু Euclid-এর lemma-র জায়গায় gcd-এর যুক্তি।

1. প্রতিটি ar_i m-এর সঙ্গে সহমৌলিক, কারণ a আর r_i দুটিই m-এর সঙ্গে সহমৌলিক, আর দুটি সহমৌলিক সংখ্যার গুণফলের সঙ্গে m-এর কোনো সাধারণ মৌলিক উৎপাদক থাকতে পারে না। তাই ar_i mod m আবার r-দের একটি। — মৌলিক উৎপাদকের যুক্তি
2. ar_i ≡ ar_j (mod m) হলে a-এর inverse দিয়ে গুণ করে r_i ≡ r_j, আর দুটিই 1 থেকে m-এর মধ্যে, তাই i = j. — gcd(a, m) = 1 ⇒ a-এর inverse আছে
3. তাই ar₁, …, ar_φ(m)-এর ভাগশেষগুলো r-দেরই একটি permutation. সব গুণ করলে a^φ(m) · R ≡ R (mod m), যেখানে R = r₁ ⋯ r_φ(m). — ক্রম বদলালে গুণফল একই
4. R সহমৌলিক সংখ্যার গুণফল, তাই gcd(R, m) = 1, আর R কাটা যায়: a^φ(m) ≡ 1 (mod m). ∎ — সহমৌলিক উৎপাদক কাটা যায়

Euler এই সাধারণ রূপটি ১৭৬০-এর দশকে প্রকাশ করেন বলে উল্লেখ করা হয়। φ চিহ্নটি পরে Gauss তাঁর ১৮০১ সালের Disquisitiones Arithmeticae-তে ব্যবহার করেন, আর “totient” নামটি J. J. Sylvester-এর (১৮৭৯-এর দিকে), এমনটাই সাধারণত বলা হয়।

উপপাদ্যটির সবচেয়ে বেশি ব্যবহৃত রূপ হলো ঘাত ছোট করা। b-কে φ(m) দিয়ে ভাগ করুন: b = qφ(m) + r, 0 ≤ r < φ(m). তাহলে a^b = (a^φ(m))^q · a^r ≡ 1^q · a^r.

131 মৌলিক, 31 ∤ 3 ⇒ 3³⁰ ≡ 12100000 = 30 · 3333 + 1033¹⁰⁰⁰⁰⁰ = (3³⁰)³³³³ · 3¹⁰43⁵ = 243 = 7 · 31 + 2653¹⁰ = (3⁵)² ≡ (−5)² = 25

বাজারঘরের কুপনের প্রশ্নে ফিরে যাই: এক লক্ষতম দিনের কুপন 3¹⁰⁰⁰⁰⁰ mod 7. 100000 = 6 · 16666 + 4, তাই উত্তর 3⁴ = 81 ≡ 4. আর যদি modulus 7 না হয়ে 100 হয় (শেষ দুই অঙ্ক), তবে φ(100) = 100 · (1/2) · (4/5) = 40, আর gcd(7, 100) = 1 বলে 7²⁰²⁶ ≡ 7^{2026 mod 40} = 7²⁶ (mod 100). এটি আরও ছোট করা যায় পরের অংশের ধারণায়।

৫ · Order আর primitive root — চক্রের আসল দৈর্ঘ্য

Euler বলেন a^φ(m) ≡ 1, কিন্তু 1-এ প্রথমবার ফেরা আরও আগেও হতে পারে। কুপনের নিয়মে 3-এর বদলে 2 নিলে mod 7-এ ক্রম হয় 2, 4, 1, 2, 4, 1, …, চক্রের দৈর্ঘ্য 3, যদিও φ(7) = 6. চক্রের এই আসল দৈর্ঘ্যের নাম order.

প্রমাণ:

1. (⇐) k = dq হলে a^k = (a^d)^q ≡ 1^q = 1. — ঘাতের নিয়ম
2. (⇒) Division algorithm-এ k = dq + r, 0 ≤ r < d. তাহলে 1 ≡ a^k = (a^d)^q a^r ≡ a^r. — division algorithm, পর্ব ২০
3. r > 0 হলে r হতো d-এর চেয়ে ছোট একটি ধনাত্মক ঘাত যেখানে a^r ≡ 1, যা d-এর “সবচেয়ে ছোট” হওয়ার বিরোধী। তাই r = 0, অর্থাৎ d ∣ k. — contradiction
4. Euler-এর উপপাদ্যে a^φ(m) ≡ 1, তাই k = φ(m) নিয়ে d ∣ φ(m). ∎

এর একটি কাজের ফল: a^x ≡ a^y (mod m) ⇔ x ≡ y (mod ord_m(a)). তাই ঘাত কমানোর জন্য φ(m)-এর চেয়েও ভালো সংখ্যা হলো order, যদি জানা থাকে। §৪-এর প্রশ্নে 7⁴ = 2401 ≡ 1 (mod 100), অর্থাৎ ord₁₀₀(7) = 4 (আর 4 ∣ 40, উপপাদ্য মেনে). 2026 = 4 · 506 + 2, তাই 7²⁰²⁶ ≡ 7² = 49 (mod 100): শেষ দুই অঙ্ক 49.

উপপাদ্য ৫.২ আসলে একটি বড় নিয়মের বিশেষ রূপ: একটি সসীম group-এর যেকোনো উপাদানের order group-এর আকারকে ভাগ করে (Lagrange-এর উপপাদ্য)। mod m-এর সহমৌলিক ভাগশেষগুলো গুণের অধীনে φ(m) আকারের একটি group, আর এই দৃষ্টিভঙ্গি পর্ব ৭০ “Group — symmetry, cyclic group আর Lagrange-এর উপপাদ্য”-এ আসবে।

(ক)-এর প্রমাণে polynomial-এর একটি তথ্য লাগে (মৌলিক modulus-এ d ঘাতের polynomial-এর বড়জোর d-টি মূল) আর ∑_{d ∣ n} φ(d) = n অভেদটি, যা ব্লক ২-এ পরীক্ষা করেছেন। পূর্ণ প্রমাণ সংখ্যাতত্ত্বের যেকোনো প্রচলিত পাঠ্যবইয়ে (যেমন Niven–Zuckerman–Montgomery বা Burton-এর বইয়ে primitive root অধ্যায়) পাবেন। এটি একটি অস্তিত্বের উপপাদ্য: কোন সংখ্যাটি primitive root, তা বলার কোনো সহজ সূত্র জানা নেই, তাই বাস্তবে p − 1-এর মৌলিক উৎপাদক জেনে প্রার্থীদের পরীক্ষা করা হয়। ছোট উদাহরণ: mod 7-এ order-গুলো 1 (a = 1), 3 (a = 2, 4), 6 (a = 3, 5), 2 (a = 6). সবগুলো 6-এর ভাজক, আর primitive root 3 ও 5, মোট φ(6) = 2টি। আর m = 8-এ primitive root নেই: 3, 5, 7 সবার বর্গ ≡ 1 (mod 8), অথচ φ(8) = 4.

বাজারঘরের কুপনে এর সরাসরি অর্থ আছে। গুণক 3 হলে mod 7-এ ছয় দিনে ছয়টি আলাদা কুপন আসে, কারণ 3 একটি primitive root. গুণক 2 হলে মাত্র তিনটি কুপন (2, 4, 1) ঘুরে ঘুরে আসে, কারণ ord₇(2) = 3; আর গুণক 6 হলে মাত্র দুটি (6, 1). যে নিয়ম যত লম্বা চক্র দেয়, কুপন তত কম পুনরাবৃত্ত হয়। “গুণ করে ভাগশেষ নাও” ধাঁচের pseudorandom সংখ্যা বানানোর পদ্ধতিতে তাই গুণক হিসেবে primitive root বাছা হয়; এই ধরনের generator পর্ব ২৬ “সংখ্যাতত্ত্বের প্রয়োগ — check digit, hashing আর pseudorandom সংখ্যা”-এ আসবে।

Primitive root g থাকলে প্রতিটি সহমৌলিক ভাগশেষ x-কে x ≡ g^k হিসেবে লেখা যায়, আর এই k-কে বলে x-এর discrete logarithm. g আর k থেকে x বের করা দ্রুত (repeated squaring), কিন্তু x থেকে k বের করা বড় p-তে কঠিন বলে বিশ্বাস করা হয়। Diffie–Hellman key exchange এই অসমতার ওপর দাঁড়িয়ে, যা পর্ব ২৯ “Discrete logarithm আর Diffie–Hellman key exchange”-এ আসবে।

নিচের ব্লক Euler-এর উপপাদ্য আর উপপাদ্য ৫.২ m < 300-এর সব সহমৌলিক জোড়ায় পরীক্ষা করে, §৪-এর দুটি হিসাব মেলায়, gcd শর্ত ভাঙলে কী হয় দেখায়, আর mod 11-এর order ও primitive root খোঁজে।

from math import gcd

def phi(n):
    return sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)

def order(a, m):                        # smallest k >= 1 with a^k ≡ 1 (mod m)
    k, x = 1, a % m
    while x != 1:
        x, k = x * a % m, k + 1
    return k

PH = {m: phi(m) for m in range(2, 300)}
pairs = [(a, m) for m in range(2, 300) for a in range(1, m) if gcd(a, m) == 1]
print("Euler's theorem on", len(pairs), "pairs (a, m), m < 300:",
      all(pow(a, PH[m], m) == 1 for a, m in pairs))
print("ord_m(a) divides phi(m) on all of them:",
      all(PH[m] % order(a, m) == 0 for a, m in pairs))

e = 100000 % 30                         # phi(31) = 30
print("3^100000 mod 31: exponent ->", e, "  answer", pow(3, e, 31),
      "  direct", pow(3, 100000, 31))
print("7^2026 mod 100: 2026 mod 40 =", 2026 % 40, " answer", pow(7, 26, 100),
      "  ord_100(7) =", order(7, 100))

print("gcd(2, 12) = 2: 2^5 mod 12 =", pow(2, 5, 12),
      " but 2^(5 mod 4) mod 12 =", pow(2, 5 % 4, 12))

print("orders mod 11:", {a: order(a, 11) for a in range(1, 11)})
roots = [a for a in range(1, 11) if order(a, 11) == 10]
print("primitive roots mod 11:", roots, " count =", len(roots), "= phi(10) =", phi(10))
print("powers of 2 mod 11:", [pow(2, k, 11) for k in range(1, 11)])

Euler's theorem on 27317 pairs (a, m), m < 300: True
ord_m(a) divides phi(m) on all of them: True
3^100000 mod 31: exponent -> 10   answer 25   direct 25
7^2026 mod 100: 2026 mod 40 = 26  answer 49   ord_100(7) = 4
gcd(2, 12) = 2: 2^5 mod 12 = 8  but 2^(5 mod 4) mod 12 = 2
orders mod 11: {1: 1, 2: 10, 3: 5, 4: 5, 5: 5, 6: 10, 7: 10, 8: 10, 9: 5, 10: 2}
primitive roots mod 11: [2, 6, 7, 8]  count = 4 = phi(10) = 4
powers of 2 mod 11: [2, 4, 8, 5, 10, 9, 7, 3, 6, 1]

৬ · Wilson-এর উপপাদ্য — factorial দিয়ে মৌলিকতা

Fermat-এর প্রমাণে (p − 1)! এসেছিল শুধু কেটে দেওয়ার জন্য। কিন্তু (p − 1)! mod p নিজেই একটি সুন্দর মান নেয়। p = 7-এ 6! = 720 = 7 · 102 + 6, অর্থাৎ 6! ≡ 6 ≡ −1 (mod 7).

প্রমাণ (⇒, p মৌলিক): p = 2-এ 1! = 1 ≡ −1 (mod 2), তাই ধরুন p বিজোড়।

1. {1, …, p − 1}-এর প্রতিটি a-এর একটি অনন্য inverse a⁻¹ আছে এই সেটের মধ্যেই, কারণ p মৌলিক (Corollary ২.২(খ)). — inverse-এর অস্তিত্ব আর অনন্যতা
2. কোন a নিজের inverse? a² ≡ 1 ⇔ p ∣ (a − 1)(a + 1) ⇔ p ∣ a − 1 বা p ∣ a + 1 ⇔ a = 1 বা a = p − 1. — Euclid-এর lemma
3. বাকি p − 3টি সংখ্যা (2 থেকে p − 2) তাই জোড়ায় জোড়ায় ভাগ হয়, প্রতিটি জোড়া {a, a⁻¹}, আর প্রতিটি জোড়ার গুণফল ≡ 1. — জোড়া বাঁধা
4. অতএব (p − 1)! ≡ 1 · 1 ⋯ 1 · (p − 1) ≡ −1 (mod p). — গুণ congruence মানে

প্রমাণ (⇐, contrapositive): n যৌগিক হলে n-এর একটি ভাজক d আছে, 1 < d < n. d সংখ্যাটি (n − 1)!-এর একটি উৎপাদক, তাই d ∣ (n − 1)!. যদি (n − 1)! ≡ −1 (mod n) হতো, তবে d ∣ (n − 1)! + 1-ও হতো, ফলে d ∣ 1, যা অসম্ভব। ∎

p = 7-এ জোড়াগুলো চোখে দেখুন: 2 · 4 = 8 ≡ 1, 3 · 5 = 15 ≡ 1, আর 1 ও 6 নিজেরাই নিজেদের inverse. তাই 6! ≡ 1 · (2 · 4) · (3 · 5) · 6 ≡ 6 ≡ −1. ফলটি Edward Waring ১৭৭০ সালে তাঁর ছাত্র John Wilson-এর নামে প্রমাণ ছাড়া প্রকাশ করেন, আর প্রথম প্রমাণ দেন Joseph-Louis Lagrange ১৭৭১ সালে বলে সাধারণত উল্লেখ করা হয়; এর অনেক আগে Ibn al-Haytham (প্রায় ১০০০ খ্রিস্টাব্দ) ফলটি জানতেন বলেও কিছু ইতিহাসবিদ মনে করেন।

যৌগিক n-এ (n − 1)! mod n আসলে আরও সরল: n > 4 হলে এটি সবসময় 0. কারণ n = ab, 1 < a ≤ b < n লিখুন। a < b হলে a আর b দুটিই 1, 2, …, n − 1-এর আলাদা সদস্য, তাই ab = n গুণফলটিকে ভাগ করে। a = b হলে n = a² (n > 4 বলে a ≥ 3), আর তখন a ও 2a দুটিই n − 1-এর চেয়ে ছোট আলাদা সংখ্যা (2a < a²), তাই a · 2a = 2n গুণফলটিকে ভাগ করে। একমাত্র ব্যতিক্রম n = 4: 3! = 6 ≡ 2 (mod 4).

উপপাদ্যটি মৌলিকতার একটি নিখুঁত পরীক্ষা, শর্ত দুই দিকেই খাটে। তবু কেউ এটি দিয়ে মৌলিকতা যাচাই করেন না: (n − 1)! mod n বের করতে n − 2টি গুণ লাগে, যা trial division-এর √n-টি ভাগের চেয়েও অনেক ধীর। 30 অঙ্কের n-এ এটি অসম্ভব রকম লম্বা। মৌলিকতা পরীক্ষার দ্রুত পথ খুঁজতে আমাদের Fermat-এর দিকেই ফিরতে হবে।

৭ · Fermat-এর পরীক্ষা, pseudoprime আর Carmichael সংখ্যা

Fermat-এর উপপাদ্যকে উল্টো দিক থেকে পড়লে একটি পরীক্ষা পাওয়া যায়: কোনো 1 < a < n নিয়ে aⁿ⁻¹ mod n বের করুন (repeated squaring-এ বড়জোর কয়েক হাজার গুণ, এমনকি n কয়েক শ অঙ্কের হলেও)। ফল 1 না হলে n নিশ্চিতভাবে যৌগিক, কারণ মৌলিক হলে ফল 1 হতেই হতো (contrapositive). এই হলো Fermat-এর পরীক্ষা। উদাহরণ: 2¹⁴ mod 15 = 4 ≠ 1, তাই 15 যৌগিক, একটিও উৎপাদক না খুঁজেই।

কিন্তু ফল 1 হলে? তখন n মৌলিক হতে পারে, প্রমাণ নয়। কারণ “p মৌলিক ⇒ a^p−1 ≡ 1” উপপাদ্যের converse সত্য নয়। পর্ব ০৮-এ দেখেছেন, একটি implication প্রমাণ করলে তার converse প্রমাণ হয় না।

সবচেয়ে ছোট base-2 pseudoprime 341 = 11 · 31: 2³⁴⁰ ≡ 1 (mod 341). কেন? 2¹⁰ = 1024 = 3 · 341 + 1, অর্থাৎ 2¹⁰ ≡ 1 (mod 341), আর 10 ∣ 340. তবে base 3 নিলে 3³⁴⁰ ≡ 56 (mod 341), তাই দ্বিতীয় base 341-কে ধরে ফেলে। Carmichael সংখ্যায় এই কৌশলও চলে না: সহমৌলিক যে base-ই নিন, ফল 1. সবচেয়ে ছোটটি 561 = 3 · 11 · 17. এটি চেনার একটি সহজ নিয়ম আছে।

561-এ (⇐) দিকের প্রমাণ: 561 − 1 = 560, আর 2 ∣ 560, 10 ∣ 560, 16 ∣ 560. ধরুন gcd(a, 561) = 1.

1. 3 ∤ a, তাই Fermat-এ a² ≡ 1 (mod 3), আর 560 = 2 · 280 বলে a⁵⁶⁰ ≡ 1 (mod 3). — Fermat, p = 3
2. একইভাবে a¹⁰ ≡ 1 (mod 11) থেকে a⁵⁶⁰ ≡ 1 (mod 11), আর a¹⁶ ≡ 1 (mod 17) থেকে a⁵⁶⁰ ≡ 1 (mod 17). — Fermat, p = 11, 17
3. 3, 11, 17 পরস্পর সহমৌলিক, আর প্রত্যেকে a⁵⁶⁰ − 1-কে ভাগ করে, তাই তাদের গুণফল 561-ও ভাগ করে: a⁵⁶⁰ ≡ 1 (mod 561). ∎ — সহমৌলিক ভাজকের গুণফলও ভাজক

এই যুক্তি যেকোনো squarefree n-এ (⇐) দিকটি প্রমাণ করে; উল্টো দিকের প্রমাণে primitive root লাগে, তাই এখানে শুধু বিবৃতি। Alwin Korselt শর্তটি ১৮৯৯ সালে দেন, কিন্তু কোনো উদাহরণ দেননি বলে উল্লেখিত; Robert Carmichael ১৯১০ সালে 561 খুঁজে পান। (চেক প্রজাতন্ত্রের গণিতবিদ Václav Šimerka ১৮৮৫ সালেই প্রথম কয়েকটি এমন সংখ্যার তালিকা দিয়েছিলেন বলে পরে জানা যায়।)

Korselt-এর শর্ত থেকে Carmichael সংখ্যার আকার সম্পর্কে দুটি তথ্য সহজেই প্রমাণ হয়। প্রথমত, এরা বিজোড়: n জোড় আর squarefree যৌগিক হলে n-এর একটি বিজোড় মৌলিক উৎপাদক p আছে, তখন p − 1 জোড়, কিন্তু n − 1 বিজোড়, তাই (p − 1) ∣ (n − 1) অসম্ভব। দ্বিতীয়ত, এদের অন্তত তিনটি মৌলিক উৎপাদক থাকে: n = pq (p < q) হলে n − 1 = p(q − 1) + (p − 1), তাই (q − 1) ∣ (n − 1) মানে (q − 1) ∣ (p − 1), যা অসম্ভব কারণ 0 < p − 1 < q − 1. 561, 1105, 1729 সবারই ঠিক তিনটি উৎপাদক।

নিচের ব্লক 10⁴-এর নিচে সব base-2 pseudoprime খোঁজে, Korselt-এর শর্ত দিয়ে 10⁵-এর নিচে সব Carmichael সংখ্যা বের করে (একটি smallest-prime-factor sieve দিয়ে উৎপাদক বের করে), 561-কে সব সহমৌলিক base-এ সরাসরি যাচাই করে, আর ছোট n-এ Wilson-এর উপপাদ্য দেখায়।

from math import gcd, factorial

def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))

psp = [n for n in range(3, 10**4, 2) if pow(2, n - 1, n) == 1 and not is_prime(n)]
print("base-2 Fermat pseudoprimes below 10^4:", len(psp), psp[:8], "...")
print("341 = 11*31:  2^340 mod 341 =", pow(2, 340, 341),
      "  3^340 mod 341 =", pow(3, 340, 341))

N = 10**5
spf = list(range(N))                    # smallest-prime-factor sieve
for i in range(2, int(N ** 0.5) + 1):
    if spf[i] == i:
        for j in range(i * i, N, i):
            if spf[j] == j:
                spf[j] = i

def factors(n):
    out = []
    while n > 1:
        out.append(spf[n])
        n //= spf[n]
    return out

def korselt(n):     # composite, squarefree, (p - 1) | (n - 1) for each prime p | n
    f = factors(n)
    return len(f) >= 2 and len(set(f)) == len(f) and all((n - 1) % (p - 1) == 0 for p in f)

car = [n for n in range(3, N, 2) if korselt(n)]
print("Carmichael numbers below 10^5:", len(car), car[:6], "...")
print("561 = 3*11*17 passes for every coprime base:",
      all(pow(a, 560, 561) == 1 for a in range(1, 561) if gcd(a, 561) == 1))
print("but 3^560 mod 561 =", pow(3, 560, 561), " because gcd(3, 561) =", gcd(3, 561))
print("n < 40 with (n-1)! mod n == n-1:", [n for n in range(2, 40) if factorial(n - 1) % n == n - 1])

base-2 Fermat pseudoprimes below 10^4: 22 [341, 561, 645, 1105, 1387, 1729, 1905, 2047] ...
341 = 11*31:  2^340 mod 341 = 1   3^340 mod 341 = 56
Carmichael numbers below 10^5: 16 [561, 1105, 1729, 2465, 2821, 6601] ...
561 = 3*11*17 passes for every coprime base: True
but 3^560 mod 561 = 375  because gcd(3, 561) = 3
n < 40 with (n-1)! mod n == n-1: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

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

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

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

1. শর্ত: 13 মৌলিক, 13 ∤ 2. Fermat-এ 2¹² ≡ 1 (mod 13).
2. 1000 = 12 · 83 + 4, তাই 2¹⁰⁰⁰ ≡ 2⁴ = 16 ≡ 3 (mod 13). উত্তর 3.

অঙ্ক ২: 7²⁰²⁶-এর শেষ দুই অঙ্ক কী?

1. শেষ দুই অঙ্ক মানে mod 100. gcd(7, 100) = 1, φ(100) = 100 · (1 − 1/2)(1 − 1/5) = 40.
2. Euler-এ 2026 mod 40 = 26, তাই 7²⁰²⁶ ≡ 7²⁶ (mod 100). আরও ছোট করতে লক্ষ করুন 7² = 49, 7⁴ = 2401 ≡ 1 (mod 100).
3. 26 = 4 · 6 + 2, তাই 7²⁶ ≡ 7² = 49. উত্তর: শেষ দুই অঙ্ক 49.

অঙ্ক ৩: mod 13-এ কয়টি primitive root, আর 2 কি তাদের একটি?

1. 13 মৌলিক, তাই primitive root আছে, আর তাদের সংখ্যা φ(φ(13)) = φ(12) = 4.
2. ord₁₃(2) হতে হবে 12-এর একটি ভাজক: 1, 2, 3, 4, 6 বা 12. 12-এর মৌলিক উৎপাদক 2 আর 3, তাই শুধু 12/2 = 6 আর 12/3 = 4 পরীক্ষা করলেই চলে: 2⁴ = 16 ≡ 3 আর 2⁶ = 64 ≡ 12 (mod 13), কোনোটি 1 নয়।
3. তাই ord₁₃(2) = 12, আর 2 একটি primitive root. (চারটি primitive root হলো 2, 6, 7, 11.)

ধাপ ২-এর কৌশলটি মনে রাখুন: g primitive root mod p ⇔ p − 1-এর প্রতিটি মৌলিক উৎপাদক q-তে g^(p−1)/q ≢ 1. কারণ order যদি p − 1-এর একটি ছোট ভাজক হয়, তবে সেটি অন্তত একটি (p − 1)/q-কে ভাগ করে।

প্রমাণের ভুল ধরুন: “Fermat-এর পরীক্ষায় পাস মানেই মৌলিক”

একজন লিখলেন: “দাবি: n > 2 বিজোড় আর 2ⁿ⁻¹ ≡ 1 (mod n) হলে n মৌলিক। প্রমাণ: Fermat-এর ছোট উপপাদ্য বলে মৌলিক p-তে 2^p−1 ≡ 1. এখানে n-এ ঠিক এই সম্পর্কটি সত্য, তাই n মৌলিক। ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: প্রমাণটি “P ⇒ Q” থেকে “Q ⇒ P” টেনেছে, অর্থাৎ converse-কে সত্য ধরেছে (affirming the consequent, পর্ব ০৬-এর একটি পরিচিত ভুল যুক্তি)। একটি counterexample-ই দাবিটি বাতিল করে: n = 341 = 11 · 31 বিজোড় ও যৌগিক, তবু 2³⁴⁰ ≡ 1 (mod 341). সঠিক বক্তব্য শুধু এক দিকে: 2ⁿ⁻¹ ≢ 1 (mod n) হলে n যৌগিক।

৯ · AI-এর যুগে — ঘাত, φ আর প্রমাণের হিসাব যাচাই

AI সহকারী এই বিষয়ের প্রশ্নে খুব আত্মবিশ্বাসী উত্তর দেয়, কিন্তু বড় সংখ্যার মাথায় হিসাবে আর উপপাদ্যের শর্তে নিয়মিত ভুল করে। কয়েকটি ধরন, আর কীভাবে ধরবেন:

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

• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত (মৌলিক, সহমৌলিক) এই সংখ্যায় নিজে মিলিয়েছি
• চূড়ান্ত ভাগশেষ pow(a, b, m) দিয়ে সরাসরি মিলিয়েছি
• φ-এর মান সূত্র আর brute force দুই পথে মিলিয়েছি
• কোনো ধাপে converse বা অ-সহমৌলিক সংখ্যা কাটা নিঃশব্দে ঢোকেনি
• দাবিটি ছোট সংখ্যায় brute force করে বা এলোমেলো ইনপুটে পরীক্ষা করেছি, আর counterexample খুঁজেছি
• ইতিহাসের সাল, নাম আর উল্লেখ করা বই বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

সবচেয়ে সস্তা প্রথম পরীক্ষা: AI যে সংখ্যাটি দিল, সেটি এক লাইনের Python-এ মিলিয়ে নিন। এই পর্বের প্রায় প্রতিটি দাবি ছোট সংখ্যায় এক সেকেন্ডে পরীক্ষা করা যায়, আর একটি অমিলই পুরো উত্তরকে সন্দেহজনক করে।