মডুলাসের মডিউলেশন

(লেখাটি ইতোপূর্বে মুক্তমনায় প্রকাশিত, বিজ্ঞানযাত্রার জন্য ঈষৎ সম্পাদিত)

-ভাই ৩^৫০০ রে ১১ দিয়া ভাগ করলে ভাগশেষ কত হয় কইতে পারবেন?

-ধুরো মিয়া, ফাইজলামি করেন নাকি! এত বড় ভাগ! কেম্নে কী! আপ্নে কইরা দেখান দেখি…

-জে ভাই আমি করতে পারুম ঠিকি, তয় সোজা আঙুলে ঘি উঠবো না, আঙুলটা একটু বাঁকান লাগবো, সেই বাঁকা আঙুলটার নাম-মডুলার এরিথমেটিক।

হ্যাঁ, মডুলার এরিথমেটিক। সংখ্যাতত্ত্ব সম্পর্কে যারা একটুআধটু খোঁজখবর তাদের অবশ্যই এই শব্দদ্বয় শোনার কথা। কারণ, সংখ্যাতত্ত্বের একটি বিশাল অংশ জুড়ে রয়েছে এই মডুলার এরিথমেটিক। মডুলার এরিথমেটিকের মতো এমন জটিল একটা টার্ম শুনে অনেকে হয়তো আগ্রহ হারিয়ে ফেলতে পারেন। কিন্তু মজার ব্যাপার হচ্ছে, জেনে হোক আর না জেনে হোক আমরা কিন্তু প্রাত্যহিক জীবনে এই ব্যাপারটি প্রতিনিয়ত ব্যবহার করে থাকি। এরকম অনেক উদাহরণ দেওয়া যায়। তবে নিঃসন্দেহে, সবচেয়ে সুন্দর উদাহরণ হচ্ছে ঘড়ি। যেমনঃ এখন যে আমি এই প্রবন্ধটি লিখছি, এখন সময় হচ্ছে ১:০৫ মিনিট। আমরা মডুলাস ব্যবহার করছি বলেই এভাবে করে বলতে পারছি। মডুলাস ব্যবহার না করলে আমাদের হয়তো বলতে হতো এখন বাজে ৭২০০৭২০০০০০০০০০০ মিনিট (বিগ ব্যাং সময়সীমা অনুসারে)। চিন্তা করুন কী বিশাল ব্যাপার! এক্ষেত্রে আমরা প্রতিবার mod 12 নিচ্ছি বলে সময়টা কত ছোট হয়ে যাচ্ছে। যারা mod 12 নেওয়ার অর্থ না বুঝে আমাকে গালিগালাজ করছেন, তাদের উদ্দেশ্যে বলি, খেয়াল করুন, আমরা সময়ের ক্ষেত্রে প্রতিবার ১২ এর পরে আবার ১ এ চলে আসছি, অর্থাৎ, প্রথম থেকে শুরু করছি। ব্যাপারটা অনেকটা ১২ দিয়ে পুরো সময়কে ভাগ করে ভাগশেষ নেওয়ার মত। একটু পরেই ব্যাপারটিকে পরিষ্কার করে বোঝাচ্ছি।

