আগে যা জানা লাগবে
সাধারণ মডুলার অ্যারিথমেটিক জানা থাকলেই চলবে। Big Mod সম্পর্কে ধারনা থাকলে ভাল হয়। তবে এটা ছাড়াও করা সম্ভব। না জেনে থাকলে এখান থেকে এবং এখান থেকে শিখে আসতে পারেন।
মডুলার ইনভার্স কেন দরকার?
সাধারনত সব কিছু তৈরির পিছনে কোন না কোন সমস্যা সমাধান এর উদ্দেশ্য থাকে। ইতিমধ্যে আমরা জানি আনেক বড় ক্যালকুলেশন মডুলার অ্যারিথমেটিক দিয়ে সহজে করে ফেলা যায়। কিন্তু এই কাজ আমরা ভাগ এর ক্ষেত্রে করতে পারি না। এর জন্যই আমাদের মডুলার ইনভার্স দরকার।
মডুলার অ্যারিথমেটিক থেকে আমরা জানি,
\[\begin{align*} (a + b) \mod M &\equiv (a \mod M + b \mod M) \mod M \\ (a - b) \mod M &\equiv (a \mod M - b \mod M) \mod M \\ (a \times b) \mod M &\equiv (a \mod M \times b \mod M) \mod M \end{align*}\]কিন্তু $\frac{a}{b} \mod M \not\equiv \frac{a \mod M}{b \mod M} \mod M$। ভাগের জন্য যে কেন কাজ করে না তার ছোট্ট একটা উদাহরণ দেই। আমরা যদি $\frac{21}{3} \mod 5$ বের করতে চাই আর উপরের মত করে করি তাহলে কি হয় দেখা যাক। $\frac{21 \mod 5}{3 \mod 5} \mod 5 = \frac{1}{3}$, যেটা আসলে ভুল। কারণ এটার উত্তর হবে $2$। কারণ, $\frac{21}{3} \mod 5$ আসলে $7 \mod 5$। যেটার উত্তর আমরা জানি $2$। কিন্তু সেটা উপরের পদ্ধতিতে উত্তর বের করা সম্ভব না। তাই আমার অন্য কোন উপায় বের করতে হবে। এর জন্যই আমাদের মডুলার ইনভার্স কাজে আসবে।
মডুলার ইনভার্স কি?
প্রথমে আমরা বোঝার চেষ্টা করি মডুলার ইনভার্স কোন ধরনের সংখ্যাকে বলে এরপর আমরা বোঝার চেষ্টা করব ওই ধরনের সংখ্যাগুলো কিভাবে ভাগ করতে সাহায্য করে। তো কোন একটা পূর্ণ সংখ্যা $b$ এর মডুলার ইনভার্স এমন কিছু পূর্ণ সংখ্যা $x$, যাতে $b \cdot x$ কে $M$ দিয়ে ভাগ করলে ভাগশেষ $1$ হয়। তাহলে বিষয়টা এমন দাঁড়াচ্ছে যে আমরা এমন একটা $x$ খুঁজে বের করতে চাচ্ছি যে,
\[b \cdot x \mod M = 1\]উপরের এই লাইনকে সাধারণত নিচের মত করে লিখা হয়,
\[\begin{equation} a \cdot x \equiv 1 \mod M \tag{১} \end{equation}\]দুইটা সমীকরণ দিয়েই একই জিনিস বুঝানো হয়। কিন্তু সাধারণত সব জায়গায় দ্বিতীয় সমীকরণ আকারে লিখা হয়ে থাকে। তো এইখানে $x$ হল এমন একটা সংখ্যা, যা দিয়ে $a$ কে গুন করলে যে গুণফল আসবে সেই গুনফলকে $M$ দিয়ে ভাগ করলে ভাগশেষ 1 হবে। $x$ কে আবার অনেক জায়গায় $b^{-1}$ এইভাবেও লিখা হয়।
একটা উদাহরণ দিলে হয়ত বিষয়টা পরিষ্কার হবে।
মনে করি, $b = 3$ এবং $M = 5$। তাহলে $b \mod M = 3$। এখন $b$ এর সাথে যদি $2$ গুন করি তাহলে $6 \mod 5 = 1$। তাহলে $2$ হচ্ছে $3$ এর মডুলার ইনভার্স যেখানে $5$ দিয়ে ভাগশেষ বের করা হবে। যেই সংখ্যা দিয়ে ভাগশেষ বের করছি সেইটা যদি পরিবর্তন হয়ে যায় তাহলে মডুলার ইনভার্সও পরিবর্তন হয়ে যাবে। আবার এইটার মডুলার ইনভার্স যে শুধু একটা সংখ্যা হবে এরকমও না। $x = 2, 7, 12, \dots$। এক্ষেত্রে $5x + 2$ এইখানে $x$ এর জায়গায় $0, 1, 2, \dots$ বসালে একটা করে মডুলার ইনভার্স পাওয়া যাবে। কিন্তু আমরা কাজ করার সময় সাধারণত সবচেয়ে ছোট সংখ্যাটা নিয়ে থাকি।
আশা করি, মডুলার ইনভার্স কোন সংখ্যাগুলাকে বলে সেটা বুঝতে পেরেছেন। এখন তাহলে মডুলার ইনভার্স কিভাবে আমাদের সমস্যা সমাধান এ সাহায্য করবে সেটা বুঝার চেষ্টা করব।
মডুলার ইনভার্স কেন কাজ করে?
আমাদের মুল সমস্যা ছিল $\frac{a}{b} \mod M$ বের করা। কিন্তু এইখানে মডুলার ইনভার্স কিভাবে সাহায্য করবে? আমি যখন মডুলার ইনভার্স শিখি তখন আমি যত জায়গায় লিখা পড়েছি সেখানে শুধু মডুলার ইনভার্স কিভাবে বের করে সেটা লিখা ছিল। কিন্তু কেন কাজ করে সেটা আমি পাইনি। তখন আমার মাথায় শুধু এই প্রশ্নই ঘুরপাক খেত। পরে যখন বিষয়টা আবিষ্কার করতে পেরেছি তখন আমার কাছে উপায়টা খুবই সুন্দর লেগেছে। আমি বিষয়টাকে যেভাবে উপলব্ধি করি সেটাই এখানে লিখার চেষ্টা করব, ইনশাআল্লাহ।
মনে করি, $b$ একটি পূর্ণসংখ্যা এবং $b$ এর মডুলার ইনভার্স $x$। এখন, মডুলার ইনভার্স এর সংজ্ঞা অনুযায়ী আমরা জানি,
\[b \cdot x \equiv 1 \mod M \tag{২}\]এখন,
\[\begin{align*} \frac{a}{b} \mod M &\equiv \frac{a}{b} \cdot 1 \mod M\\ &\equiv \frac{a}{b} \cdot bx \mod M \tag{২ নং সমীকরণ থেকে} \\ &\equiv a \cdot x \mod M \end{align*}\]এখান থেকে বোঝা যাচ্ছে যে $b$ দিয়ে ভাগ করা আর $a$ এর মডুলার ইনভার্স $x$ দিয়ে গুন করা একই কথা। তাহলে সর্বশেষ সমীকরণটা হল,
\[\frac{a}{b} \mod M \equiv a \cdot x \mod M \tag{৩}\]আমরা তাহলে কিছু সংখ্যা দিয়ে চেষ্টা করে দেখি।
উপরে যেই উদাহরণটা দিয়েছিলাম ওইটা দিয়েই আবার দেখি। তাহলে আমারদের $a = 21, b = 3, M = 5, x = 2$। আবার মনে করে দেই, এইখানে $x$ হচ্ছে $b$ এর মডুলার ইনভার্স যখন $M$ দিয়ে ভাগশেষ বের করা হবে। তাহলে আমাদের $\frac{21}{3} \mod 5$ বের করতে হবে। যেহেতু $3$ এর মডুলার ইনভার্স $2$ যখন $5$ দিয়ে ভাগশেষ বের করা হবে, সেহেতু সমীকরণ (৩) অনুযায়ী,
\[\begin{align*} \frac{21}{3} \mod 5 &= 21 \cdot 2 \mod 5\\ &= 42 \mod 5\\ &= 2\\ \end{align*}\]এইটার উত্তর আমি উপরে দেখিয়েছি যে $2$ হওয়ার কথা। এইখানেও তাই এসেছে। সুতরাং, আমরা বলতেই পারি যে, কোন একটা সংখ্যা দিয়ে ভাগ করে মডুলাস বের করি অথবা তার মডুলার ইনভার্স দিয়ে গুন করে মডুলাস বের করি উত্তর একই আসবে।
তাহলে আমাদের লাভ হল যে আগে আমরা ভাগ মডুলার অ্যারিথমেটিক দিয়ে করতে পারতাম না। কিন্তু এখন যখন আমরা ভাগকে গুনে পরিবর্তন করে ফেললাম, এখন ভাগের কাজ আমরা গুনের অ্যারিথমেটিক ব্যবহার করে করতে পারব।
পাঠকের কাজ
এখন আপনাদের কিছু কাজ আছে। এইযে আমি বললাম $b = 3$ এবং $M = 5$ এর জন্য মডুলার ইনভার্স $2$। এইটা কি যেকোনো সংখ্যার জন্য পাওয়া যাবে? আমরা তাহলে আরেকটা উদাহরণ নিয়ে চিন্তা করি। $b = 3$ এবং $M = 6$ এইটার জন্য কি হবে?
হিন্টঃ সমীকরণ ২ এ $x = 1, 2, 3, \dots$ বসিয়ে দেখেন যে মডুলার ভ্যালু কত আসে? এইখানে একটু লক্ষ করলেই বুঝতে পারবেন যে মডুলার ভ্যালু কিছু সংখ্যা পর পর পুনরাবৃত্তি হয়।
আর একটু বিশ্লেষণ করলে আমরা সিদ্ধান্তে আসতে পারি যে $b = 3$ এবং $M = 6$ এর জন্য মডুলার ইনভার্স পাওয়া সম্ভব নয়। আসলে $b$ এবং $M$ সহমৌলিক না হলে তাদের মডুলার ইনভার্স থাকে না। তাদেরকে এইভাবে ভাগ করা যাবে না। এজন্য সাধারণত যেসব প্রবলেমে মডুলার ইনভার্স ব্যবহার করতে হয় সেখানে $M$ বেশ বড় একটা মৌলিক সংখ্যা দেয়া থাকে।
মডুলার ইনভার্স কিভাবে বের করব?
মডুলার ইনভার্স বের করার বেশ কয়েকটা পদ্ধতি আছে। এইগুলা নিয়ে ইতিমধ্যে বেশ কিছু আর্টিকেল আছে। তাই আমি এইটা নিয়ে আর লিখছি না। আমি এইগুলার লিঙ্ক দিয়ে দিচ্ছি।
প্রাকটিস প্রবলেম
আশা করি, এই লিখাটা পরে আপনাদের মডুলার ইনভার্স সম্পর্কে আগের থেকে ভাল ধারনা হয়েছে। আমি চাই আমরা কোন কিছু শিখতে গেলে যাতে সেইটা না বুঝে একটা ব্লাক বক্স এর মত করে ব্যবহার না করি। এজন্যই আমার এই লিখাটা। আপনারা যদি এইখানে থেকে কিছুটা হলেও উপকৃত হয়ে থাকেন সেটাই আমার সার্থকতা।