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

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

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

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

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

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

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

${\displaystyle a=kn+b,}$

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

${\displaystyle a=pn+r,}$

${\displaystyle b=qn+r,}$

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

${\displaystyle a-b=kn,}$

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

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

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

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

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

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

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

${\displaystyle 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): pp মৌলিক সংখ্যা হবে যদি ও কেবল যদি (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⁻¹ হল m এর গুণাত্মক বিপরীত মডুলো n এ এবং n_m⁻¹ হল n এর গুণাত্মক বিপরীত মডুলো m এ।
• ল্যাগ্রেঞ্জের উপপাদ্য (Lagrange's theorem): f (x) ≡ 0 (mod p), যেখানে p মৌলিক সংখ্যা এবং f (x) = a₀ xⁿ + ... + 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