মডুলার এরিথমেটিকের ইতিহাস খুব নতুন না হলেও এই বিষয়টির পদ্ধতিগত গবেষণা শুরু হয় অষ্টাদশ শতকে এক মহান গণিতবিদের হাত ধরে। গণিতের ইতিহাসে তিনি ‘গণিতের রাজপুত্র’ নামে খ্যাত। আপনারা অনেকেই হয়ত ধরে ফেলেছেন উনি কে; হ্যাঁ তিনি হচ্ছেন মহান গণিতবিদ ‘কার্ল ফ্রেডরিখ গাউস’। গাউসের জন্ম হয় ১৭৭৭ সালে খুবই গরিব একটি পরিবারে। তাঁর মা ছিলেন গৃহ পরিচারিকা আর বাবা ছিলেন দিনমজুর। গাউসের গণিতপ্রতিভার বিস্ফোরণ ঘটে একেবারে ছোটবেলাতেই। তাঁর গণিতপ্রতিভা সম্পর্কে কিছু সুন্দর গল্প প্রচলিত আছে। গণিতের বিভিন্ন শাখা তাঁর মেধার স্পর্শে সমৃদ্ধ। সংখ্যাতত্ত্ব, বীজগণিত, জটিল সংখ্যা, ধারা, জ্যামিতি ইত্যাদি নানা শাখায় তিনি অবদান রেখেছেন। এছাড়াও পদার্থবিজ্ঞান, জ্যোতির্বিজ্ঞানও তাঁর মেধার আশীর্বাদ থেকে বঞ্চিত হয়নি। বিদ্যুৎবিজ্ঞানে তিনি একটি অসাধারণ সূত্র দিয়েছেন যা এখন আমরা দ্বাদশশ্রেণীতে পদার্থবিজ্ঞানে পড়ে থাকি। এছাড়াও তিনি তাঁর উদ্ভাবিত ‘লিস্ট স্কয়ার’ পদ্ধতি ব্যবহার করে জ্যোতির্বিদদের উদ্ভাবিত একটি হারানো গ্রহকণা খুঁজে দিয়েছিলেন। আইনস্টাইন জেনারেল রিলেটিভিটি উদ্ভাবন করতে গিয়ে যে বক্রতল জ্যামিতির সাহায্য নিয়েছিলেন, তাঁর ভিত্তি কিন্তু গাউসই গড়ে দিয়েছিলেন।

যাই হোক, গাউস ১৮০১ সালে ‘Disquisitiones Arithmeticae’ নামক একটি বই প্রকাশ করেছিলেন। ওই বইটিকে আধুনিক সংখ্যাতত্ত্বের বাইবেল বললে আমার মনে হয় মোটেই বাড়িয়ে বলা হবে না। এই বইটিতেই গাউস সর্বপ্রথম মডুলার এরিথমেটিকের সংঘবদ্ধ রূপ বর্ণনা করেন। বিভাজ্যতা সম্পর্কে পিঁয়ে দ্য ফার্মা (১৬০১-১৬৬৫), লিওনারদ অয়লার (১৭০৭-১৭৮৩)-এর যে উপপাদ্যগুলো ছিল সেগুলোকে তিনি মডুলার এরিথমেটিকের রূপ দেন। তিনি বিভাজ্যতার জন্য নতুন কিছু চিহ্ন প্রবর্তন করেছিলেন। যেমনঃ mod, congruence বা অনুসম চিহ্ন। এছাড়াও ঐ বইটিতে গাউস তাঁর নিজের উদ্ভাবিত ‘Quadratic Reciprocity’ বা দ্বিঘাত বিনিময় সূত্রটি প্রকাশ করেছিলেন। এই অসাধারণ সূত্রের সাহায্যে দ্বিঘাত সমীকরণের পূর্ণসাংখ্যিক সমাধান বের বের করা যায়। কম্পিউটার বিজ্ঞানে এই সূত্রটির ভুমিকা ব্যাপক।

অনেক তো ভ্যাদর ভ্যাদর করলাম, এইবার কাজের কথায় আসি। মডুলাসের কিছু মৌলিক ধর্ম বর্ণনা করা যাকঃ
(মডুলাসের ধর্ম বর্ণনার সময় অনুসম চিহ্নকে (~) দিয়ে দেখিয়েছি, কিন্তু অনুসম চিহ্ন ঠিক এরকম নয়, অনুসম চিহ্ন উপরে-নিচে ৩টি সমান্তরাল রেখা দ্বারা গঠিত। কিন্তু ঐ চিহ্নটি ব্যবহার সম্ভব নয় বলে (~) চিহ্ন ব্যাবহার করেছি। অনেকে অবশ্য অনুসম চিহ্নের পরিবর্তে (=) চিহ্ন ব্যবহার যৌক্তিক মনে করেন। )

গাউস সাহেব

