Simultaneous Linear Congruence and Chinese Remainder Theorem (CRT)

একবছর হল এই জিনিসটা শেখার চেস্টায় ছিলাম। যতবার ক্লাসের পরীক্ষায় এই অঙ্কগুলো করেছি কোনদিনও শুন্যের উপরে নাম্বার পাই নি। যেকোনো সময়ই করি না কেন, কিছু না কিছু ভুল হতো। কিন্তু ভুল হলে তো মুশকিল, আমি তো সংখ্যা নিয়ে খেলতে পছন্দ করি, এই নাম্বার থিওরি নিয়েই কাজ করার ইচ্ছা, এতো সোজা জিনিস ভুল হলে তো আমি আর কোনদিনও এই বিষয় নিয়ে কাজই করতে পারব না, কেউ কাজই দেবে না এই বিষয়ের উপরে।

মনে হয় মাথায় ব্যারাম দেখা দিয়েছে, পাগলের ডাক্তার ডাকতে হবে। আজকে প্রথমবারের মতন এটা খুবই ভালমতন বুঝেছি (মনে হচ্ছে), বুঝলাম আমি দুনিয়ার সবচেয়ে বড় গাধা। আজকে এই বিষয়ের উপরে অনেকগুলো অঙ্কও করলাম, একটাও ভুল হয় নি (আপাতত)। তাই মনে হল আমি নিজে খুশি হব কেন, এখানেও আমার গাধা হওয়ার Announcement টা জানিয়ে দেই। আমাকে তো আর ফেসবুকে কেউ পাবে না। রেজা ভাই আগের লেখাটায় বলেছিল “সাধনা চালিয়ে যাও, এরকম আরও লেখা চাই”, সেই মাপের লেখা হবে কি না জানি না, তবে ভাইয়ের মান সম্মান রক্ষার চেস্টা করব।

প্রথমে দেখব খুবই সাধারন একটা সমস্যা, তারপর আস্তে আস্তে কঠিনের দিকে যাব।

Q. Find the smallest positive number which, when divided by $5$ and $7$, leaves a remainder of $1$ and $4$.

সল্যুশনঃ আমাদের এই সমীকরণগুলো সমাধান করতে হবে…

$x\equiv 1\mod 5$

$x\equiv 4\mod 7$

প্রথম সমীকরণ থেকে পাই…

$x=5k+1$

এটা না বোঝার কিছু নেই, খুবই সাধারণ Clock Arithmetic। একটাই মজা, এই নিয়মের অঙ্কগুলোতে ঘড়িটা প্রয়োজনে বিপরীত দিকেও ঘোরানো যায়। এখন এই মান টা পরের সমীকরণে বসাবো।

$5k+1\equiv 4\mod 7$

$\implies 5k\equiv 3\mod 7$

$\implies -2k\equiv -4\mod 7$

$\implies k\equiv 2\mod 7$

$\implies k=7l+2$

অঙ্ক করা শেষ, এখন সমাধান কিভাবে করে? এগুলো কিন্তু স্বাভাবিক সমীকরণের মতন একটা মান বসিয়ে দিলেই হয় না, এখন Back Substitution করতে হবে।

$x=5k+1=5(7l+2)+1=35l+10+1=35l+11$

$\implies x\equiv 11 \mod 35$

Putting $l=0$, we have $11$ as our smallest positive number that satisfies the conditions stated in the system of linear congruences

এখন আমি নিজেই প্রশ্ন করে বসব, শুরু তো করলাম $\mod 5$ আর $\mod 7$ দিয়ে, তাহলে এই $\mod 35$ বাবাজি কোথা থেকে উদয় হলেন? এখানেই আসবে মজার থিওরেমটা, এটাই আমাদের Chinese Remainder Theorem এবং না জানি এটাকে ক্লাসে কিভাবে শেখানো হয়েছিল যে আমি এর মাথামুণ্ড কিছুই বুঝি নি।

Chinese Remainder Theorem: Consider the system of simultaneous linear congruences:

$x\equiv a_1 \mod n_1$

$x\equiv a_2 \mod n_2$

$…………….$

$x\equiv a_k \mod n_k$

where $n_1,n_2,…..n_k$ are all positive integers greater than $1$ and the $n_i$’s are pairwise coprime. Then the solution of the system is of the form

$x\equiv m \mod N$

where $0\leq m< N$ and $N=lcm(n_1,n_2,….n_k)$

এখন দেখব আর একটা অঙ্ক।

Q. What is the least positive number which, when divided by $7, 9$ and $11$ leaves a remainder of $1,2$ and $3$ respectively

$x\equiv 1\mod 7$

$x\equiv 2\mod 9$

$x\equiv 3\mod 11$

Solution: We have $3$ linear congruences. Multiply the divisors taking $(3-1)=2$ at a time. According to the Chinese remainder theorem, we must have

