মডুলার পাটীগণিত

মডুলার পাটিগণিত গণিতের একটি শাখা যেখানে পূর্ণসংখ্যা এবং নির্দিষ্ট একটি সংখ্যার পর সংখ্যাগুলো পুনরায় ফিরে আসা নিয়ে আলোচনা করা হয়। এই নির্দিষ্ট সংখ্যাকে বলা হয় মডুলাস (modulus , বহুবচন : moduli)। আধুনিক মডুলার পাটীগণিতের জনক হলেন জার্মান গণিতবিদ কার্ল ফ্রেডরিক গাউস। ১৮০১ সালে এ সম্বন্ধে তার Disquisitiones Arithmeticae বইটি প্রকাশিত হয়।

১২-ঘণ্টা ঘড়িতে মডুলার পাটিগণিত ব্যবহৃত হয়। একদিনকে দুইভাগে ভাগ করে সময় দেখায় এই ঘড়ি। যদি ঘড়িতে এখন ৭:০০ বেজে থাকে তাহলে ৮ ঘণ্টা পর ৩:০০ টা বাজবে। চিরায়িত যোগের নিয়মানুযায়ী এটা ৭ + ৮ = ১৫ হওয়া উচিত ছিল। কিন্তু ১২-ঘণ্টা ঘড়ির সময় অনুযায়ী ১৫ টা বলে কিছু নেই। অর্থাৎ ১২ টার পর পুনরায় ১ তারপর ২, তারপর ৩ ... এভাবে চলবে। তাই ৮ ঘণ্টা পর ৩ টা বাজবে।

কংগ্রুয়েন্স সম্পর্কের সংজ্ঞা

মডুলার পাটীগণিত গাণিতিকভাবে প্রকাশের জন্য পূর্ণসংখ্যার কংগ্রুয়েন্স সম্পর্ক নামে নতুন এক সম্পর্ক এমনভাবে সংজ্ঞায়িত করা হয় যেন সেটি পূর্ণসংখ্যার চিরায়িত অপারেশন যোগ,বিয়োগ এবং গুণের সাথে সামঞ্জস্যপূর্ণ হয়। যেকোন ধনাত্মক পূর্ণসংখ্যা $n$ এর জন্য, দুটি পূর্ণসংখ্যা $a$ এবং b কে কংগ্রুয়েন্স মডুলো n বলা হয়, যদি তাদের পার্থক্য $a - b$ , $n$ এর গুণিতক হয় (অর্থাৎ এমন একটি পূর্ণসংখ্যা k থাকবে যেন $a - b = kn$ হয়). গাণিতিকভাবে,

a\equiv b{\pmod {n}}.

এখানে $n$ কে কংগ্রুয়েন্সের মডুলাস বলা হয়।

কংগ্রুয়েন্স সম্পর্ক নিম্নোক্ত উপায়েও লেখা যায়,

a=kn+b,

যা কিনা ইউক্লিডীয় বিভাজনের সাথে সরাসরি সম্পর্কিত। যদিও, a কে n দ্বারা ভাগ করলে b ভাগশেষ নাও হতে পারে। আরও ভালোভাবে বললে, $a \equiv b mod n$ এর অর্থ হল $a$ এবং $b$ কে $n$ দ্বারা ভাগ করলে একই ভাগশেষ থাকবে।

a=pn+r,

b=qn+r,

যেখানে, $0 \leq r < n$ হল সাধারণ ভাগশেষ। এই সমীকরণ দুটি বিয়োগ করে আমরা পূর্বের সম্পর্কটি পাই :

a-b=kn,

যেখানে k = p − q.

উদাহরণ

উদাহরণস্বরূপ,

38\equiv 14{\pmod {12}}\,

কারণ 38 − 14 = 24, যা কিনা 12 এর গুণিতক।

ঋণাত্মক সংখ্যার জন্যই একই নিয়ম প্রযোজ্য :

{\begin{aligned}-8&\equiv 7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}

একইভাবে, $a \equiv b mod n$ এর অর্থ হল $a$ এবং $b$ কে $n$ দ্বারা ভাগ করলে একই ভাগশেষ থাকে। উদাহরণস্বরূপ,

