Modular Arithmetic: Introduction

মডুলার অ্যারিথমেটিক নিয়ে পড়ার আগে আমরা কিছু জিনিস রিক্যাপ করে নেই , যেগুলা আমরা ক্লাস ফাইভে পড়ে এসেছি ।

ভাজ্য = ভাজক × ভাগফল + ভাগশেষ বা, Dividend = Divisor × Quotient + Remainder

অনেকের যদি কোনটা কি জিনিস মনে না থাকে তাহলে পুরানো বইয়ের পাতা উলটে দেখতে পার , আর গুগল মামা তো আছেই ।

এবার অনেকর মনে প্রশ্ন আসবে , অমুক প্রবলেম তো সহজেই পাটিগণিত / সাধারণ নিয়মে সল্ভ করে ফেলা যায় , তাহলে এসব ম্যাথ করার জন্য মডুলার অ্যারিথমেটিক কেন শিখবো? তার উপর এটা তো একটা কঠিন টপিক ।

তাদের জন্য বলে রাখা, মডুলার অ্যারিথমেটিক হল এসব সাধারণ নিয়মগুলোর একটা কম্প্যাক্ট ফর্ম । তাই এভাবে করলে সহজেই অনেক প্রবলেম সল্ভ করে ফেলা যায় । যেগুলো কিনা সাধারণ ভাবে করলে অনেক বড় হয়ে যেত । আর সত্যি কথা বলতে মানুষকে কোন ম্যাথের সলিউশন বুঝাতে গেলে বেশি লেখা দেখলে ভয় পেয়ে যায়। কিন্তু মডুলার অ্যারিথমেটিক দিয়ে সল্ভ করলে কয়েক লাইনে হয়ে যায় বলে তারা ভয় পায় না। (just kidding :v​ )

Definition:⌗

আমরা অনেক সময় দেখে থাকি $a \text{ (mod b)}$ । এর মানে কি? সহজ করে বলতে গেলে এর মানে হল a কে b দিয়ে ভাগ করলে যেই ভাগশেষ থাকবে সেই সংখ্যাটা । উদাহরণস্বরূপ $5 \text{ (mod 3)}=2$

এখানে mod সাইনটা আসলে modulo(মডুলো) শব্দের সংক্ষিপ্ত রূপ ।

আমরা আবার অনেকসময় দেখে থাকি $a\equiv b \text{ (mod m)}$ এর মানেই বা কি?

কখনো যদি $a \text{ (mod m)}=b \text{ (mod m)}$ হয় , তখন আমরা সংক্ষেপে লিখতে পারি $a\equiv b \text{ (mod m)}$ । এবং এটাকে পড়তে হয় "a is congruent to b modulo m" এভাবে ।

এটাকে আমরা আরও একভাবে সংজ্ঞায়িত করতে পারি , যদি $(a-b)$ , $m$ দিয়ে নিঃশেষে ভাগ যায়, তাহলে আমরা লিখতে পারি $a\equiv b \text{ (mod m)}$ ।

আসলে দুইটা সংজ্ঞাই একই , একটু চিন্তা করলে বুঝতে পারবা।

Properties:⌗

আমরা কোন সমীকরণের দুইপাশে যেমন একই সংখ্যা দিয়ে যোগ , বিয়োগ, গুন করতে পারি ঠিক তেমনি আমরা মডুলার অ্যারিথমেটিকেও উভয় দিকে একই সংখ্যা দিয়ে যোগ বিয়োগ গুন করতে পারি । [ বিদ্রঃ উভয় দিকে একই সংখ্যা দিয়ে ভাগ করতে পারি না । ]

যেমন আমাদের রাশিটি যদি হয় $a\equiv b \text{ (mod m)}$ তাহলে কোন পূর্নসংখ্যা $k$ এর জন্য আমরা লিখতে পারি

• $a +k\equiv b+k \text{ (mod m)}$

  proof click to hide

  . $a\equiv b \text{ (mod m)}$ হলে আমি বলতে পারি $a-b=mp$ যেখানে p হল $(a-b)$ কে m দিয়ে ভাগ করলে যেই ভাগফল থাকবে সেইটা ( ২য় সংজ্ঞা দিয়ে চিন্তা কর) এখন , $a-b=mp$ = $(a+k)-(b+k)=mp$ তারমানে বলতে পারি , $a +k\equiv b+k \text{ (mod m)}$

• $a-k\equiv b-k \text{ (mod m)}$

  proof click to hide

  নিজে চেষ্টা কর।
  

• $a\times k\equiv b\times k \text{ (mod m)}$

  proof click to hide

  নিজে চেষ্টা কর।
  

আরও কিছু বৈশিষ্ট্য …

• $a \equiv b \text{ (mod m)}$ এবং $p \equiv q \text{ (mod m)}$ হলে $a+p \equiv b+q \text{ (mod m)}$
• $a \equiv b \text{ (mod m)}$ এবং $p \equiv q \text{ (mod m)}$ হলে $a-p \equiv b-q \text{ (mod m)}$
• $a \equiv b \text{ (mod m)}$ এবং $p \equiv q \text{ (mod m)}$ হলে $a\times p \equiv b\times q \text{ (mod m)}$