একটি সংখ্যা a ও আরেকটি সংখ্যা b কে m(এক্ষেত্রে a, b, m তিনটিই কিন্তু পূর্ণসংখ্যা) দিয়ে ভাগ করলে যদি উভয়ক্ষেত্রে একই ভাগশেষ থাকে তবে একে লেখা হয় এইভাবে,
a ~(অনুসম চিহ্ন)b(mod m)
এর মানে হচ্ছে m দিয়ে ভাগ করার ক্ষেত্রে a এবং b অনুসম বা সমতুল্য। ব্যপারটি আরও পরিষ্কার করা যাক। যেমন আমি দুটি সংখ্যা নিলাম 31 ও 16.এই সংখ্যাদুটিকে যদি 5 দিয়ে ভাগ করা হয় তবে উভয়ক্ষেত্রে ভাগশেষ থাকে 1। এই ভাগশেষের গুরুত্ব মডুলাসের জগতে সবচেয়ে বেশী। 31 ও 16 উভয়কে 5 দিয়ে ভাগ করলে ভাগশেষ থাকে 1। অর্থাৎ 5 দিয়ে ভাগ করার ক্ষেত্রে 31 ও 16 সমতুল্য বা অনুসম;যেহেতু একই ভাগশেষ থাকছে। অর্থাৎ, মডুলাসের জগতে ভাগশেষ সমান হওয়াটাই গুরুত্বপূর্ণ, ভাগফল নয়। আরেকটি উদাহরণ নেওয়া যাক, 10034 ও 44 সংখ্যাদুটির পার্থক্য যত বেশি হোক না কেন, 6 দিয়ে ভাগ করলে উভয় ক্ষেত্রে ভাগশেষ থাকে 2। তাই mod 6 এর জগতে সংখ্যা দুইটি congruent বা অনুসম। এইবার খেয়াল করুন, 10034 ও 44 উভয় সংখ্যা থেকে 2 বিয়োগ করলে, সংখ্যাদুটিকে 6 দ্বারা নিঃশেষে ভাগ করা যায়। তাই 10034 থেকে 44 বিয়োগ করলেও বিয়োগফলকে 6 দ্বারা নিঃশেষে ভাগ করা যায়। তাহলে, পুরো ব্যাপারটিকে সাধারণভাবে এইভাবে বলা যায়, a ও b দুটি সংখ্যাকে m দিয়ে ভাগ করা হলে যদি উভয়ক্ষেত্রে একই ভাগশেষ থাকে, তবে (a-b), m দ্বারা নিঃশেষে বিভাজ্য হবে।

উপরোক্ত বক্তব্যকে খুব সহজ গণিতের সাহায্যে প্রমাণ করা যায়। যেমনঃ ধরা যাক, দুটি সংখ্যা a=xm+p এবং b=ym+p । অর্থাৎ, উভয়ক্ষেত্রে m দ্বারা ভাগ করলে ভাগশেষ থাকে p । তাহলে, a-b = xm+p-ym-p = xm-ym = m(x-y);যা কিনা m দ্বারা নিঃশেষে বিভাজ্য। এই ফলাফলটিকে আমরা মডুলাসের সাহায্যে এইভাবে লিখতে পারিঃ

১। a ~ b(mod m) হলে a-b ~0(mod m) ।
ভালকরে লক্ষ্য করুন, মডুলাসের ধর্মের সাথে বীজগাণিতিক সমীকরণের ধর্মের একটি মিল পাওয়া যাচ্ছে। যেমনঃ বীজগাণিতিক সমীকরণে a=b হলে, a-b=0 হয়;মডুলাসের ক্ষেত্রেও এই ধর্ম প্রযোজ্য। আমরা সামনে দেখব, মডুলাসের অনেক ধর্মেরই সমীকরণের ধর্মের সাথে সাদৃশ্য রয়েছে। (এ কারণেই অনেকে অনুসম চিহ্নের বদলে (=) চিহ্নের ব্যবহার যুক্তিযুক্ত মনে করেন)। তাহলে, এই ধর্মটির সারমর্ম টানি এইভাবেঃ
a ও b দুটি সংখ্যাকে m দ্বারা ভাগ করলে যদি উভয় ক্ষেত্রে একই ভাগশেষ থাকে, তবে a কে m দ্বারা ভাগ করলে আমরা b কে ভাগশেষ বিবেচনা করতে পারি। এবার আরও কিছু বৈশিষ্ট্য দেখা যাকঃ

