গসাগুর ভাগ প্রক্রিয়া: কেন কাজ করে?

চমক হাসান
______________________________________________________________
ছেলেবেলায় আমরা যা কিছু শিখি, তার অনেককিছুর শুধু নিয়মটাই আমাদের শেখা হয়। নিয়মটা কেন এমন হলো, সেটা আর শেখা হয় না। বড় হতে হতে সেই কৌতূহলটুকুও হারিয়ে যায়। ফলে শেখাটা এক রকম অসমাপ্ত থেকে যায়। এমনই একটা নিয়ম হলো গসাগু নির্ণয়ের ভাগ প্রক্রিয়া।

পদ্ধতিটা মনে হয় আমাদের অনেকেরই জানা। তবু একবার মনে করিয়ে দিই।

———————————————–
ছোট সংখ্যা দিয়ে বড়টাকে ভাগ করো। এবার ভাগশেষ যা আসবে তা দিয়ে আগের ভাজককে ভাগ করো। এভাবে করতে থাকো, যখন মিলে যাবে অর্থাৎ ভাগশেষ শূন্য চলে আসবে তখন শেষ ভাজকটাই হবে গসাগু।
———————————————–

উদাহরণ দিলে ভালো করে বোঝা যাবে। ধরা যাক আমরা 20 আর 68 এর গসাগু বের করতে চাই। নিচের ছবিতে ভাগ প্রক্রিয়ায় সেটা করে দেখানো হলো।
_________________________________________________________