$x\equiv (99a+77b+63c) \mod lcm(7,9,11)$

$\implies x\equiv 99a+77b+63c \mod 693$

এখন সমীকরণটাকে আগের মতন লিখে এই মান টা বসিয়ে কাজ করব, দেখি কত পাই।

$x\equiv 1\mod 7$

$\implies 99a+77b+63c\equiv 1 \mod 7$

$\implies 99a\equiv 1\mod 7$

$\implies a\equiv 1\mod 7$

এখান থেকে পেলাম $a=1$

এভাবে আরও দুটো মান লাগবে

$x\equiv 2\mod 9$

$\implies 77b\equiv 2\mod 9$

$\implies -4b\equiv 2\mod 9$

$\implies 2b\equiv -1\mod 9$

$\implies 2b\equiv 8\mod 9$

$\implies b\equiv 4\mod 9$

পেলাম $b=4$

আরও একটা মান দরকার

$x\equiv 3\mod 11$

$\implies 63c\equiv 3\mod 11$

$\implies -3c\equiv 3\mod 11$

$\implies c\equiv -1\mod 11$

$\implies c\equiv 10\mod 11$

এখন শুধু মানগুলো নিয়ে সংখ্যাটা তৈরি করব।

$x\equiv 99+77\times 4+63\times 10 \mod 693$

$\implies x\equiv 1037 \mod 693$

$\implies x\equiv 344 \mod 693$

$\implies x=693k+344$

Putting $k=0$, the least positive number is $344$

এখানে প্রশ্ন উঠবে আমি কেন আগের নিয়মে অঙ্কটা করলাম না, আগেরটাই তো সোজা মনে হচ্ছে। করা যায় না? করলেই করা যায়, অবশ্যই করা যায়। দেখি না একটু চেস্টা করে…

$x\equiv 1\mod 7\implies x=7k+1$

$x\equiv 2\mod 9$

$\implies 7k+1\equiv 2\mod 9$

$\implies 7k\equiv 1\mod 9$

$\implies -2k\equiv -8\mod 9$

$\implies k\equiv 4\mod 9$

$\implies k=9l+4$

$x\equiv 3\mod 11$

$\implies 9l+4\equiv 3\mod 11$

এখানেই কিন্তু ধরাটা খাব, আমার এজন্যেই অঙ্কগুলো মিলতো না, আমি কোন দুঃখে যেন $x$ এর জায়গায় $k$ এর মান টা বসাতাম, মনে করতাম এটা তো automatically একটা consistent system, মনে হয় Simultaneous Equation এর মতন সহজে মিলে যাবে।

এখন এটা ঠিকভাবে করি তো…

$x\equiv 3\mod 11$

$\implies 7k+1\equiv 3\mod 11$

$\implies 7k\equiv 2\mod 11$

$\implies 7(9l+4)\equiv 2\mod 11$

$\implies 63l+28\equiv 2\mod 11$

$\implies -3l+6\equiv 2\mod 11$

$\implies -3l\equiv -4\mod 11$

$\implies -3l\equiv (-22+18) \mod 11$

$\implies -3l\equiv 18 \mod 11$

$\implies l\equiv -6 \mod 11$

$\implies l\equiv 5 \mod 11$

$\implies l=11m+5$

So,

$x=7k+1$

$\implies x=7(9l+4)+1$

$\implies x=63l+29$

$\implies x=63(11m+5)+29$

$\implies x=693m+344$

$\implies x\equiv 344\mod 693$

বোঝাই যাচ্ছে যদি $x$ এর বদলে $k$ এর মান বসিয়ে দিতাম তাহলে আর অঙ্কটা হতো না। কলেজে গিয়ে একবছরে যা বুঝার ক্ষমতা হলো না, সেটা কেন যে আজকে ঘরে বসে ৫মিনিটের মধ্যে এমনভাবে শিখে গেলাম যে আর কোনদিনও ভুলবো না। জীবনটা আসলেই অনেক আজব এবং চমৎকার। ও ভালো কথা, আমার কথা শুনে কেউ আবার কলেজ ড্রপ আউট হয়ে ঘরে বসে পড়া শুরু করে দেবেন না, ঢাকা বিশ্ববিদ্যালয়ের মতন চমৎকার একটা শিক্ষা প্রতিষ্ঠান থেকে শিক্ষা গ্রহন করার যোগ্যতা অথবা সুযোগ সবার আসে না।

এই সহজ জিনিস টার জন্য এতো বড় লেখাটা লেখার কোন মানে হয় কি না জানি না। লিখতে ইচ্ছা করল দেখে মনের আনন্দেই লিখে দিলাম। ভালো না লাগলে বা লেখার মধ্যে কোন ভুলভাল থাকলে গালমন্দ করতে দ্বিতীয়বার চিন্তা করবেন না।

I have the heart of a warrior, I’ll not learn to lose