২। a, b, ও m পূর্ণসংখ্যা হলে, যদি a ~b(mod m) হয়, তবে b ~a(mod m)
উদাহরনের সাহায্যে বিষয়টিকে পরিষ্কার করা যাক। 25~20(mod 5) হলে 25-20~0(mod 5) {এর মানে নিশ্চয়ই বুঝতে পারছেন, 25 ও 20 এর বিয়োগফল 5 দ্বারা নিঃশেষে বিভাজ্য। } সেক্ষেত্রে, 20~25(mod 5)

৩। যদি a ~b(mod m) ও b ~c(mod m) হয়, তবে a ~c(mod m).
প্রমাণঃ
এই প্রমাণটি করার আগে পাঠককে বিভাজ্যতা চিহ্নের সাথে পরিচয় করিয়ে দেওয়া প্রয়োজন। কোনো সংখ্যা a, পূর্ণসংখ্যা b কে নিঃশেষে বিভাজিত করলে, এটিকে এভাবে লেখা যায়, a|b.অর্থাৎ, (|) চিহ্নটি বিভাজ্যতা চিহ্ন। এটি b ~0(mod a) এর আরেক রূপ।
তাহলে, a ~b(mod m) মানে হচ্ছে, m|(a-b);
b ~c(mod m) মানে m|(b-c).
এখন (a-b) ও (b-c) এর উভয়টিই যদি m দ্বারা নিঃশেষে বিভাজ্য হয়, তবে তাদের যোগফলও m দ্বারা নিঃশেষে বিভাজ্য হবে।
সুতরাং, m|(a-b+b-c), কাজেই, m|(a-c).
এটিকেই আমরা লিখতে পারি a ~c(mod m).
৪। যদি a ~b(mod m) ও c ~d(mod m)হলে a+c~b+d(mod m) এবং a-c~b-d(mod m)
প্রমাণঃ
a~b(mod m) হলে a-b ~0(mod m),
আবার, c~d(mod m) হলে c-d ~0(mod m).
সুতরাং, a-b~c-d(mod m)
বা a-c~b-d(mod m){১নং বৈশিষ্ট্য অনুসারে}
একইভাবে a+c~b+d(mod m) সহজেই প্রমাণ করা যায়। আশা করি, সেই দায়িত্বটি পাঠক নিয়ে আমাকে উদ্ধার করবেন।
৫। যদি a~b(mod m) হয়, তাহলে, a~b+mk(mod m) এবং a~b-mk(mod m).
প্রমাণঃ
a~b(mod m) হলে a-b ~0(mod m);
আবার, mk~0(mod m) এবং -mk~0(mod m){আশা করি এমনিতেই বুঝতে পারবেন}
সুতরাং, a-b ~mk(mod m) এবং a-b~ -mk(mod m)
কাজেই, a~b+mk(mod m) এবং a~b-mk(mod m)
৬। a~b(mod m) হলে, যে কোনও পূর্ণসংখ্যা c এর জন্য ac~bc(mod m)
প্রমানঃ
a~b(mod m) হলে m|(a-b);
এখন, m|(a-b) হলে, m|c(a-b);
তাহলে, m|ca-cb
কাজেই, ca~cb(mod m).
৭। a~b(mod m) হলে a^n~b^n(mod m), যেখানে n পূর্ণ সংখ্যা;
এই ধর্মটি প্রমাণ করার জন্য খোয়ারিজমি সাহেবের আল জাবরের দ্বারস্থ হতে হবে। কিন্তু এক্ষেত্রে গণিত জটিল পর্যায়ে চলে যাবে। আমি এই লেখায় কোনোরূপ গাণিতিক বিমূর্ততায় যেতে চাই না। বরং এই ধর্মটির তাৎপর্য উদাহরণের মাধ্যমে বোঝানো যাক। দেখুন, 14~2(mod 6).এবার n=2 হলে, এই ধর্মানুসারে 14^2~2^2(mod 6) হওয়ার কথা। এবার দেখুন 14^2-2^2=196-4=192, যা কিনা 6 দ্বারা নিঃশেষে বিভাজ্য। এভাবে n=2 এর পরিবর্তে যে কোনও সংখ্যা নিয়ে পরীক্ষা করে দেখতে পারেন। আশা করি এই ধর্মটির সত্যতা বুঝতে পারবেন। ব্যতিক্রম ফলাফল পাইলে, গাউস সাহেবকে স্মরণ করিবেন, আমার বিশ্বাস উনি আপনাদিগকে এই বিপদ হইতে উদ্ধার করিবেন!

