Diophantine Equations (ডায়াফন্টাইন সমীকরণ):

ডায়াফন্টাইন সমীকরণ বলতে মূলত এমন সমীকরণকে বুঝানো হয় যার জন্য আমরা শুধু পূর্ণসংখ্যা সমাধানকে হিসেবের মধ্যে রাখব। এ ধরণের সমীকরণ নিয়ে প্রথম কাজ করেন তৃতীয় শতাব্দীর গ্রীক গণিতবিদ ডায়াফন্টাস। সাধারণভাবে আমরা দেখি যতগুলো অজানা রাশি ততগুলো স্বাধীন সমীকরণ থাকলে সমীকরণসমূহ সমাধান করা সম্ভব হয়। ডায়াফন্টাইন সমীকরণের ক্ষেত্রে সমীকরণের সংখ্যা প্রায় সবসময়ই হয় কম। এ কারণে ইউনিক সল্যুশনের কোনও নিশ্চয়তা নাই। অনেক ক্ষেত্রেই সমস্যাগুলো দেখতে হয় এমনঃ নিচের সমীকরণের সকল পূর্ণ সাংখ্যিক সমাধান বের কর, বা সমীকরণের সকল ধনাত্মক পূর্ণ সাংখ্যিক সমাধান বের কর। ডায়াফন্টাইন সমীকরণ অনেক রকমের হতে পারে। এবং এগুলো সমাধান করার জন্য বিভাজ্যতা, গসাগু, লসাগু, ফ্যাক্টরাইজেশন এসব বিষয়ে মোটামোটি ভাল দখন থাকতে হবে। যাই হোক, এবার আমরা দেখি বিভিন্ন ধরণের ডায়াফন্টাইন সমীকরণ।

Linear Diophantine Equations:

সবচেয়ে সরল ডায়াফন্টাইন ইকুয়েশন হল লিনিয়ার ডায়াফন্টাইন ইকুয়েশন। লিনিয়ার ইকুয়েশন বা একঘাত সমীকরণের সাথে তো বীজগণিত থেকে আমরা সবাই পরিচিত। এর বৈশিষ্ট্যগুলো কি? সকল অজানা পদ থাকবে একঘাত রাশি হিসেবে। যেমন এমন প্রবলেম তো বেশ কমন।
নিচের সমীকরণসমূহকে সমাধান করঃ

2x+3y = 8; 4x+5y = 10.

দুইটি অজানা রাশি, দুইটি সমীকরণ। এবং সহজেই সমাধান করা যাবে। এভাবে তোমরা তিনটি রাশি বিশিষ্ট তিনটি সমীকরণ সমাধান করে ফেলতে পারবে। সহজ কাজ।

এবার ধর আমি একটাই সমীকরণ দিলাম।

4x+5y = 10

এখন এই সমীকরণকে আমি বললাম সমাধান করতে। কি করা যায়? লিখা যায়ঃ

x = (10-5y)/4

আচ্ছা এখন যদি y এর মান বসাই প্রতি মানের জন্য আমি x এর বিভিন্ন মান পাব। একটা টেবিল করে ফেলি তাহলে x আর y এর মানের।

x	5/2	5/4	0	-3/4	-5/2	-15/4	-5	-25/4
y	0	1	2	3	4	5	6	7

এখানে, এই যে কয়েকটা মান বসিয়ে দেখলাম আমরা, এখানে আমরা দুইটা পূর্ণ সংখ্যা সমাধান পেয়েছি (x,y) এর জন্য। (0,2) আর (-5,6) (এদের মধ্যে সম্পর্ক কি সেটায় আমরা পরে আসব)। তো y এর ৮টা মানের জন্য আমরা ২টা সমাধান পেয়ে গেছি। তাহলে আরও সমাধান পাওয়া নিশ্চয়ই সম্ভব। আরও কত? অনেক? অসীম সংখ্যক? এই সমীকরণের ক্ষেত্রে নাহয় সমাধান পাওয়া গেল, সবসময় কি যাবে? সমীকরণটা যদি হয় 4x+6y = 13 তখন?