38\equiv 14{\pmod {12}}\,

কারণ 38 এবং 14 উভয়কে 12 দ্বারা ভাগ করলে 2 ভাগশেষ থাকে।আবার 38 − 14 = 24 যা কিনা 12 এর গুণিতক। তাই এটি কংগ্রুয়েন্সের মূল সংজ্ঞার সাথে সঙ্গতিপূর্ণ।

বৈশিষ্ট্য

কংগ্রুয়েন্স সম্পর্ক সমতুল্য সম্পর্কের সকল শর্ত সিদ্ধ করে :

Reflexivity: a ≡ a (mod n)
প্রতিসাম্যতা : a ≡ b (mod n) যদি ও কেবল যদি b ≡ a (mod n)
Transitivity: যদি a ≡ b (mod n) এবং b ≡ c (mod n) হয়, তাহলে a ≡ c (mod n)

যদি a₁ ≡ b₁ (mod n) এবং a₂ ≡ b₂ (mod n), অথবা যদি a ≡ b (mod n), হয় তাহলে :

a + k ≡ b + k (mod n) , যেকোন পূর্ণসংখ্যা k এর জন্য $k$
k a ≡ k b (mod n) , যেকোন পূর্ণসংখ্যা k এর জন্য
a₁ + a₂ ≡ b₁ + b₂ (mod n) (যোগের সাথে সামঞ্জস্যপূর্ণ)
a₁ – a₂ ≡ b₁ – b₂ (mod n) (বিয়োগের সাথে সামঞ্জস্যপূর্ণ)
a₁ a₂ ≡ b₁ b₂ (mod n) (গুণের সাথে সামঞ্জস্যপূর্ণ)
a^k ≡ b^k (mod n) , যেকোন পূর্ণসংখ্যা k এর জন্য (সূচকের সাথে সামঞ্জস্যপূর্ণ)
p(a) ≡ p(b) (mod n), যেকোন পূর্ণসাংখ্যিক সহগবিশিষ্ট বহুপদী p(x) এর জন্য (বহুপদীর মান নির্ণয়ের সাথে সামঞ্জস্যপূর্ণ)

যদি a ≡ b (mod n) হয়, সাধারণভাবে k^a ≡ k^b (mod n) সত্য নয়। যদিও,

যদি c ≡ d (mod φ(n)), হয় যেখানে φ হল অয়লারের টোশেন্ট ফাংশন।, তাহলে a^c ≡ a^d (mod n) হবে, যেখানে $a$ এবং $n$ সহমৌলিক।

উভয়পক্ষ থেকে সাধারণ পদ বাদ দিতে হলে নিম্নোক্ত নিয়ম রয়েছে :

যদি a + k ≡ b + k (mod n) হয়, যেকোন পূর্ণসংখ্যা k জন্য $k$ , তাহলে a ≡ b (mod n)
যদি k a ≡ k b (mod n) এবং k ও n সহমৌলিক হয়, তাহলে a ≡ b (mod n)

সবশেষে, a এর গুণাত্মক বিপরীত (multiplicative inverse) কে $a -1$ দ্বারা সূচিত করে, আমরা নিম্নোক্ত নিয়মগুলো পাই :

গুণাত্মক বিপরীতের অস্তিত্ব: একটি পূর্ণসংখ্যার অস্তিত্ব থাকবে, যা $a -1$ দ্বারা সূচিত করা হয়, যেন aa⁻¹ ≡ 1 (mod n) হবে যদি ও কেবল যদি $a$ ও n সহমৌলিক হয়.
যদি a ≡ b (mod n) এবং $a -1$ এর অস্তিত্ব থাকে, তাহলে a⁻¹ ≡ b⁻¹ (mod n) (গুণাত্মক বিপরীতের সাথে সামঞ্জস্যপূর্ণ)
যদি a x ≡ b (mod n) এবং $a$ ও n সহমৌলিক হয়, তাহলে এই সরলরৈখিক কংগ্রুয়েন্স সম্পর্কের সমাধান হল, x ≡ a⁻¹b (mod n)