এতক্ষণ মডুলাসের অনেক ধর্মই দেখলাম। মডুলাসের যোগ, বিয়োগ, গুণ এমনকি পাওয়ারের ধর্ম দেখতে পেলাম। কিন্তু মডুলাসের ভাগ সম্পর্কে কিন্তু টুঁ শব্দটিও করিনি। এটি অনেকটা ইচ্ছে করেই করেছি। মডুলাসের ভাগের নিয়মটি কিছুটা ব্যতিক্রম। মডুলাসের ভাগ সাবধানে করতে হয়। তা না হলে মহাভারত অশুদ্ধ হওয়াটাও অসম্ভব কিছু নয়। a~b(mod m) হলে যেমন আমরা উভয়পাশে c গুণ করে ac~bc(mod m) লিখতে পারছি, ac~bc(mod m) হলে কিন্তু উভয়পাশ থেকে, c বাদ দিয়ে লিখতে পারবেন না, a~b(mod m). এক্ষেত্রে সাবধানতা অবলম্বন করতে হবে। অর্থাৎ, উপপাদ্যটি যদি এবং কেবল যদি টাইপের না। (যদি এবং কেবল যদি টাইপের উপপাদ্য মানে হচ্ছে, উপপাদ্যটির বিপরীত উক্তিটিও সত্য। মজার ব্যাপার হচ্ছে, আমরা অনেকেই গণিতের বিভিন্ন ক্ষেত্রে এই বাক্যাংশটি পড়ি, কিন্তু এর সত্যিকার অর্থটি বুঝি না)। কি;বিশ্বাস হল না তো। ঠিক আছে;এবার তাহলে উদাহরণ দিয়ে দেখাই। যেমনঃ 48~12(mod 6) বা 4*12~1*12(mod 6).এবার তাহলে দুইপাশ থেকে 12 ‘আলগোস্তে’ ভ্যানিশ করে দেই। তাহলে কি লেখা যায়! 4~1(mod 6). অ্যাঁ! ঘটলো তো কেলেংকারি; আপনাদের বিশ্বাস করাতে গিয়েই তো এসব হলো। এতো করে বললাম, বিশ্বাস করলেন না তো। এখন আমার কত বড় একটা মিথ্যা কথা লিখতে হলো!

যাই হোক, পাপ যখন করেই ফেলেছি, এখন আর কেঁদেকেটে কি হবে, তার চেয়ে বরং আপনাদের ব্যাপারটা বোঝানো যাক। তবে টেনশন হচ্ছে, গাউস মশাই আবার কবর থেকে উঠে এসে আমার পাছায় আবার লাথি না কষিয়ে দেন!

৮। ca~cb(mod m) হলে a~b(mod m) হবে শুধুমাত্র যদি c ও m সহমৌলিক সংখ্যা হয়। অস্থির হবেন না, সহমৌলিক সংখ্যা কি তা বোঝানোর চেষ্টা করছি। যারা জানেন তাঁরা দূরে গিয়ে ম…থুক্কু …এই প্যারা বাদ দিয়ে সামনে এগিয়ে যান। দুটি সংখ্যা a ও b এর মধ্যে যদি 1 ব্যাতিত আর কোনও সাধারণ গুণনীয়ক না থাকে তবে সংখ্যা দুটিকে বলা হবে পরস্পর সহমৌলিক। যেহেতু এদের মধ্যে 1 ব্যতীত অন্য কোনও সাধারণ গুণনীয়ক নেই, তাই এদের গ.সা.গু. (গরিষ্ঠ সাধারণ গুণনীয়ক) বা GCF (Greatest Common Factor) অবশ্যই 1 । দুটি সংখ্যা a, b হলে তাদের গ.সা.গু. কে (a, b) দ্বারা চিহ্নিত করা হয়। সহমৌলিক সংখ্যার ক্ষেত্রে (a, b)=1. আমাদের এই নিয়মটির ক্ষেত্রে (c, m)=1. আমি নিশ্চিত, ভাগের নিয়মটি সত্য হতে গেলে (c, m)=1 হতে হবে কেন সেটি অনেকেই ধরে ফেলেছেন; অনেকেই হয়তো বের করার চেষ্টা করতে করতে মাথার চুল ছিড়ে ফেলছেন। যাই হোক, চুল ছিঁড়াছিঁড়ির দরকার নাই। আমি ব্যাখ্যা করছি।