সমাধানযোগ্যতাঃ

         I.            4x+5y = 10

        II.            4x+6y = 13

      III.            3x+6y = 17

      IV.            14x + 21y = 143

       V.            9x + 18y = 69

উপরের সমীকরণগুলোর মধ্যে কোনগুলো সমাধানযোগ্য?

         I.            সমাধান দেখানো হয়েছে।

        II.            এটার ক্ষেত্রে একটা ব্যাপার খেয়াল কর। বাম পাশের দুইটি পদই জোড়। দুইটা জোড় সংখ্যাকে যোগ করলে কি হয়? আরেকটা জোড় সংখ্যা। কিন্তু ডানপাশে থাকা 13 তো জোড় না। তার মানে কোন x, y এর জন্যই এর কোন সমাধান নেই।

      III.            বাম পাশে কি খেয়াল করতে পার? দুইটি পদই ৩ দিয়ে বিভাজ্য। মানে যোগফলও ৩ দিয়ে বিভাজ্য হতে হবে। ডান পাশের 17 আবার তা না। তার মানে? এক্ষেত্রেও কোন সমাধান নাই।

      IV.            বাম পাশ সম্বন্ধে কি বলা যায়? ৭ দিয়ে বিভাজ্য। ডান পাশ কিন্তু ৭ দ্বারা বিভাজ্য। তাই আগেরবারের মত কোন সমস্যা নাই। সমাধান থাকতেই পারে।

       V.            বাম পাশ ৯ দ্বারা বিভাজ্য। ডান পাশ না।

তাহলে যা যা দেখলাম এখন পর্যন্ত তাকে সংক্ষেপে কিভাবে বলা যেতে পারে? Generalize করার চেষ্টা করি।

ধরি সাধারণ সমীকরণঃ

ax + by = c; a, b, c হচ্ছে ধনাত্মক বা ঋনাত্মক পূর্ণসংখ্যা।

এখন ধরা যাক gcd(a,b) = d. তাহলে x, y এর মান যাই হোক না কেন ax ও by উভয়েই d দিয়ে বিভাজ্য হবে। তার মানে তাদের যোগফলও d দিয়েই বিভাজ্য হবে। এখন c যদি d দিয়ে বিভাজ্য না হয় সেক্ষেত্রে এই সমীকরণের কোন সমাধান থাকবে না। বিপরীতভাবে এটাও বলা যায় যদি gcd(a,b) দ্বারা c নিঃশেষে বিভাজ্য হয় তাহলে সমীকরণের সমাধান থাকবেই। কেন সবসময় থাকবেই এটা তোমরা ভেবে বের কর।

সিদ্ধান্ত ১. ax + by = c সমীকরণটির পূর্ণ সাংখ্যিক সমাধান থাকবে যদি এবং কেবল যদি gcd(a,b) দ্বারা c নিঃশেষে বিভাজ্য হয়।

এখন আরেকটা জিনিস খেয়াল কর। ax+by এর মান যাই হোক না কেন তাকে gcd(a,b) = d দিয়ে বিভাজ্য হতে হবে। এখন যদি c | d হয় তাহলে d এর সর্বনিম্ন ধনাত্মক মান হবে c. তাহলে ব্যাপারটা এভাবেও বলা যায় যে ax+by আকৃতির সকল ধনাত্মক সংখ্যার মধ্যে সর্বনিম্ন হবে d.

সিদ্ধান্ত ২. ax + by এই লিনিয়ার কম্বিনেশনে x, y এর বিভিন্ন মান বসিয়ে প্রাপ্ত সকল ধনাত্মক সংখ্যার মধ্যে ক্ষুদ্রতমটি হবে x ও y এর গসাগু।

এইভাবে অনেকসময় গসাগু বের করতে হতে পারে।

সমাধান নির্ণয়ঃ

এখন আমরা বের করতে পারি যে ডায়াফন্টাইন সমীকরণের সমাধান আছে কিনা। এখন সমাধান নির্ণয় করা যাক। প্রথম উদাহরণেই ফিরে যাই। 

4x+5y = 10; x = (10-5y)/4

এবং টেবিলটা আবার তৈরি করি আরও বেশি সংখ্যা নিয়ে।

x	5/2	5/4	0	-3/4	-5/2	-15/4	-5	-25/4	-15/2	-35/4	-10	-45/4
y	0	1	2	3	4	5	6	7	8	9	10	11

আরেকটু বাড়িয়ে আরও একটা সমাধান পেয়েছি আমরা।

(x,y) = (0,2), (-5,6), (-10,10).

এগুলোর মধ্যে কিছু খেয়াল করতে পারো? X এর মান কমছে 5 এর ব্যবধানে, বা বলা যায় বাড়ছে -5 করে। একইসাথে y এর মান বাড়ছে 4 করে। মানে x এর মানে -5 করে বাড়ার জন্য y এর মান বাড়ছে 4 করে। তার মানে x, y এর প্রথম যে মানটা পেয়েছি আমরা সেখান থেকে আমরা সহজেই পরের সমাধানগুলো বের করতে পারব। x এর মান -5 করে বাড়াতে থাকব আর y এর মান 4 করে। সাধারণ একটা সমাধান লিখেই ফেলিঃ
x = 0 – 5t; y = 2 + 4t, t হবে যেকোন পূর্ণসংখ্যা। এটা যে কাজ করে সেটা তোমরা t এর বিভিন্ন মান বসিয়ে দেখা যায়। সমীকরণ থেকে বোঝানোর চেষ্টা করি।

x = (10-5y)/4

এখন y = 2 এর জন্য আমরা দেখছি x ও পূর্ণসংখ্যা হচ্ছে। তার কারণটা কি? x কে পূর্ণসঙ্খ্যা হতে হলে (10-5y) কে 4 দিয়ে বিভাজ্য হতে হবে। এবং 10-5x2 = 0, 4 দিয়ে বিভাজ্য। এখন ধরি y = 2+k. তাহলে

(10-5y)  = 10 - 5(2+k) = -5k.

বিভাজ্যতার জ্ঞান ঝালাই করে নাও। -5k, 4 দিয়ে বিভাজ্য হবে কখন? যখন k নিজেই 4 দিয়ে বিভাজ্য। তাহলে ধরে নিতেই পারি

k = 4t;  y = 2+4t;

এবার y এর মান সমীকরণে বসিয়ে x এর মান পাবঃ

x = (10- 5(2+4t))/4 = -5t

তার মানে, (x,y) = ( -5t, 2 + 4t ).

ঠিক আগে যা বলেছিলাম।এখন t এর মান কি হতে পারে? যেকোন পূর্ণসঙ্খ্যা। তার মানে t এর, তথা (x,y) এর কয়টি সমাধান থাকতে পারে? অসীম সংখ্যক। তার মানে কি? সমীকরণের একটা সমাধান কোন মতে বের করতে পারলেই সেখান থেকে আরও অসীমসংখ্যক সমাধান পাওয়া যাবে।

সিদ্ধান্ত ৩. ax + by = c সমীকরণটির একটি মাত্র পূর্ণ সাংখ্যিক সমাধান থাকলেই অসীমসংখ্যক পূর্ণ সাংখ্যিক সমাধান থাকবে।

আচ্ছা আরেকটা সমীকরণ দেখা যাক,

14x + 21y = 28.

সবকয়টি পদ gcd(7,14)=7  দিয়ে বিভাজ্য। তাহলে 7 দিয়ে সবাইকে ভাগ করে দিয়ে পাই

2x + y = 4;

আগের সমীকরণ আর এই সমীকরণের সমাধান সবসময় একই হবে, কারণ তারা মূলত একই সমীকরণ। এখন এর কয়েকটা সমাধান মোটামোটি দেখেই বুঝা যায় x = 1, y =2. বা x = 2, y = 0. প্রথম সমাধানটার সাপেক্ষে এটারও সাধারণ সমাধান বের করার চেষ্টা করিঃ

y = 4 – 2x;

If, x = 1+t, y = 2-2t, যারা উভয়েই পূর্ণসঙ্খ্যা।

তাহলে, (x,y) = (1+t, 2-2t);

এখন (-5t, 2+4t) তে t এর সহগ -5,4, (1+t, 2-2t) তে t এর সহগ 1,-2; এদের কোন তাতপর্য আছে? হ্যাঁ, 5 আর 4 হচ্ছে গিয়ে মূল সমীকরণে x, y এর সহগ। আমরা 4x+5y = 10 এর একটা সমাধান পেয়েছিলাম (0,2), সেখান থেকে সাধারণ সমাধান (0-5t, 2+4t)। 2, 1 ও গসাগু দিয়ে ভাগ করার পর সমীকরণে x,y এর সহগ।  

তাহলে এটাকে জেনারালাইজ করে ফেলি। অবশ্যই আমরা ধরে নিব আমরা সহগের গসাগু দিয়ে সমীকরনকে ভাগ করে নিয়েছি, এবং তার ফলে এখন সহগরা সহমৌলিক।

সিদ্ধান্ত ৪. ax + by = c, [gcd(a,b)=1]; সমীকরণটির একটি পূর্ণ সাংখ্যিক সমাধান যদি হয় (x0,y0) তাহলে এর সাধারণ সমাধান হবে (x,y) = (x0-bt,y0+at) যেখানে t যেকোন পূর্ণসঙ্খ্যা।

এই সিদ্ধান্তটা প্রমাণ করার চেষ্টা কর, খুব সহজেই হয়ে যাবে। আর যদি আমরা গসাগু দিয়ে ভাগ না করতাম, তাহলে সাধারণ সমীকরণকে কিভাবে প্রকাশ করতে তাও বের করে ফেল।

এখন, আমরা একটা সমাধান পেলে সেখান থেকে সাধারণ সমাধান করা শিখলাম। এখন একটা সমাধান তো অন্তত বের করতে হবে। এতক্ষন পর্যন্ত আমরা পর্যবেক্ষণ থেকে অথবা ট্রায়াল অ্যান্ড এরর করে একটা সমাধান করেছি। এখন একটা সাধারণ পদ্ধতি শেখা যাক যেটা সবসময় কাজ করবে।

খেয়াল কর, 2x+y = 4 এর একটা সমাধান খুব সহজেই করা যায়। এখানে x = 0 বসালেই y = 4 পাওয়া যায়। অথবা y = 0 বসালে সহজেই x = 2 পাওয়া যায়। এত সহযে হয়েছে তার মূল কারন এখানে x, y এর সহগেরা প্রত্যেকে 4 কে নিঃশেষে ভাগ করে। তাই যেকোন একটাকে 0 করে দিলে একটা পূর্ণসাংখ্যিক সমাধান পাওয়া যায়। তার মানে কোন সমীকরণ ax+by = c

এটায় a|c হলে বা b|c হলে একটা সমাধান সহজেই হয়। নিচের সমীকরণগুলোর ক্ষেত্রে একটা সমাধান খাতা-কলম ছাড়াই বের করে ফেল।

         I.            2x + 3y = 9

        II.            x + y = 7

      III.            3x + y = 8

      IV.            5x + 7y = 49

       V.            2x + 17y = 51

এখন এরকম অবস্থায় পেলে কি করব সেটা তো বোঝা গেল। তাহলে এরকম অবস্থায় না পেলে কি করব? জোর করে এরকম অবস্থায় আনব।

