সংখ্যাতত্ত্বের আরেকটি লিখাতে আপনাদের স্বাগতম। আগের লিখায় দেখেছিলাম আমরা কিভাবে ইউক্লিডিয়ান অ্যালগরিদম ব্যবহার করে এর সমাধান করতে পারি। এই লিখায় আমরা এর সমাধান করা শিখবো যেখানে বা , দ্বারা বিভাজ্য এবং অথবা এর যেকোনো একটি অশূন্য হবে। এই সমীকরণের নাম লিনিয়ার ডায়োফ্যান্টাইন সমীকরণ ।
লিনিয়ার ডায়োফ্যান্টাইন সমীকরণ: সমস্যার বিবরণী
আমাদের একটি সমীকরণ দেয়া আছে, যেখানে প্রদত্ত পূর্ণসংখ্যা, , দ্বারা বিভাজ্য। আমাদেরকে এর এমন দুইটি মান বের করতে হবে যেন এই সমীকরণটি সত্য হয়।
এই লিখাটি অনেক বেশি Extended Euclidean Algorithm এর উপর নির্ভরশীল। সুতরাং যাদের বর্ধিত ইউক্লিডিয়ান অ্যালগরিদম বা Extended Euclidean Algorithm নিয়ে জানা নেই তারা লিখাটি পরে আসেন।
Linear Diophantine Equation এর একটি সমাধান বের করা।
যদি পূর্ব থেকে এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগরিদম নিয়ে জানা থাকে তবে এই সমস্যার সমাধান করা সহজ হবে আশা করি। এই সমীকরণে কে দ্বারা নিঃশেষে ভাগ করা যায়। এটা সমাধানের আগে আমরা এর সমাধান বের করবো বর্ধিত ইউক্লিডিয়ান অ্যালগরিদম ব্যবহার করে।
আমরা সেখান থেকে জেনেছিলাম এর জন্য আমরা সবসময় এর একটি সমাধান পাবো। আগের লিখা থেকে extended_gcd() ফাংশনটি কপি করছি।
| 1 2 3 4 5 6 7 8 9 10 11 12 | int extended_euclid(int a,int b,int &x,int &y){ if(b==0){ x=1; y=0; return a; } int x1,y1; int gcd=extended_euclid(b,a%b,x1,y1); x=y1; y=x1-floor(a/b)*y1; return gcd; } |
উদাহরণস্বরূপ একটি সমীকরণ বিবেচনা করি, , এখানে । আমরা main() ফাংশনের ভেতর থেকে extended_euclid() কে কল করবো।
| 1 2 3 4 5 6 | int main(){ int a=8,b=44,x_g,y_g;//8x+44y int gcd=extended_euclid(a,b,x_g,y_g); cout<<gcd<<" "<<x_g<<" "<<y_g<<endl; return 0; } |
এখানে রেফেরেন্সের মাধ্যমে আপডেট হয়ে গিয়েছে। এবং ফাংশনটি রিটার্ন করেছে। আমরা এই কলের মাধ্যমে এর মান পেয়েছি। এখানে আমরা পাই
এখন লিনিয়ার ডায়োফ্যান্টাইন সমীকরণের শর্ত মোতাবেক অবশ্যই দ্বারা বিভাজ্য হতে হবে। এখানে যা 4 দ্বারা বিভাজ্য। ।
বর্ধিত ইউক্লিডিয়ান অ্যালগরিদম থেকে পাই,
[উভয় পক্ষে বা 13 গুন করি]
এর সাথে তুলনা করে পাই, এবং
আমরা যদি সাধারনরূপে লিখি তবে পাই,
এর সাথে তুলনা করি, এবং
উভয় পক্ষে গুন করে পাই,
বা,
বা,
সুতরাং আমরা সমীকরণের একটি সমাধান পেলাম।
সাধারণরূপে সমাধান বের করা
উপরের ধাপে আমরা এর একটি সমাধান সমাধান বের করেছি। কিন্তু লিনিয়ার ডায়োফ্যান্টাইন সমীকরণ এর অসীম সংখ্যক সমাধান পাওয়া যায়। কিভাবে? চলুন নিচের অংশটুকু শেষ করি।
আমরা x এর মান এর সাথে যোগ করেছি এবং y এর মানের থেকে বিয়োগ করেছি। এতে করে এই সমীকরনের সাম্যতা অক্ষুন্ন রয়েছে। প্রমান নিচে দেয়া হলো।
সুতরাং দেখতে পাছি এর সাথে যোগ এবং থেকে বিয়োগ করলে ও এর নতুন যা মান পাবো পাবো তা আমাদের সমীকরণকে সিদ্ধ করে।
একই ভাবে খুব সহজেই দেখানো যায় যে,
এখানে k হলো যেকোনো পূর্ণসংখ্যা। সুতরাং দেখতে পাচ্ছি লিনিয়ার ডায়োফ্যান্টাইন সমীকরণের অসীম সংখ্যক সমাধান রয়েছে, যা k এর মানের উপর নির্ভর করে।
সুতরাং আমরা সাধারণ রুপে লিখতে পারি,
এখানে k যেকোনো পূর্ণসংখ্যা।
C++ এর মাধ্যমে লিনিয়ার ডায়োফ্যান্টাইন সমীকরণ এর ইমপ্লিমেন্টেশন
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include<bits/stdc++.h> using namespace std; int extended_euclid(int a,int b,int &x,int &y){ if(b==0){ x=1; y=0; return a; } int x1,y1; int gcd=extended_euclid(b,a%b,x1,y1); x=y1; y=x1-floor(a/b)*y1; return gcd; } int main() { //Our equation 8x+44y=52 int a=8,b=44,x_g,y_g,c=52; int gcd=extended_euclid(a,b,x_g,y_g); //8x+44y=gcd(a,b) এর জন্য সমাধান বের করি। if(c%gcd!=0){// যদি c, gcd দ্বারা নিঃশেষে বিভাজ্য না হয় তবে x,y এর কোন পূর্ণ মানের জন্য সমীকরনের সমাধান নেই। cout<<"The equation has no solution!\n"; return 0; } int k=3; // k এর মান ইচ্ছেমত ধরে নিন। int x=x_g*c/gcd+k*b/gcd; int y=y_g*c/gcd-k*a/gcd; cout<<"Solution for 8x+44y=52 is: x="<<x<<"; y="<<y<<endl; return 0; } |
এখনে আমরা সবার প্রথমে Extended Euclidean Algorithm অনুসারে সমাধানের জন্য extended_euclid() ফাংশন তৈরি করে নিয়েছি। এর মাধ্যমে আমরা gcd(a,b) এর পাশাপাশি এর মান পাবো। তারপরে আমরা পরিক্ষা করে দেখেছি কে দ্বারা ভাগ করা যায় কি না। যদি ভাগ করা না যায় তবে আমরা বলতে পারি এই সমিকরনের সমাধান সম্ভব নয় যেখানে পূর্ণ সংখ্যা হবে।
এর পর আমরা k এর একটি ইচ্ছেমত মান ধরে নিয়েছি। k এর মান অনুসারে আমরা এই সমিকরনের বিভিন্ন সমাধান পেতে পারি। তারপর আমরা সুত্র প্রয়োগ করে এর মান বের করেছি এবং আউটপুট দিয়েছি।
এই লিখাটি অসম্পূর্ণ। লিখাটি আরও আপডেট করা হবে। আপাতত এখানে একটি সমাধান বের করা দেখানো হলেও আমরা এর এমন মান বের করতে পারবো যেন এর মান সর্বনিম্ন হয়। একই সাথে আমরা বের করতে পারবো একটি নির্দিষ্ট সীমার মধ্যে কতগুলো সমাধান রয়েছে।
সুত্র: https://cp-algorithms.com/algebra/linear-diophantine-equation.html
