Advanced number theory — হিসাবের দৃশ্যমান ধাপ¶

Extended Euclid: gcd(99,78)=3¶

নিচে নামা: remainder	ওপরে ওঠা: substitution
99 = 1×78 + 21	3 = 14×78 − 11×99
78 = 3×21 + 15	3 = 3×78 − 11×21
21 = 1×15 + 6	3 = 3×15 − 2×21
15 = 2×6 + 3	3 = 15 − 2×6
6 = 2×3 + 0	এখান থেকে ওপরে পড়ো

শেষে x=-11, y=14। সরাসরি যাচাই: 99×(-11)+78×14=-1089+1092=3। শুধু remainder নয়, পুরোনো সংখ্যার linear combination-ও ধরে রেখেছি।

CRT: দুটি ভাগশেষের মিল¶

x % 3 = 2, x % 5 = 3; 0 থেকে 14-এর মধ্যে:

শর্ত	মেলে এমন সব মান
mod 3-এ 2	2,5,8,11,14
mod 5-এ 3	3,8,13
দুই তালিকার ছেদ	8

3 ও 5 coprime, তাই সমাধান x = 8 + 15k, integer k-এর জন্য। প্রথম তিনটি nonnegative উত্তর 8,23,38।

Matrix power: 13টি transition¶

flowchart LR
    A["T: 1 ধাপ"] -->|"square"| B["T²: 2 ধাপ"]
    B -->|"square"| C["T⁴: 4 ধাপ"]
    C -->|"square"| D["T⁸: 8 ধাপ"]
    D --> E["T¹³ = T⁸ × T⁴ × T"]

13-এর binary 1101; জ্বলা bit-এর powers নিই। Fibonacci-তে T=[[1,1],[1,0]], initial column [F1,F0]=[1,0]; এক ধাপে [1,1], দুই ধাপে [2,1], তিন ধাপে [3,2]। State-এর order বদলালে matrix-ও বদলাবে।

Segmented sieve: [10,20]¶

√20 পর্যন্ত prime হলো 2 ও 3। 2 কাটে 10,12,14,16,18,20; 3 নতুন করে কাটে 15। অবশিষ্ট prime 11,13,17,19। প্রথম কাটার স্থান max(p*p, ceil(L/p)*p)—এতে range-এর মধ্যে p থাকলেও p নিজে বাদ পড়ে না। 0 ও 1 থাকলে আলাদাভাবে বাদ দিতে হবে।

Diophantine সমাধানের পরিবার¶

99x+78y=3-এর একটি সমাধান (−11,14)। GCD=3 বলে x=-11+26t, y=14-33t।

t	x	y	99x+78y
−1	−37	47	3
0	−11	14	3
1	15	−19	3

ax+by=c-এ gcd(a,b) যদি c-কে ভাগ না করে, integer সমাধান নেই।

Möbius-এর তিন রকম ফল¶

n	prime factorization	μ(n)
1	কোনো prime factor নেই	1
6	2×3, দুটি ভিন্ন prime	+1
30	2×3×5, তিনটি ভিন্ন prime	−1
12	2²×3, square factor আছে	0

Totient-এর 12-এর উদাহরণ মৌলিক number theory চিত্রে আছে। μ একই সংখ্যা গোনা inclusion–exclusion-এর sign সংগঠিত করতে সাহায্য করে।

Miller–Rabin: একটি base-এর ফল কী বোঝায়¶

n	n−1 = d×2ˢ	base 2-এ প্রথম x=2ᵈ mod n	পরের square	সিদ্ধান্ত
13	3×2²	8	12 = n−1	এই base-এ pass
21	5×2²	11	16, n−1 নয়	composite নিশ্চিত

একটি base-এ pass মানেই prime নিশ্চিত নয়। প্রথম x=1 বা n−1 হলেও pass; অন্যথায় নির্ধারিত square-গুলোর কোনোটি n−1 হতে হবে। Deterministic ফলের জন্য পরীক্ষিত base set ও তার integer সীমা মানতে হবে।

Pollard rho: পুরো n-এ সমান হওয়ার আগেই factor মেলে¶

n=91, f(x)=(x²+1)%91, দুজনের শুরু x=y=2।

flowchart LR
    A["শুরু: 2"] --> B["f(2)=5"] --> C["f(5)=26"]
    B --> D["কচ্ছপ x=5"]
    C --> E["খরগোশ y=26"]
    D --> F["gcd(abs(5-26),91)=7"]
    E --> F

5 ও 26 modulo 7-এ সমান, তাই factor 7 পাওয়া গেল। gcd=1 হলে চালাই; gcd=n হলে এই চেষ্টা ব্যর্থ, অন্য seed/constant নিয়ে শুরু করি।

ধারণায় ফিরি · সব সমস্যা ও অনুশীলন · মূল উৎস