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

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে

দুই বা তার অধিক সংখ্যার গরিষ্ঠ সাধারণ গুণনীয়ক (গ.সা.গু.) হলো সেই বৃহত্তম সংখ্যা যাকে দিয়ে ওই সংখ্যাগুলোকে নিঃশেষে ভাগ করা যায়। ইংরেজি ভাষায় গ.সা.গু. কে বলা হয় "Greatest common divisor" বা (GCD)। কোন ভগ্নাংশকে তার ক্ষুদ্রতম পদে প্রকাশ করার জন্য গ.সা.গু. প্রয়োজন হয়, উদাহরণ: ৪৮ এবং ৭২ এর গ.সা.গু. হলো ২৪, তাহলে:

Image:vognangso.png

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

গ.সা.গু. নির্ণয়[সম্পাদনা]

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

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

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

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

Gcdvenndiagram.svg

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

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

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

৩৬৩এবং১৪৩এরগ.সা.গু.png

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

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

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

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

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

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

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

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

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

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

একি ভাবে বলা যায় {r}_{n\mathrm{-}1} অবশ্যই {r}_{n\mathrm{-}3} এরও গুণনীয়ক কারণ, {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} এভাবে দেখানো যায় {r}_{n\mathrm{-}1} সব গুলো {r}_{x} (x যেকোন ধনাত্মক সংখ্যা) এরই গুণনীয়ক। যেহেতু a এবং b কে {r}_{x} হিসেবে বলা করা যায় সেহেতু প্রমাণিত হলো {r}_{n\mathrm{-}1} a এবং b দুটি সংখ্যাকেই নিঃশেষে ভাগ করে, অর্থাৎ {r}_{n\mathrm{-}1} a এবং b এর একটি সাধারণ গুণনীয়ক, আর তাই {r}_{n\mathrm{-}1}\mathrm{\le }g হতে হবে

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

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

তাহলে বলা যায়, c প্রথম ভাগশেষ {r}_{0} কে নিঃশেষে ভাগ করে কারণ, {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 সব {r}_{x} কেই নিঃশেষে ভাগ করে, যেমন {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 {r}_{n\mathrm{-}1} কে নিঃশেষে ভাগ করে। যেহেতু c\mathrm{=}g হতে পারে সেহেতু বলা যায় g, {r}_{n\mathrm{-}1} এর গুণনীয়ক। এর মানে g\mathrm{\le }{r}_{n\mathrm{-}1} হতে হবে।

এই দুই সর্তকে যদি এক সাথে সত্যি হতে হয় তাহলে নিশ্চিত ভাবে বলা যায়, 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 কে বর্ধিত ইউক্লিডিয়ান অ্যালগরিদম দিয়ে নির্ণয় করা যায়।
  • \mathit{\gcd }\left(a,0\right)\mathrm{=}\mathrm{|}a\mathrm{|}যেখানে a\mathrm{\ne }b, যেহেতু যে কোন সংখ্যাই শূন্যের গুণনীয়ক এবং a এর সবচেয়ে বড় গুণনীয়ক হলো এর পরমমান\mathrm{|}a\mathrm{|}
  • যদি a গুনফল b.c কে নিঃশেষে ভাগ করে এবং gcd(a, b) = d হয় তাহলে a/d, c কেও নিঃশেষে ভাগ করে।
  • যদি m অ-ঋণাত্মক পূর্ণ সংখ্যা হয়, তাহলে gcd(m.am.b) = m.gcd(ab)।
  • যদি m যে কোন পূর্ণ সংখ্যা হয়, তাহলে gcd(a + m.bb) = gcd(ab)।
  • m যদি a এবং b এর অ-শূন্য সাধারণ গুণনীয়ক হয়, তাহলে gcd(a/mb/m) = gcd(ab)/m।
  • গ.সা.গু. গুণনশীলতার নিয়ম মেনে চলে এই অর্থে যে, যদি {a}_{1}এবং {a}_{2}পারস্পরিক ভাবে মৌলিক সংখ্যা হয় মানে যদি তাদের গ.সা.গু ১ হয়, তাহলে \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) এর সাথে সম্পর্কিত, \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