20) 68 (3 # 20 দিয়ে 68 কে ভাগ দিই
60 ভাগশেষ হলো 8
——————
8 ) 20 (2 # ভাগশেষ 8 দিয়ে আগের ভাজক
16 20 কে ভাগ দিই। ভাগশেষ 4।
————–
4) 8 (2 # ভাগশেষ 4 দিয়ে আগের ভাজক
8 8 কে ভাগ দিই। মিলে গেল।
————- গসাগু হবে শেষ ভাজক মানে 4।
0
_________________________________________________________

এই পদ্ধতিটাকে বলে ইউক্লিডীয় অ্যালগরিদম, মহামতি ইউক্লিড এখন থেকে ২৩০০ বছর আগে তার এলিমেন্টস গ্রন্থে এই নিয়ম প্রথম বর্ণনা করেন। নিয়মটা আমাদের অনেকের জানা, কিন্তু আমরা অনেকেই জানি না এটা কেন কাজ করে। জানি না কেন বারবার ভাগশেষকে ভাজক বানিয়ে এভাবে আমরা ভাগ করে যাই, আর কেনই বা শেষের ভাজকটাই হয় গসাগু।

******************************
একটু ফিরে দেখা (গসাগু)
******************************

এ পর্যায়ে গসাগুর মূল অর্থটা আরেকবার মনে করে নিই। গসাগু হলো গরিষ্ঠ সাধারণ গুণনীয়ক। যেসব সংখ্যা দিয়ে 20 কে নিঃশেষে ভাগ করা যায় তারাই 20 এর গুণনীয়ক। সেগুলো হলো 1,2,4,5,10,20। একইভাবে 68 এর গুণনীয়কগুলো হলো 1,2,4,17,34,68। এই দুই দলের ভেতরে কমন বা সাধারণ হলো 1, 2 আর 4। এই তিনটা হলো 20 আর 68 এর সাধারণ গুণনীয়ক। আর তাদের ভেতরে সবচেয়ে বড় বা গরিষ্ঠ হলো 4। তাই 4 হলো গসাগু।

অর্থাৎ 4 হলো সবচেয়ে বড় সংখ্যা যাকে দিয়ে 20 ও 68 দুটোকেই নিঃশেষে ভাগ করা যায়। উপরের ভাগ প্রক্রিয়ায় শেষ পর্যন্ত আমরা 4 ই উত্তর পেয়েছি। কিন্তু ইউক্লিডের ভাগ প্রক্রিয়া কী করে এমন একটা সংখ্যা খুঁজে বের করে?

******************************
মূল রহস্য জানার আগে প্রস্তুতি পর্ব
******************************

ভাগ প্রক্রিয়ার গভীরে ঢুকতে গেলে আমাদের জানতে হবে বিয়োগ প্রক্রিয়া। সেটাই আমাদের মূল রহস্, বিয়োগ প্রক্রিয়াটা কী সেটা বলব এর পরের অনুচ্ছেদে। তবে তার আগে বিভাজ্যতার একটা জরুরি ব্যাপার বুঝতে হবে। কথাটা এমনিতে শুনতে সহজ-

দুটো সংখ্যা যদি অন্য একটা সংখ্যা দিয়ে বিভাজ্য হয়, তাহলে সেই দুটো সংখ্যার যোগফল এবং বিয়োগফলও ওই অন্য সংখ্যাটা দিয়ে বিভাজ্য। যেমন 25 আর 15 দুটোই 5 দিয়ে বিভাজ্য। তাই এদের বিয়োগফল 10 আর যোগফল 40-ও হবে 5 দিয়ে বিভাজ্য।

এটার প্রমাণও সহজ। ধরা যাক a ও b দুটো পূর্ণসংখ্যাই আরেকটা পূর্ণসংখ্যা c দিয়ে বিভাজ্য।

যেহেতু a সংখ্যাটা c দিয়ে বিভাজ্য, এদের ভাগফল a/c হবে একটা পূর্ণসংখ্যা। সেই ভাগফলকে নাম দিই m।

a/c=m
∴ a=mc ——- (i)

একইভাবে b/c ও হবে পূর্ণসংখ্যা, সেই ভাগফলকে একটা পূর্ণসংখ্যা n ধরলে পাবো,
b/c=n,
∴ b=nc ——- (ii)

(i)+(ii) থেকে পাবো,
a+b=c(m+n)
∴ (a+b)/c=(m+n)

m,n পূর্ণসংখ্যা হলে m+n ও হবে পূর্ণসংখ্যা। তার মানে a,b এর যোগফল a+b, ও হবে c দ্বারা বিভাজ্য। একইভাবে (i)-(ii) করলে আসবে (a-b)/c=(m-n)। ফলে a,b এর বিয়োগফল a+b, ও হবে c দ্বারা বিভাজ্য। অর্থাৎ দুটো সংখ্যা আরেকটা সংখ্যা দিয়ে বিভাজ্য হলে যোগফল বিয়োগফলও ওই আরেকটা সংখ্যা দিয়ে বিভাজ্য।

এটা জানা হলে এবার যাওয়া যেতে পারে মূল রহস্য বিয়োগ পদ্ধতি বুঝতে।

******************************
মূল রহস্য (বিয়োগ পদ্ধতি)
******************************

ইউক্লিডের পদ্ধতির মূল রহস্য বোঝা যাবে একটা সম্পর্ক জানলে, সেটা হলো
GCD(a, b)=GCD(a, b-a)

এখানে GCD(a,b) মানে হলো দুটো সংখ্যা a আর b এর গসাগু (GCD=Greatest Common Divisor)। এই উপরের লাইনটা বলছে যে দুটো সংখ্যার গসাগু যা হবে, ওদের বিয়োগফল এবং ওদের যেকোনো একটা সংখ্যার গসাগু-ও একই হবে।

এটা বুঝলেই মূল বোঝাটা শেষ। কারণ এই সম্পর্কটাই বারবার ব্যবহার করা হয় ইউক্লিডের অ্যালগরিদমে। এই সম্পর্কটা ঠিক কেন সেটা বোঝাই এবার।

ধরা যাক, a আর b এর গসাগু p। তাহলে p হলো সেই সবচেয়ে বড় সংখ্যা যেটা দিয়ে a আর b দুটোই বিভাজ্য।

p দিয়ে যেহেতু a, b দুটোই বিভাজ্য, তাহলে প্রস্তুতি পর্বে যা জেনেছি সেখান থেকে বলে দেয়া যায় যে b, a এর বিয়োগফল (b-a)ও p দিয়ে বিভাজ্য। এখান থেকে চিন্তা করা যায় যে a এবং (b-a) এর গসাগু হবে p। কেন? আগেই বলেছি p গসাগু হওয়ার মানে হলো p হবে এমন সবচেয়ে বড় সংখ্যা যা দিয়ে a এবং (b-a) দুটোই বিভাজ্য। p দিয়ে দুটোই বিভাজ্য, সেটা তো বুঝলাম, কিন্তু এটার চেয়ে বড় আর কেউ নেই, সেটা কী করে নিশ্চিত হই? হওয়া যায় আসলে।

p এর চেয়ে বড় কোনো সংখ্যা q দিয়ে যদি a আর (b-a) দুটোই বিভাজ্য হতো, সেই বড়ভাই q দিয়ে a আর (b-a) এর যোগফলও বিভাজ্য হয়ে যেত। কিন্তু a আর (b-a) এর যোগফল b। তার মানে q দিয়ে যদি a আর (b-a) দুটোই বিভাজ্য হতো, তাহলে q দিয়ে b ও বিভাজ্য হয়ে যেত।

ভেবে দেখো এমন হলে সেই বড়ভাই q নিজেই হয়ে যেত a, b এর গসাগু, p কে হটিয়ে দিয়ে। কিন্তু আমরা আগেই বলে দিয়েছি (a,b) এর গসাগু p, এর চেয়ে বড় সাধারণ গুণনীয়ক আর নাই। আর কোনো বড় ভাইটাই এখানে নাই।

সুতরাং p এর চেয়ে বড় আর কোনো সংখ্যা নেই যা দিয়ে a আর (b-a) দুটোই বিভাজ্য। অর্থাৎ a এবং (b-a) এর গসাগু হবে p। অর্থাৎ GCD(a, b)=GCD(a, b-a) ।

*********************************
বিয়োগ থেকে ভাগের পথে (প্রথম ধাপ)
*********************************

এবারে GCD(a, b)=GCD(a, b-a) এই সম্পর্ক ব্যবহার করে আমরা শুরুর অঙ্কটা করব। বের করতে হবে GCD(20,68)। আমরা প্রতিবার ছোটটাকে রাখব আর বিয়োগফলটাকে রাখব। ডানদিকে আমাদের পুরনো ভাগ পদ্ধতিটাও দিচ্ছি বোঝার সুবিধার্থে।
________________________________________________
GCD(20,68) | 20) 68 (3
= GCD(20,48) ∵ 68-20=48 | 60
= GCD(20,28) ∵ 48-20=28 | ——–
= GCD(20,8) ∵ 28-20=8 | 8
________________________________________________

এবারে এটার সঙ্গে আমরা একেবারে শুরুর ভাগ প্রক্রিয়াটা মিলিয়ে দেখি। আসলে এখানে যে তিন লাইন আছে, তাকেই সংক্ষেপে লেখা হয়েছে ভাগ প্রক্রিয়ায়।

68 থেকে আমরা 20 কে কতবার বাদ দিতে পারি, যেন ঋণাত্মক কিছু না আসে? ধরো একটা চৌবাচ্চায় 68 মগ পানি আছে। এখন একটা বড় বালতি যেটাতে 20 মগ পানি আঁটে, সেই বালতি দিয়ে কতবার চৌবাচ্চা থেকে পানি তুলে নিতে পারবে?

উত্তর হলো 3 বার। একারণেই বামদিকে 3 বার বিয়োগ করা হয়েছে। আর ভাগ প্রক্রিয়ায় এ কারণেই ভাগফল এসেছে 3। আর 20 মগের বালতি দিয়ে 3 বার পানি ওঠালে মোট পানি উঠবে তিন-বিশে ষাট মগ, তারপর বাকি থাকবে 68-60=8 মগ। উপরে বামপাশের শেষ লাইনে যে বিয়োগফল, এটাই সেই 8। আর ডানদিকে ভাগ প্রক্রিয়ায় এই 8-কেই আমরা পাই ভাগশেষ হিসাবে।

এই বিয়োগের প্রক্রিয়া আমাদের নিশ্চিত করছে যে, শেষ বিয়োগফল 8 আর শুরুর ছোট সংখ্যা 20 এর গসাগু যা, মূল দুটো সংখ্যা 20 আর 68 এর গসাগুও তা। GCD(20,68) = GCD(20,8)।

ভাগের দিকে তাকালে এই কথাটার মানে দাঁড়ায়, “ভাজক আর ভাজ্যের গসাগু হবে ভাজক আর ভাগশেষের গসাগুর সমান”।

*********************************
বিয়োগ থেকে ভাগের পথে (দ্বিতীয় ধাপ)
*********************************

দেখো, উপরের বিয়োগগুলোতে 20 কে আমরা স্থির রেখেছি, কারণ 20 ছিল ছোট। তিনবার বাদ দেয়ার পরে 20 এর চেয়ে ছোট একটা সংখ্যা চলে 8 এসেছে। এখন 20 কে আর স্থির না রেখে 8 কে স্থির করি।

GCD(20,8) কে একটু সাজিয়ে GCD(8,20) লিখে নিচ্ছি, 8 কে আগে রাখছি। এমনিতে যদিও গসাগুতে আগে পরে কোনোই ব্যাপার না, এখানে আমি সামনে রাখছি এটা বোঝাতে যে, 8 স্থির থাকবে, আর বাকিটাতে বিয়োগফল বসবে।

________________________________________________
| 8 ) 20 (2
GCD(8,20) | 16
= GCD(8,12) ∵ 20-8=12 | ——–
= GCD(8, 4) ∵ 12-8=4 | 4
________________________________________________

আবার শুরুর ভাগ প্রক্রিয়ায় তাকাও। সেখানে আগের বারের ভাগশেষ 8 কে ভাজক বানানো হয়েছে। বিয়োগের এখানে 8 কে স্থির রেখে আমরাও সেই কাজটাই করেছি।
20 থেকে 8 কে 2 বার বাদ দেয়া যায়। তাই ভাগ প্রক্রিয়ায় ভাগফল ছিল 2। দুইবারে আট আর আট 16 বাদ দেওয়ার পর ভাগশেষ পড়ে থাকে 4।

উপরে বামপাশে বিয়োগ প্রক্রিয়ার শুরুর আর শেষের লাইনে তাকালে দেখি, 8 আর 20 এর গসাগু হবে 8 আর 4 এর গসাগুর সমান। এদেরকেই দেখা যাচ্ছে ডানপাশেও: ভাজক, ভাজ্য আর ভাগশেষে।

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

—————————————–
বিয়োগ প্রক্রিয়া হোক বা ভাগ, আমাদের লক্ষ্য হলো সংখ্যাদুটোকে ছোট করতে থাকা। ভাগ প্রক্রিয়াকে ভাবা যায় বিয়োগ প্রক্রিয়ারই দ্রুত আর সংক্ষিপ্ত রূপ হিসেবে। বিয়োগে যেটা কয়েক ধাপে করতে হয়, সেটা ভাগ প্রক্রিয়ায় একধাপেই আমরা করে ফেলি।
—————————————–

*********************************
বিয়োগ থেকে ভাগের পথে (শেষ ধাপ)
*********************************

কিন্তু বিমান যত দ্রুতই উড়ুক, তাকে থামতে জানতে হয়। এবার উপরে বিয়োগের প্রক্রিয়ার শেষ লাইনে তাকাই। GCD(8,4) । এই অবস্থায় এসে আমরা দেখি এমন দুটো সংখ্যা আমরা পেয়েছি, যাদের একটা দিয়ে অন্যটা বিভাজ্য। এমন হলে গসাগু বের করা খুব সোজা। গসাগু হবে এদেরই একটা। এদের ভেতর যে সংখ্যাটা দিয়ে অন্যটা বিভাজ্য সেই সংখ্যাটাই হবে গসাগু। 4 দিয়ে 8 বিভাজ্য। তাই 4 হবে গসাগু।

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

GCD(4,8)=4

এজন্য ভাগ প্রক্রিয়ায় যখনই মিলে যায়, যখনই আমরা বুঝে যাই একটা দিয়ে অন্যটা বিভাজ্য, তখনই আমাদের কাজ শেষ। আমরা বলতে পারি, যেই ধাপে মিলে গেল সেই ভাজকটাই হলো গসাগু।

ব্যাস এটাই হলো ভাগ প্রক্রিয়া।
.
******************************
পুনশ্চ -১
******************************
.
ভাগপ্রক্রিয়া বোঝা শেষ। তবে আগ্রহীরা চাইলে বিয়োগের প্রক্রিয়া আরও দুইবার চালিয়ে যেতে পারব। GCD(4,8)= GCD(4,4)= GCD(0,4)।

শূন্য এবং যেকোনো ধনাত্মক সংখ্যার গসাগু হলো ওই ধনাত্মক সংখ্যা। কারণটা একটু আগে যেমন বলেছি তেমন। এখানে দেখো 0 সংখ্যাটা সব সংখ্যা দ্বারা বিভাজ্য, তাই সে 4 দিয়েও বিভাজ্য। আর 4 নিজে 4 দ্বারা বিভাজ্য। 0 ও 4 দুটোই 4 দ্বারা বিভাজ্য। আরও স্পষ্ট করে বললে 4 হলো সবচেয়ে বড় সংখ্যা যা দিয়ে 0 ও 4 দুইই বিভাজ্য। তাই 4-ই হবে গসাগু।

******************************
পুনশ্চ -২
******************************

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