Modulo — ঘর, চক্র ও inverse¶

Mod 5-এ 7 ধাপ এগোনো¶

flowchart LR
    A["0"] --> B["1"] --> C["2"] --> D["3"] --> E["4"] --> A

সম্পূর্ণ পথ: 0 → 1 → 2 → 3 → 4 → 0 → 1 → 2। তাই 7 % 5 = 2। ঘড়ির মতো ঘুরে আসি, মোট কয়বার ঘুরেছি সেই তথ্য আর রাখি না।

3⁵ mod 7: প্রতিটি binary-exponentiation ধাপ¶

শুরুতে exponent	result	base	কাজের পরে result	square-এর পরে base
5 (odd)	1	3	3	2
2 (even)	3	2	3	4
1 (odd)	3	4	5	2

প্রতিবার exponent-কে 2 দিয়ে integer divide করা হয়: 5 → 2 → 1 → 0। উত্তর 5। সরাসরি 3⁵=243, 243%7=5 দিয়েও মেলে।

ভাগের বদলে inverse¶

flowchart LR
    A["3 × 5 = 15 ≡ 1 mod 7"] --> B["3-এর inverse হলো 5"]
    B --> C["6 / 3 mod 7 = 6 × 5 mod 7 = 2"]
    C --> D["যাচাই: 2 × 3 mod 7 = 6"]

1/3 mod 7-এর মান 5; এটি integer division-এর 0 নয়। আমরা এমন x খুঁজছি যাতে 3x ≡ 1 (mod 7)।

Mod 6-এ 2-এর inverse নেই: 2x % 6 শুধু 0,2,4 হতে পারে, কখনো 1 নয়। তাই modular division-এর আগে gcd(ভাজক,modulus)=1 পরীক্ষা জরুরি।

যোগ, গুণ ও power-cycle¶

হিসাব	ছোট করে হিসাব	ফল
(9+8) mod 12	17 mod 12	5
(9−11) mod 12	−2-এর nonnegative remainder	10
(8×9) mod 5	(3×4) mod 5	2

7-এর positive powers-এর শেষ অঙ্কের পূর্ণ cycle:

flowchart LR
    A["7¹: 7"] --> B["7²: 9"] --> C["7³: 3"] --> D["7⁴: 1"] --> A

7⁶-এর শেষ অঙ্ক দ্বিতীয় ঘরের 9; কারণ (6−1)%4=1। Exponent 0 হলে আলাদা করে 7⁰=1।

nCr-এর তিন ধাপ: C(5,2) mod 7¶

flowchart LR
    A["numerator: 5! mod 7 = 1"] --> C["1 × inverse(5) mod 7"]
    B["denominator: 2! × 3! mod 7 = 5"] --> C
    C --> D["inverse(5)=3; উত্তর 3"]

সরাসরি C(5,2)=10, 10%7=3। এই factorial পদ্ধতিতে n<p রাখা হয়েছে।

ছোট rolling hash: একই remainder হলে collision হতে পারে¶

ধরি A=1, B=2, base=3, modulus=7; প্রতিটি অক্ষরে h=(h*3+value)%7।

string	প্রথম state	পরের state	hash
AB	1	(1×3+2)%7	5
BA	2	(2×3+1)%7	0

Hash ছোট range-এ অনেক string-কে বসায়; এটি দ্রুত প্রার্থী খোঁজে, সমতার নিশ্চয়তা দেয় না।

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