Residue class:⌗

কোন ধনাত্মক পূর্নসংখ্যা , $n$ দিয়ে অন্য যেকোনো পূর্নসংখ্যাকে ভাগ করলে ভাগশেষের সম্ভাব্য সকল সংখ্যাকে নিয়ে যে সেট হয় , তাকে রেসিডিউ ক্লাস বলে । সহজ ভাবে বললে , কোন পূর্ন সংখ্যা , $n$ দিয়ে অন্য যেকোনো পূর্নসংখ্যাকে ভাগ করি না কেন , ভাগশেষ অবশ্যই $0$ থেকে $n-1$ এর মধ্যে হবে ( $0$ এবং $n-1$ সহ ) । যেমনঃ $5$ দিয়ে কোন সংখ্যাকে ভাগ করলে ভাগশেষ হতে পারে ${0,1,2,3,4}$ । তাই $5$ এর রেসিডিউ ক্লাস হল ${0,1,2,3,4}$ ।

Divisibility Rule:⌗

• $2$ দিয়ে নিঃশেষে বিভাজ্য হওয়ার নিয়মঃ কোন সংখ্যার শেষ অংকটি যদি $2$ দিয়ে ভাগ যায় , অর্থাৎ $0,2,4,6,8$ এর মধ্যে যেকোনোটা হয় । তাহলে সংখ্যাটি $2$ দিয়ে বিভাজ্য ।

  proof click to hide

  . মনে করি সংখ্যাটি $n=10x+p$ । অর্থাৎ এর শেষ অংকটি হল $p$ । তাহলে আমরা বলতে পারি , $n\equiv 10x+p \text{ (mod 2)}$ $\Longrightarrow n\equiv 0+p \text{ (mod 2)}$ $\Longrightarrow \boxed{n\equiv p \text{ (mod 2)}}$ অর্থাৎ $p$ ( শেষ অংক) কে $2$ দিয়ে ভাগ করলে যেই ভাগশেষ থাকবে , $n$ কে $2$ দিয়ে ভাগ করলেও একই ভাগশেষ থাকবে ।

• $3$ দিয়ে নিঃশেষে বিভাজ্য হওয়ার নিয়মঃ

  কোন সংখ্যার অংকগুলোর যোগফল যদি $3$ দিয়ে ভাগ যায়, তাহলে সংখ্যাটিও $3$ দিয়ে ভাগ যাবে ।

  proof click to hide

  . মনে করি সংখ্যাটি $n=d_{0}+10d_{1}+100d_{2}+…+10^{k-1}d_{k-1}$

  সংক্ষেপে বললে , $n=\sum_{i=0}^{k-1}{10^{i}d_{i}}$ এখানে $n$ হল $k$ অংকের একটি সংখ্যা , এবং এর অংকগুলো হল , $d_{0},d_{1},d_{2},…,d_{k-1}$। যেখানে $d_{0}$ হল একক স্থানীয় অংক, $d_{1}$ হল দশক স্থানীয় অংক , … । এখন , $10^p\equiv10\times 10 \times … \times 10 \text{ (mod 3)}$ [মোট $p$ সংখ্যক $10$] $\Longrightarrow 10^{p}\equiv 1\times 1\times 1 \times … \times 1 \text{ (mod 3)} \equiv 1 \text{ (mod 3)}$

  অর্থাৎ , $n\equiv d_{0}+10d_{1}+100d_{2}+…+10^{k-1}d_{k-1}\text{ (mod 3)}$ $\Longrightarrow \boxed{n\equiv d_{0}+d_{1}+d_{2}+…+10d_{k-1} \text{ (mod 3)}}$

• $4$ দিয়ে নিঃশেষে বিভাজ্য হওয়ার নিয়মঃ

  কোন সংখ্যার শেষ দুই অংক নিয়ে গঠিত সংখ্যা যদি $4$ দিয়ে ভাগ যায়, তাহলে সংখ্যাটিও $4$ দিয়ে ভাগ যাবে ।

  proof click to hide

  . মনে করি সংখ্যাটি $n=d_{0}+10d_{1}+100d_{2}+…+10^{k-1}d_{k-1}$ $\Longrightarrow n\equiv d_{0}+10d_{1}+100d_{2}+…+10^{k-1}d_{k-1}\text{ (mod 4)}$ $\Longrightarrow \boxed{n\equiv d_{0}+10d_{1}\text{ (mod 4)}}$

• …

…চলবে…

Reference:⌗

• Brilliant Wiki (আমি যখন ব্রিলিয়ান্ট উইকি খুললাম তখন অবাক হয়ে গেলাম এটা দেখে যে সংজ্ঞার অংশ দুই জায়গায় ই একই :v )
• মডুলো অপারেশন - উইকিপিডিয়া
• Divisibility rule from wiki
• Some Misconception about modulo