Linear Diophantine Equation


২ টি সমীকরন,
5x + 3y = 21
4x + 2y = 16

এখানে অজানা ভেরিয়েবল ২টি, x and y
সমীকরন সমাধান করে এই ২টি অজানা ভেরিয়েবলের মান বের করা যায়।
x = 3 and y = 2

এই ব্যাপারটি যেকোন সমীকরনের ক্ষেত্রে সত্য।
যেমন : যদি ৫ টি সমীকরন দেয়া হয় এবং ৫টি অজানা ভেরিয়েবল থাকে তবে সমীকরন সমাধান করে সেই ৫টি ভেরিয়েবলের মান বের করা সম্ভব।

সমস্যা হল, যদি ২ টি সমীকরন দেয়া থাকে এবং অজানা ভেরিয়বল ৩ টি হয়
তাহলে কিভাবে ৩টি ভেরিয়েবলের মান বের করা যাবে
একইভাবে যদি ১টি সমীকরন দেয়া থাকে এবং অজানা ভেরিয়েবল ২ টি হয়
যেমন : 2x + 5y = 13

এমনও সমীকরন হতে পারে, যার আসলে কোন সমাধান নেই।
যেমন : 4x + 10y = 13
এই সমীকরনের জন্য x and y এর কোন মান পাওয়া সম্ভব নয়।
এটা খুব সহজে বের করা যায়।

প্রথমে, 4 and 10 এর গ.সা.গু বের করতে হবে। সেই গ.সা.গু দিয়ে যদি 13 কে নিঃশেষ ভাগ করা না যায়, তাহলে সেই সমীকরনের কোন সমাধান নেই।

#include <stdio.h>

int gcd (int a, int b)
{
    if ( b == 0 ) return a;
    return gcd (b, a % b);
}

int main ()
{
    int a = 4;
    int b = 10;
    int c = 13;

    // equation : 4x + 10y = 13
    // general format : ax + by = c

    if ( c % gcd (a, b) == 0 ) printf ("Solution exist\n");
    else printf ("NO solution\n");
}

সমীকরনের কোন সমাধান না থাকলে তো কিছু করার নাই, তাই না ?
যদি সমাধান থাকে তাহলে সেটা কিভাবে বের করা যায় ?
যেকোন একটি সমীকরন নেয়া যাক, যেমন : 6x + 10y = 40

প্রথমে আমাদের 6 and 10 এর গ.সা.গু বের করে নিতে হবে।
gcd (6, 10 ) = 2
তারপর আমাদের নীচের সমীকরনটি তৈরী করতে হবে :
6x + 10y = 2
অর্থ্যাৎ, 6x + 10y = gcd (6, 10)
or, ax + by = gcd (a, b )

Number Coefficient of 10 Coefficient of 6 Result
10 1 0 (10*1) + (6*0) = 10
6 0 1 (10*0) + (6*1) = 6

Number column এ প্রথমে বড় সংখ্যাটি তারপর ছোট সংখ্যাটি বসাতে হবে।
১ম সারিতে, ১০ এর সহগ ১
এবং ৬ এর সহগ ০
অর্থ্যাৎ, মোট যোগফল = ১০

২য় সারিতে, ১০ এর সহগ ০
এবং ৬ এর সহগ ১
অর্থ্যাৎ, মোট যোগফল = ৬

এখন, আগের ২টি সারির বিয়োগফল দিয়ে ৩য় সারি পূর্ণ করতে হবে

Number Coefficient of 10 Coefficient of 6 Result
10 1 0 (10*1) + (6*0) = 10
6 0 1 (10*0) + (6*1) = 6
10 – 6 = 4 1 – 0 = 1 0 – 1 = -1 (10*1) + (6*-1) = 4

একইভাবে ৪র্থ সারি পূর্ণ করতে হবে।

Number Coefficient of 10 Coefficient of 6 Result
10 1 0 (10*1) + (6*0) = 10
6 0 1 (10*0) + (6*1) = 6
4 1 -1 (10*1) + (6*-1) = 4
6 – 4 = 2 0 – 1 = -1 1 – (-1) = 2 (10*-1) + (6*2) = 2

যখন Number column  এ gcd (6, 10) = 2 আসবে তখন থামতে হবে ।
আমাদের ৪র্থ সারিতে থামতে হবে।
আমাদের তৈরী করা সমীকরনটি ছিল, 6x + 10y = 2
এখানে, x = last coefficient of 6 = 2
and y = last coefficient of 10 = -1
অর্থ্যাৎ, (6 * 2) + (10 * -1) = 2

সমীকরনটি আমরা সমাধান করে ফেলেছি, x = 2 and y = -1
কিন্তু আমাদের মূল সমীকরনটি কি ছিল ?
6x + 10y = 40
আমরা সমাধান করলাম, 6x + 10y = 2 সমীকরনটি
বামপাশের অংশটা ঠিকই আছে কিন্তু ডানপাশের অংশটি ঠিক নেই।
6x + 10y = 40 = 2 * 20
আমরা যে সমীকরনটা সমাধান করলাম তার সাথে ২০ গুন করে দিলে মূল সমীকরটা পাওয়া যায়
তাহলে, 6x + 10y = 40 সমীকরনটির সমাধান হল, x = 2 * 20 and y = -1 * 20
so, x = 40, y = -20

এটাই কিন্তু সমীকরনটির একমাত্র সমাধান নয়।
যেমন এই সমীকরনটির অন্যান্য সমাধান : x = 45, y = -23
x = 50, y = -26
x = 55, y = -29 and many more

আমাদের সমীকরনটি ছিল,
6x + 10y = 40
এবং পুরোনো সমাধানটি ছিল Xold = 40 and Yold = -20
Xnew = Xold + (10 / 2) * K = Xold + 5K
Ynew = Yold + (6 / 2) * K = Yold + 3K

এখন K এর যেকোন মানের জন্য আমরা নতুন নতুন X and Y মান পাব।

সাধারন সূত্রটি এমন,
equation : ax + by = c
Xnew = Xold + (b / gcd (a, b)) * K
Ynew = Yold + (a / gcd (a, b)) * K

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s