সেটাই দেখা যাক কিভাবে একটা উদাহরণ দিয়ে।

13x  + 17y = 109

gcd(13,17)  = 1, যা দিয়ে 109 বিভাজ্য। মানে সমীকরণটির সমাধান আছে। এখন 13 বা 17 দিয়ে 109 বিভাজ্য না। তাই অত সহজে আমরা কিছু পেয়ে যাচ্ছি না। তাহলে এক কাজ করে পুরো সমীকরণ থেকে 13 আর 17 এর মধ্যে ছোট 13 কে কমন নেই।

13(x+y-8) + 4y = 109-104 = 5;

So, 13(x+y-8) + 4y = 5;

এখন x+y-8 আরেকটা অজানা রাশি হয়ে যাচ্ছে। ধরি x+y-8 = u. তাহলে সমীকরণটি দাঁড়ায়ঃ

13u + 4y = 5;

আগের সমীকরণ থেকে আরেকটু সহজ একটা সমীকরণ পেলাম। তো আগেরবার যা করেছি একই কাজ আবার করি।

4(3u+y-1) + u = 1;

আবার আরেকটা অজানা রাশি আমদানি করি v = 3u+y-1, তাহলে

4v + u = 1;

আচ্ছা এবার এর একটা সমাধান আমরা করতে পারব।

v = 0, u = 1.

So, v = 3u+y-1 = 1; so 0 = 3x1+y-1, [u আর v এর মান বসিয়ে], so y = -2.

y এর এই মান বসিয়ে পাই, x = 11

তার মানে একটা সমাধানঃ (x,y) = (11,-2);

সাধারণ সমাধানঃ (x,y) = (11-17t,-2+13t), t যেকোন পূর্ণসঙ্খ্যা। এখানে বিভিন্ন মান বসিয়ে দেখে নাও যে এটা আসলেই সাধারণ সমাধান হয়েছে। এখন পদ্ধতিটা অনেক বড় মনে হতে পারে, আসলেই একটু বড় তবে এটা মোটামোটিভাবে সবচেয়ে সহজ পদ্ধতি একঘাত ডায়াফন্টাইন সমীকরণ সমাধানের জন্য।

তবে কেউ নিজে সমাধান করার সময় অবশ্যই এতকিছু লিখার তো দরকার নাই যা আমি বুঝানোর জন্য লিখছিলাম। তাহলে আরেকটা সমীকরণে শুধু কাজগুলো করে দেখাই।

সমীকরণ: 24x + 13y = 81

o    13(x+y-6) + 11x = 3 o    13u + 11x = 3 o    11(u+x) + 2u = 3 o    11v + 2u = 3 o    2(5v + u - 1) + v = 1 o    2w  + v = 1 o    So v = 1, w = 0

o    Now working backwards o    w = 5v +u -1, so u = -4 o    u + x =  v, so x = 5 o    And so y = -3

                একক সমাধান: (x,y) = (5,-3);

                সাধারণ সমাধান: (x,y) = (5+13k, -3-24k)

সহজ সমস্যাঃ

I –III এর জন্য পূর্ণসাঙ্খ্যিক সমাধান বের করঃ

         I.            3x + 18y = 29

        II.            7x + 5y = 13

      III.            3x – 18y = -7

      IV.            x,y উভয়েই ধনাত্মক এমন সকল সমাধান নির্ণয় করঃ 3x + 4y = 48 [Hint: সাধারণ সমাধান নির্ণয় কর, তারপর x>0, y>0 লিখে দুইটা অসমতাকে সমাধান করে সম্ভাব্য সকল t এর মান বের কর]

       V.            3x - 6y = 69 এর জন্য x ঋনাত্মক ও y ধনাত্মক এমন পূর্ণসাঙ্খ্যিক সমাধান কয়টি?

To be continued...