দেখুন, ca~cb(mod m) কে লেখা যায়, m|(ca-cb) বা m|c(a-b). এখন m ও c এর মধ্যে যদি কোনো সাধারণ উৎপাদক থাকে, ধরি সেটি d. তাহলে, (m, c)=d.সেক্ষেত্রে m|c(a-b) এর মধ্যে m ও c এর থেকে d কাটাকাটি হয়ে যাবে। তাহলে, হরে আর যেটুকু বাকি থাকল, অর্থাৎ, m/d কে দিয়ে (a-b) কে নিঃশেষে ভাগ করা গেলেই কেল্লা ফতে। অর্থাৎ, পুরো m এর (a-b) কে ভাগ করার দরকার পড়বে না। (a-b) কে পুরো m দ্বারা ভাগ তখনই যেতে হতো, যখন c এর সাথে m এর কোনো অংশ কাটাকাটি যাবে না। অর্থাৎ, (c, m)=1 হবে। আশা করি ভাল করে বুঝতে পারেন নি! একটু পরিষ্কার মাথায় চিন্তা করুন, আশা করি “clear” হয়ে যাবে। তাহলে মডুলাসের ভাগের ক্ষেত্রে ইচ্ছেমত কাটাকাটি করা যাবে না। আগে দেখে নিতে হবে (c, m)=1 কিনা; খিয়াল কইরা কিন্তুক!

এতক্ষণ তো অনেক তত্ত্ব আওড়ানো হল। এবার তাহলে মডুলাসের কেরামতি প্রত্যক্ষ করা। শুরুতে উল্লেখিত সমস্যাটি দিয়ে বিসমিল্লা করি।
উদাহরণ ১:
3^500 কে 11 দিয়ে ভাগ করলে ভাগশেষ কত থাকবে?
এটিকে মডুলাসের ভাষায় এভাবে লেখা যায়ঃ 3^500 ~?(mod 11).
খেয়াল করুন, 242~0(mod 11)
তাহলে, 243-1~0(mod 11)
বা, 243 ~ 1(mod 11){১নং ধর্মানুসারে}
বা, 3^5~1(mod 11)
বা, (3^5)^100 ~1^100(mod 11){৭ নং ধর্মানুসারে উভয়পক্ষে 100 পাওয়ার নিয়ে। }
বা, 3^500 ~ 1 (mod 11);
অর্থাৎ, ভাগশেষ 1. কি অসাধারণ ব্যাপার তাই না! একটা সংখ্যা এতো বড় যে আমি এর মান জানি না। অথচ, ঐ সংখ্যাটিকে আরেকটি সংখ্যা দিয়ে ভাগ দিলে ভাগশেষ কত হয় তা আমি বলে দিতে পারছি। এটাই আসলে মডুলার এরিথমেটিকের আসল মজা।

(চলবে…)

সহায়ক বই ও তথ্যসূত্রঃ
১। The Theory of Numbers-John Coury & Andrew Adler
২। 104 Number Theory Problems-Titu Andreescu, Dorin Andrica, Zuming Feng
৩। Excursion in Number Theory-Stanly Ojilvy & J Anderson
৪। BDMO প্রস্তুতি
৫। সংখ্যাতত্ত্বে আনন্দভ্রমণ-রক্তিম বড়ুয়া
৬। https://en.wikipedia.org/wiki/Modular_arithmetic.

Comments