যদি $p$ মৌলিক সংখ্যা হয় তাহলে $a$ এর সকল মানের জন্য $a$ এবং p সহমৌলিক হবে যেখানে $0 < a < p$ . সুতরাং $a$ যদি মডুলো $p$ তে শূন্যের সমতুল্য না হয় তাহলে a এর সকল মানের জন্য একটি গুণাত্মক বিপরীতের অস্তিত্ব থাকবে।

কংগ্রুয়েন্স সম্পর্কের আরও কিছু বিশেষ বৈশিষ্ট্য নিম্নরূপ :

অয়লারের উপপাদ্য (Euler's theorem): যদি $a$ এবং $n$ সহমৌলিক হয়, তাহলে a ^φ(n) ≡ 1 (mod n), যেখানে φ হল অয়লারের টোশেন্ট ফাংশন।

ফার্মার লিটল থিওরেম থেকে পাই, যদি $p$ মৌলিক হয় তাহলে a⁻¹ ≡ a ^{p − 2} (mod p) হল a এর গুণাত্মক বিপরীত যেখানে $0 < a < p$ . আরও সাধারণভাবে, অয়লারের উপপাদ্য অনুযায়ী, যদি $a$ এবং $n$ সহমৌলিক হয়, তাহলে a⁻¹ ≡ a ^{φ(n) − 1} (mod n).
আরেকটি অনুসিদ্ধান্ত হল, যদি a ≡ b (mod φ(n)), এবং k ও n সহমৌলিক হয়, যেখানে φ হল অয়লার টোশেন্ট ফাংশন]], তাহলে k^a ≡ k^b (mod n) হবে।
উইলসনের উপপাদ্য (Wilson's theorem): p $p$ মৌলিক সংখ্যা হবে যদি ও কেবল যদি (p − 1)! ≡ −1 (mod p) হয়।
চাইনিজ ভাগশেষ উপপাদ্য (Chinese remainder theorem): যদি x ≡ a (mod m) এবং x ≡ b (mod n) হয় যেন $m$ ও $n$ সহমৌলিক, তাহলে x ≡ b m_n⁻¹ m + a n_m⁻¹ n (mod mn) হবে, যেখানে $m n -1$ হল $m$ এর গুণাত্মক বিপরীত মডুলো $n$ এ এবং $n m -1$ হল $n$ এর গুণাত্মক বিপরীত মডুলো $m$ এ।
ল্যাগ্রেঞ্জের উপপাদ্য (Lagrange's theorem): f (x) ≡ 0 (mod p), যেখানে $p$ মৌলিক সংখ্যা এবং $f (x) = a 0 x n + ... + a n$ একটি বহুপদী যেন a₀ ≠ 0 (mod p), এই কংগ্রুয়েন্স সম্পর্কের সর্বোচ্চ $n$ সংখ্যক মূল থাকতে পারে।

তথ্যসূত্র

John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
টেমপ্লেট:Apostol IANT. অধ্যায় ৫ ও ৬ দ্রষ্টব্য।
Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. আইএসবিএন ০-২৬২-০৩২৯৩-৭. Section 31.3: Modular arithmetic, pp. 862–868.
Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. আইএসবিএন ০-৪৮৬-৪১৪৪৯-৩.
Long, Calvin T. (১৯৭২)। Elementary Introduction to Number Theory (2nd সংস্করণ)। Lexington: D. C. Heath and Company।
Pettofrezzo, Anthony J.; Byrkit, Donald R. (১৯৭০)। Elements of Number Theory। Englewood Cliffs: Prentice Hall।
Sengadir, T. (২০০৯)। Discrete Mathematics and Combinatorics। Chennai, India: Pearson Education India। আইএসবিএন 978-81-317-1405-8। ওসিএলসি 778356123।

বহিঃসংযোগ সমূহ

An article on modular arithmetic on the GIMPS wiki
Modular Arithmetic and patterns in addition and multiplication tables
Whitney Music Box—an audio/video demonstration of integer modular math