গরিষ্ঠ সাধারণ গুণনীয়ক

দুই বা তার অধিক সংখ্যার গরিষ্ঠ সাধারণ গুণনীয়ক (গ.সা.গু.) হলো সেই বৃহত্তম সংখ্যা যাকে দিয়ে ওই সংখ্যাগুলোকে নিঃশেষে ভাগ করা যায়। (অর্থাৎ, ভাগ করার পর কোনো ভাগশেষ থাকে না।) কোনো ভগ্নাংশকে তার ক্ষুদ্রতম পদে প্রকাশ করার জন্য গ.সা.গু.-র প্রয়োজন হয়।

উদাহরণ: ৪৮ এবং ৭২-এর গ.সা.গু. হলো ২৪, তা হলে–

+৪৮/৭২ = +৪৮ ÷ ২৪/৭২ ÷ ২৪ = +২/৩

(অর্থাৎ +৪৮/৭২ = +২ × ২৪/৩ × ২৪ = +২/৩)

মানে +৪৮/৭২ এর ক্ষুদ্রতম রূপ হল +২/৩। দুটি সংখ্যার গ.সা.গু. যদি ১ হয় তা হলে তাদেরকে সহমৌলিক সংখ্যা বলে, যেমন: ৯ এবং ২৮-এর গ.সা.গু. ১, তাই তারা সহমৌলিক। যেমন: 9)28(3

 27
  1)9(1
    9
    0

গ.সা.গু. নির্ণয়

মৌলিক গুণনীয়ক বা উৎপাদকের সাহয্যে গ.সা.গু. নির্ণয়

গ.সা.গু. মানে যেহেতু সবচেয়ে বড় সাধারণ উৎপাদক, তাই যেসব সংখ্যার গ.সা.গু. বের করতে হবে তাদের মৌলিক উৎপাদকগুলো (prime factor) জানা থাকলে, সেসব মৌলিক উৎপাদকগুলোর মধ্যে যেগুলো সবগুলো সংখ্যার জন্য সাধারণ (common) (অর্থাৎ, যেসকল মৌলিক উৎপাদক উভয় সংখ্যা বা ততোধিক সংখ্যায় বিদ্যমান) সেগুলোকে নিয়ে গুণ করলে ওই সংখ্যাগুলোর সবচেয়ে বড় সাধারণ উৎপাদক বা গ.সা.গু. পাওয়া যায়। উদাহরণ: ৪৮ এবং ১৮০ এর মৌলিক উৎপাদকগুলো হল,

৪৮ = ২ × ২ × ২ × ২ × ৩

১৮০ = ২ × ২ × ৩ × ৩ × ৫

এখানে ৪৮ এবং ১৮০-এর জন্য দুটি ২ এবং একটি ৩ সাধারণ (common) মৌলিক উৎপাদক (অর্থাৎ, যে মৌলিক উৎপাদক বা সংখ্যাগুলো উভয়েই বিদ্যমান), তা হলে ৪৮ এবং ১৮০-এর গ.সা.গু. হলো ২ × ২ × ৩ = ১২।
নিচে ভেনচিত্রের মাধ্যমে উদাহরণটিকে আরও সুস্পষ্ট করে দেখানো হল:

যদি সংখ্যাগুলোর কোন মৌলিক সাধারণ উৎপাদক না থাকে, তবে তাদের গ.সা.গু. হবে ১।

ভাগ প্রক্রিয়ার মাধ্যমে গ.সা.গু নির্ণয়

গ.সা.গু. নির্ণয়ের জন্য মৌলিক উৎপাদক পদ্ধতির চেয়ে অনেক বেশি কার্যকর পদ্ধতি হলো গ্রিক গণিতবিদ ইউক্লিডের^[1] লিপিবদ্ধ করা ভাগ প্রক্রিয়ার এ পদ্ধতিটি। এটিকে ইউক্লিডের অ্যালগরিদম বলা হয়। এই অ্যালগরিদম বা প্রক্রিয়াটি এই পর্যবেক্ষণ থেকে এসেছে যে, দুটি সংখ্যা—${\displaystyle a}$, ${\displaystyle b}$ (যেখানে ${\displaystyle a>b}$)-এর গ.সা.গু. আর ${\displaystyle (a-b)}$, ${\displaystyle b}$-এর গ.সা.গু. একই হয়। যদি সংখ্যাগুলো যথাক্রমে ১৪৩ এবং ৭৭ হয় তাহলে, গসাগু(১৪৩, ৭৭) = গসাগু(৭৭, (১৪৩ − ৭৭)) = ১১। অর্থাৎ দুটি সংখ্যার গ.সা.গু. সংখ্যা দুটির পরমদূরত্বকেও নিঃশেষে ভাগ করে এবং সংখ্যা দুটির পরমদূরত্ব ও তাদের ক্ষুদ্রতম সংখ্যার গ.সা.গু. মূল সংখ্যা দুটির গ.সা.গু. এর সমান।
যদি এ পর্যবেক্ষণ সঠিক হয় তাহলে এই প্রক্রিয়াটি কিছু সংখ্যক বার পুনরাবৃত্তি করা হলে, মানে বড় সংখ্যাটি থেকে ছোট সংখ্যাটি বিয়োগ করে বিয়োগফল এবং ছোট সংখ্যাটি নিয়ে আবার একি কাজ করা হলে এক সময় বিয়োগফল এবং ছোট সংখ্যাটি সমান হয়ে যাবে, আর আমরা বুঝতে পারি দুটি সংখ্যা সমান হলে তাদের গরিষ্ঠ সাধারণ গুণনীয়ক হবে ওই সংখ্যাটিই। তাহলে অবশেষে আমরা মূল সংখ্যা দুটি এবং এই প্রক্রিয়ায় মধ্যবর্তী যতগুলো সংখ্যার জোড়া এসেছে তাদের সবার গ.সা.গু. পেয়ে যাবো। যেহেতু বারবার বিয়োগ করা মানে ভাগ করা তাই বিয়োগ না করে ছোট সংখ্যাটি দিয়ে বড় সংখ্যাটিকে ভাগ করে ভাগশেষ এবং ছোট সংখ্যাটি নিয়ে পুরো প্রক্রিয়াটিকে আরো দ্রুত শেষ করা সম্ভব। নিচে ভাগের মাধ্যমে ৩৬৩ এবং ১৪৩ এর গ.সা.গু নির্ণয়ের ধাপ গুলো দেখানো হল:

উপরের ছবিতে ভাগশেষগুলোকে ইংরেজি ${\displaystyle r}$ এবং ভাগফলগুলোকে ${\displaystyle q}$ দ্বারা চিহ্নিত করা হয়েছে।
বিধিসন্মত ভাবে ইউক্লিডের অ্যালগরিদমকে নিচের মতো করে বর্ণনা করা যায়:

${\displaystyle \operatorname {gcd} (a,0)=a}$

${\displaystyle \operatorname {gcd} (a,b)=\operatorname {gcd} (b,a-b\left\lfloor {a \over b}\right\rfloor ).}$

এটাকে আবার এই ভাবেও লেখা যায়:

${\displaystyle \operatorname {gcd} (a,0)=a}$

${\displaystyle \operatorname {gcd} (a,b)=\operatorname {gcd} (b,a{\mbox{ mod }}b).}$

ভাগ প্রক্রিয়ায় গ.সা.গু. নির্ণয় পদ্ধতির সত্যতা প্রমাণ

ইউক্লিডের অ্যালগরিদমকে দুটি পর্যায়ক্রমিক যুক্তির মাধ্যমে প্রমাণ করা সম্ভব।

• প্রথম পর্যায়ে দেখানো হয় যে সর্বশেষ অ-শূন্য ভাগশেষ ${\displaystyle {r}_{n\mathrm {-} 1}}$ ${\displaystyle a}$ এবং ${\displaystyle b}$ দুটি সংখ্যাকেই নিঃশেষে ভাগ করে। যেহেতু ${\displaystyle a}$ এবং ${\displaystyle b}$-এর গ.সা.গু.(${\displaystyle g}$)-ও ঠিক একই কাজ করে তা হলে ${\displaystyle {r}_{n\mathrm {-} 1}}$ কে অবশ্যই ${\displaystyle g}$-এর চেয়ে ছোট বা সমান হতে হবে।
• দ্বিতীয় পর্যায়ে দেখানো হয় ${\displaystyle a}$ এবং ${\displaystyle b}$-এর যে-কোন সাধারণ গুণনীয়ক (যার মধ্যে ${\displaystyle g}$-ও আছে) ${\displaystyle {r}_{n\mathrm {-} 1}}$-কে নিঃশেষে ভাগ করে, আর তাই যদি হয় তা হলে ${\displaystyle g}$-কে অবশ্যই ${\displaystyle {r}_{n\mathrm {-} 1}}$ এর চেয়ে ছোট অথবা সমান হতে হবে! আর এই দুটা প্রমাণ পরস্পরকে বাতিল করে দেয় যদি সর্বশেষ অ-শূন্য ভাগশেষ ${\displaystyle {r}_{n\mathrm {-} 1}}$ই গ.সা.গু. না হয়।

সর্বশেষ অ-শূন্য ভাগশেষ ${\displaystyle {r}_{n\mathrm {-} 1}}$ ${\displaystyle a}$ এবং ${\displaystyle b}$ দুটি সংখ্যাকেই নিঃশেষে ভাগ করে

${\displaystyle {r}_{n\mathrm {-} 1}}$ যে ${\displaystyle a}$ এবং ${\displaystyle b}$-এর গুণনীয়ক তা দেখানোর জন্য প্রথমে দেখানো হয় ${\displaystyle {r}_{n\mathrm {-} 1}}$ তার আগের ভাগশেষ ${\displaystyle {r}_{n\mathrm {-} 2}}$ এর গুণনীয়ক।

যেহেতু ${\displaystyle {r}_{n}\mathrm {=} 0}$

সেহতু ${\displaystyle {r}_{n\mathrm {-} 1}}$ অবশ্যই ${\displaystyle {r}_{n\mathrm {-} 2}}$ এর গুণনীয়ক, অর্থাৎ ${\displaystyle {r}_{n\mathrm {-} 2}\mathrm {=} {r}_{n\mathrm {-} 1}{q}_{n}}$

একই-ভাবে বলা যায় ${\displaystyle {r}_{n\mathrm {-} 1}}$ অবশ্যই ${\displaystyle {r}_{n\mathrm {-} 3}}$ এরও গুণনীয়ক কারণ, ${\displaystyle {r}_{n\mathrm {-} 3}\mathrm {=} {r}_{n\mathrm {-} 2}{q}_{n\mathrm {-} 1}+{r}_{n\mathrm {-} 1}\mathrm {=} {r}_{n\mathrm {-} 1}{q}_{n}{q}_{n\mathrm {-} 1}+{r}_{n\mathrm {-} 1}\mathrm {=} \left({q}_{n}{q}_{n\mathrm {-} 1}+1\right){r}_{n\mathrm {-} 1}}$ এভাবে দেখানো যায় ${\displaystyle {r}_{n\mathrm {-} 1}}$ সব গুলো ${\displaystyle {r}_{x}}$ (${\displaystyle x}$ যেকোন ধনাত্মক সংখ্যা) এরই গুণনীয়ক। যেহেতু ${\displaystyle a}$ এবং ${\displaystyle b}$-কে ${\displaystyle {r}_{x}}$ হিসেবে বলা করা যায় সেহেতু প্রমাণিত হলো ${\displaystyle {r}_{n\mathrm {-} 1}}$ ${\displaystyle a}$ এবং ${\displaystyle b}$ দুটি সংখ্যাকেই নিঃশেষে ভাগ করে, অর্থাৎ ${\displaystyle {r}_{n\mathrm {-} 1}}$ ${\displaystyle a}$ এবং ${\displaystyle b}$-এর একটি সাধারণ গুণনীয়ক, আর তাই ${\displaystyle {r}_{n\mathrm {-} 1}\mathrm {\leq } g}$ হতে হবে।

a এবং b এর যে কোন সাধারণ গুণনীয়ক ${\displaystyle {r}_{n\mathrm {-} 1}}$ কে নিঃশেষে ভাগ করে:

ধরা যাক a এবং b এর এটি সাধারণ গুননীয়ক হলো c সেক্ষেত্রে ${\displaystyle a\mathrm {=} {\mathit {dc}}}$এবং ${\displaystyle b\mathrm {=} {\mathit {ec}}}$(যেখানে d, e যেকোন সংখ্যা)।

তাহলে বলা যায়, c প্রথম ভাগশেষ ${\displaystyle {r}_{0}}$ কে নিঃশেষে ভাগ করে কারণ, ${\displaystyle {r}_{0}\mathrm {=} a\mathrm {-} {\mathit {bq}}_{0}\mathrm {=} {\mathit {dc}}\mathrm {-} {\mathit {ecq}}_{0}\mathrm {=} \left(d\mathrm {-} {\mathit {eq}}_{0}\right)c}$

একি ভাবে দেখানো যায় c সব ${\displaystyle {r}_{x}}$ কেই নিঃশেষে ভাগ করে, যেমন ${\displaystyle {r}_{1}\mathrm {=} b\mathrm {-} {r}_{0}{q}_{1}\mathrm {=} {\mathit {ec}}\mathrm {-} \left(d\mathrm {-} {\mathit {eq}}_{0}\right){\mathit {cq}}_{1}\mathrm {=} \left(e\mathrm {-} \left(d\mathrm {-} {\mathit {eq}}_{0}\right){q}_{1}\right)c}$

তাই প্রমাণিত হয়, c ${\displaystyle {r}_{n\mathrm {-} 1}}$ কে নিঃশেষে ভাগ করে। যেহেতু ${\displaystyle c\mathrm {=} g}$ হতে পারে সেহেতু বলা যায় ${\displaystyle g}$, ${\displaystyle {r}_{n\mathrm {-} 1}}$ এর গুণনীয়ক। এর মানে ${\displaystyle g\mathrm {\leq } {r}_{n\mathrm {-} 1}}$ হতে হবে।

এই দুই সর্তকে যদি এক সাথে সত্যি হতে হয় তাহলে নিশ্চিত ভাবে বলা যায়, ${\displaystyle g\mathrm {=} {r}_{n\mathrm {-} 1}}$। অর্থাৎ ভাগ প্রক্রিয়ার সত্যতা প্রমাণিত হলো।

গ.সা.গু. এর বৈশিষ্ট্য সমূহ:

• a এবং b এর সকল সাধারণ গুণনীয়ক gcd(a, b) এর ও গুণনীয়ক
• gcd(a, b) (যেখানে a এবং b এর উভয়ই শূন্য না), হলো সে ক্ষুদ্রতম ধনাত্মক সংখ্যা g যাকে লেখা যায় g = a.p + b.q যেখানে p এবং q দুটাই পূর্ণ সংখ্যা। এই সমতাকে বলা হয় বেজাওটের আইডেনটেটি। p এবং q কে বর্ধিত ইউক্লিডিয়ান অ্যালগরিদম দিয়ে নির্ণয় করা যায়।
• ${\displaystyle {\mathit {\gcd }}\left(a,0\right)\mathrm {=} \mathrm {|} a\mathrm {|} }$যেখানে ${\displaystyle a\mathrm {\neq } b}$, যেহেতু যে কোন সংখ্যাই শূন্যের গুণনীয়ক এবং a এর সবচেয়ে বড় গুণনীয়ক হলো এর পরমমান${\displaystyle \mathrm {|} a\mathrm {|} }$।
• যদি a গুনফল b.c কে নিঃশেষে ভাগ করে এবং gcd(a, b) = d হয় তাহলে a/d, c কেও নিঃশেষে ভাগ করে।
• যদি m অ-ঋণাত্মক পূর্ণ সংখ্যা হয়, তাহলে gcd(m.a, m.b) = m.gcd(a, b)।
• যদি m যে কোন পূর্ণ সংখ্যা হয়, তাহলে gcd(a + m.b, b) = gcd(a, b)।
• m যদি a এবং b এর অ-শূন্য সাধারণ গুণনীয়ক হয়, তাহলে gcd(a/m, b/m) = gcd(a, b)/m।
• গ.সা.গু. গুণনশীলতার নিয়ম মেনে চলে এই অর্থে যে, যদি ${\displaystyle {a}_{1}}$এবং ${\displaystyle {a}_{2}}$পারস্পরিক ভাবে মৌলিক সংখ্যা হয় মানে যদি তাদের গ.সা.গু ১ হয়, তাহলে ${\displaystyle {\mathit {\gcd }}\left({a}_{1}.{a}_{2},b\right)\mathrm {=} {\mathit {\gcd }}\left({a}_{1},b\right).{\mathit {\gcd }}\left({a}_{2},b\right)}$।
• গ.সা.গু. বিনিময় নিয়ম মেনে চলে: gcd(a, b) = gcd(b, a) ।
• গ.সা.গু. সহযোজন নিয়ম মেনে চলে: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)।
• বিনিময় নিয়ম এবং সহযোজন নিয়ম অনুসারে তিনটি সংখ্যার গ.সা.গু. এভাবে নির্ণয় করা যায়: gcd(a, b, c) = gcd(gcd(a, b), c) । এ পদ্ধতিকে তিন এর অধিক সংখ্যার গ.সা.গু নির্ণয়ের বেলাতেও ব্যবহার করা যায়।
• গ.সা.গু. দুটি সংখ্যার লঘিষ্ঠ সাধারণ গুণিতক (ল.সা.গু / lcm) এর সাথে সম্পর্কিত, ${\displaystyle {\mathit {\gcd }}\left(a,b\right).{\mathit {lcm}}\left({\mathit {a.b}}\right)\mathrm {=} {\mathit {a.b}}}$।

তথ্যসূত্র

1. Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications