ইউক্লিডীয় এলগরিদম

২৫২ এবং ১০৫ এর জন্যে ইউক্লিডীয় এলগরিদমের এনিমেশন। প্রতিটি ক্রসবার ২১ একক নির্দেশ করছে, যা সংখ্যা দুটির গরিষ্ঠ সাধারণ গুণনীয়ক (গসাগু)। প্রতিটি ধাপে বৃহত্তর সংখ্যাটি থেকে ক্ষুদ্রতর সংখ্যাটি বিয়োগ করা হয়, যে পর্যন্ত একটি সংখ্যা শুণ্যে পরিণত না হয়। তারপর যে সংখ্যাটি রয়ে যায় তাই হল গসাগু।

গণিতে ইউক্লিডীয় এলগরিদম হল গরিষ্ঠ সাধারণ গুণনীয়ক (গসাগু), বা গরিষ্ঠ সাধারণ উৎপাদক নির্ণয় করার জন্যে একটি কার্যকর পদ্ধতি। একে গ্রিক গণিতবিদ ইউক্লিডের নামানুসারে নামকরণ করা হয়েছে, যিনি এলিমেন্টস এর VII এবং X নং খণ্ডে এর বর্ণনা করেছেন।^[১]

দুটি সংখ্যার গসাগু হল সেই বৃহত্তম সংখ্যা যা দুটি সংখ্যাকেই নিঃশেষে বিভাজ্য করে। ইউক্লিডীয় এলগরিগম এই নীতির ওপর প্রতিষ্ঠিত যে বৃহত্তর সংখ্যাটি থেকে ক্ষুদ্রতর সংখ্যাটি বিয়োগ করা হলেও তাদের গসাগু পরিবর্তিত হয় না। যেমন, ২১ হল ২৫২ ও ১০৫ এর গসাগু। (২৫২ = ২১ × ১২; ১০৫ = ২১ × ৫); যেহেতু ২৫২ − ১০৫ = ১৪৭, ১৪৭ ও ১০৫ এর গসাগুও ২১। যেহেতু এ প্রক্রিয়ায় বৃহত্তর সংখ্যাটি ছোট হতে থাকে, তাই এর পুনরাবৃত্তি অপেক্ষাকৃত ক্ষুদ্রতর সংখ্যা প্রদান করে এবং এক সময় একটি সংখ্যা শুণ্য হয়ে যায়। তখন অবশিষ্ট যে সংখ্যাটি রয়ে যায় তাই হয় সংখ্যা দুটির গসাগু। ইউক্লিডীয় এলগরিদমের ধাপসমূহ বিপরীত করে গসাগুকে প্রকৃত সংখ্যা দুটির যোগফল হিসাবে লেখা যায়, যেখানে সংখ্যাদুটিকে কোন ধনাত্বক বা ঋণাত্মক পূর্ণসংখ্যা দ্বারা গুণ করা হয়েছে, উদাহরণস্বরূপ, ২১ = ৫ × ১০৫ + (−২) × ২৫২. এই গুরুত্বপূর্ণ সম্পর্কটি বেঁজোর অভেদ নামে পরিচিত।

ইউক্লিডের এলগরিদম দক্ষতার সাথে বড় বড় সংখ্যার গসাগু নির্ণয় করতে পারে, কারণ এর কখনোই ক্ষুদ্রতর পূর্ণসংখ্যাটিতে থাকা অঙ্কসংখ্যার (১০ ভিত্তিকে) পাঁচ গুণের চেয়ে বেশি ধাপ প্রয়োজন পড়ে না। এ প্রমাণটি ১৮৪৪ সালে গ্যাব্রিয়েল লামি কর্তৃক সম্পন্ন হয়, যা কম্পিউটেশনাল কমপ্লেক্সিটি তত্ত্বের জন্ম দেয়। ইউক্লিডীয় এলগরিদমের দক্ষতা বাড়ানোর বিভিন্ন উপায় ২০ শতকে আবিষ্কৃত হয়েছে।

পটভূমি

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

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

একটি ২৪-বাই-৬০ আয়তক্ষেত্র দশটি ১২-বাই-১২ বর্গাকার খন্ড দিয়ে ভরাট করা হয়েছে, যেখানে ১২ হল ২৪ ও ৬০ এর গসাগু। আরও সাধারণভাবে, একটি 'a-বাই-b আয়তক্ষেত্র c দৈর্ঘবিশিষ্ট বর্গাকার খন্ড দিয়ে ভর্তি করা যাবে, যদি c , 'a এবং b এর সাধারণ উৎপাদক হয়।

ধরি, g = গসাগু(a, b). যেহেতু a এবং b উভয়েই g এর গুণিতক, তাদের এভাবে লেখা যেতে পারে a = mg এবং b = ng, এবং এমন কোন বৃহত্তর সংখ্যা G > g নেই যার জন্যে এটি সত্য হতে পারে। তাই স্বাভাবিক সংখ্যা m এবং n অবশ্যই সহমৌলিক সংখ্যা, কারণ কোন সাধারণ উৎপাদক m এবং n কে ভাগ করলে তা g এর মান বৃহত্তর করবে. তাই, অন্য যেকোন সংখ্যা c যা a এবং b উভয়কেই ভাগ করে তা অবশ্যই gকেও বিভাজ্য করবে। তাই a এবং b এর গরিষ্ঠ সাধারণ উৎপাদক g হল তাদের এমন একটি সাধারণ উৎপাদক যা তাদের অন্য যে কোন সাধারণ উৎপাদক দ্বারা বিভাজ্য।^[৪] ধরি, g = গসাগু(a, b). যেহেতু a এবং b উভয়েই g এর গুণিতক, তাদের এভাবে লেখা যেতে পারে a = mg এবং b = ng, এবং এমন কোন বৃহত্তর সংখ্যা G > g নেই যার জন্যে এটি সত্য হতে পারে। তাই স্বাভাবিক সংখ্যা m এবং n অবশ্যই সহমৌলিক সংখ্যা, কারণ কোন সাধারণ উৎপাদক m এবং n কে ভাগ করলে তা g এর মান বৃহত্তর করবে. তাই, অন্য যেকোন সংখ্যা c যা a এবং b উভয়কেই ভাগ করে তা অবশ্যই gকেও বিভাজ্য করবে। তাই a এবং b এর গরিষ্ঠ সাধারণ উৎপাদক g হল তাদের এমন একটি সাধারণ উৎপাদক যা তাদের অন্য যে কোন সাধারণ উৎপাদক দ্বারা বিভাজ্য।[৪]

গসাগু এভাবে দৃশ্যায়িত করা যেতে পারে।^[৫] ধরা যাক একটি আয়তাকার ক্ষেত্র a বাই b, এবং যেকোন সাধারণ উৎপাদক c যা a এবং b উভয়কেই নিঃশেষে ভাগ করে। ফলে আয়তটির বাহুগুলোকে c দৈর্ঘের বিভিন্ন অংশে ভাগ করা যেতে পারে, যা আয়তটিকে c দৈর্ঘ্যবিশিষ্ট বর্গাকার ছকে ভাগ করে। সর্বোচ্চ সাধারণ উৎপাদক g হল c এর সর্বোচ্চ মান যার জন্যে এরূপ বিভাজন সম্ভব। উদাহরণ হিসাবে বলা যায়, একটি ২৪-বাই-৬০ আয়তক্ষেত্রকে এ সব ভাগে ভাগ করা যেতে পারে: ১-bবাই-১ বর্গ, ২-বাই-২ বর্গ, ৩-বাই-৩ বর্গ, ৬-বাই-৬ বর্গ অথবা ১২-বাই-১২ বর্গ. তাই, ১২ হল ২৪ এবং ৬০ এর গসাগু। একটি ২৪-বাই-৬০ আয়তক্ষেত্রকে ১২-বাই-১২ বর্গাকার ক্ষেত্রে ভাগ করা চলে, যেখানে একটি ধারে দুটি বর্গ (২৪/১২ = ২) এবং অপর ধারে ৫ টি (৬০/১২ = ৫) বর্গ থাকে।

দুটি সংখ্যা a ও b এর গসাগুকে তাদের সাধারণ মৌলিক উৎপাদক দ্বারা সংজ্ঞায়িত করা যেতে পারে।^[৬] উদাহরণস্বরূপ, ৪৬২ কে এভাবে উৎপাদকে বিশ্লেষিত করা যায়: ২ × ৩ × ৭ × ১১ এবং ১০৭১ কে ৩ × ৩ × ৭ × ১৭, ৪৬২ এবং ১০৭১ এর গসাগু হল ২১ = ৩ × ৭, যা তাদের সাধারণ উৎপাদকের গুণফল। যদি দুটি সংখ্যার কোন সাধারণ মৌলিক উৎপাদক না থাকে তখন তাদের গসাগু হয় ১—তারা সহমৌলিক হয়। ইউক্লিডীয় এলগরিদমের সুবিধাহল এখানে গসাগু নির্ণয় করার জন্যে উৎপাদক হিসেব করার প্রয়োজন পড়ে না।^[৭][৮] বড় বড় পূর্ণ সংখ্যার উৎপাদকে বিশ্লেষণ এতটাই কঠিন সমস্যা হিসেবে বিবেচিত যে অনেক আধুনিক ক্রিপ্টোগ্রাফি সিস্টেম এর ওপর ভিত্তি করে তৈরি করা।^[৯]

গসাগুর আরও একটু সূক্ষ্ম সংজ্ঞা উচ্চতর গণিতে সহায়ক হয়, বিশেষ করে বলয় তত্ত্বে।^[১০] দুটি সংখ্যা a ও b এর গরিষ্ঠ সাধারণ গুণনীয়ক g একই সাথে তাদের ক্ষুদ্রতম পূর্ণসাংখ্যিক গুণিতক, অর্থাৎ, ua + vb আকারের ক্ষুদ্রতম সংখ্যা যেখানে u এবং v হল পূর্ণসংখ্যা। এ থেকে বলা যায়, a এবং b এর সকল পূর্ণ সাংখ্যিক গুণিতকের সেট (ua + vb জাতীয় সকল সংখ্যা) g এর পূর্ণ সাংখ্যিক গুণিতকের সেটের সমান। আধুনিক গাণিতিক পরিভাষায়, a এবং b দ্বারা তৈরিকৃত আদর্শ হল g হতে উৎপন্ন প্রধান ধারণা। গসাগুর এই সংজ্ঞার সাথে অন্যান্য সংজ্ঞার সমতুল্যতার বর্ণনা নিম্নে প্রদত্ত হল।

তিন বা ততোধিক সংখ্যার গসাগু হল তাদের মধ্যে থাকা সাধারণ মৌলিক উৎপাদকের গুণফল^[১১], যা সংখ্যা গুলো জোড়ায় জোড়ায় নিয়ে প্রাপ্ত গসাগুর সমান।

বর্ণনা

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

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

কার্যপদ্ধতি

ইউক্লিডীয় এলগরিদম পুনরাবৃত্তিক, অর্থাৎ এর মাধ্যমে সমাধান কয়েকটি ধাপে পাওয়া যায়; প্রতিটি ধাপের ফলাফল পরবর্তী ধাপের সূচনা হিসেবে ব্যবহৃত হয়।^[১২] ধরা যা k হল এলগরিদমটির ধাপ গণনাকারী পূর্ণ সংখ্যা, যা শুন্য থেকে শুরু হয়। তাহলে শুরুর ধাপটি হল k = 0, পরবর্তী ধাপ k = 1, এবং এভাবে চলতে থাকে।

প্রতিটি ধাপ দুটি অঋণাত্মক অবশিষ্ট নিয়ে শুরু হয় r_k−1 এবং r_k−2। যেহেতু এই এলগরিদমের মাধ্যমে প্রতিটি ধাপেই অবশিষ্ট ক্ষুদ্রতর হয়, ফলে r_k−1 তার পূর্ববর্তী r_k−2 এর চেয়ে ছোট। kতম ধাপের লক্ষ্য হল এমন একটি ভাগফল q_k এবং ভাগশেষ r_k খুঁজে বের করা যেন এই সমীকরণটি সিদ্ধ করে

r_k−2 = q_k r_k−1 + r_k

যেখানে r_k < r_k−1. অন্য ভাষায় বললে, ক্ষুদ্রতর সংখ্যা r_k−1এর গুণিতক বৃহত্তর সংখ্যা r_k−2 থেকে বাদ দেয়া হয়, যে পর্যন্ত না ভাগশেষ r_k−1 এর চেয়ে ছোট না হয়।

প্রথম ধাপে (k = 0), a ও b ধরা হল r_-2 ও r_-1, অর্থাৎ মূল সংখ্যা দুটো। পরের ধাপে (k = 1), a এবং b এর মান যথাক্রমে b এবং পূর্ববর্তী ধাপ হতে পাওয়া ভাগশেষ r₀, এবং এভাবে চলতে থাকে। এভাবে এলগরিদমটিকে নিচের মত সমীকরণগুলোর সাহায্যে প্রকাশ করা যায়

a = q₀ b + r₀

b = q₁ r₀ + r₁

r₀ = q₂ r₁ + r₂

r₁ = q₃ r₂ + r₃

…

যদি a এর মান b এর চেয়ে ছোট হয় তবে প্রথম ধাপটির ফলে 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
2. Stark, p. 16.
3. Stark, p. 21.
4. Leveque, p. 31.
5. Grossman JW (১৯৯০)। Discrete Mathematics। New York: Macmillan। পৃষ্ঠা 213। আইএসবিএন 0-02-348331-8। 
6. Schroeder, pp. 21–22.
7. Schroeder, p. 19.
8. Ogilvy CS, Anderson JT (১৯৬৬)। Excursions in number theory। New York: Oxford University Press। পৃষ্ঠা 27–29। এলসিসিএন ৬৬-০ – 0। 
9. Schroeder, pp. 216–219.
10. উদ্ধৃতি ত্রুটি: <ref> ট্যাগ বৈধ নয়; Leveque_p33 নামের সূত্রটির জন্য কোন লেখা প্রদান করা হয়নি
11. Stark, p. 25.
12. Stark, pp. 16–20.

গ্রন্থতালিকা

• Cohen H (১৯৯৩)। A Course in Computational Algebraic Number Theory। New York: Springer-Verlag। আইএসবিএন 0-387-55640-0। 
• Cohn H (১৯৬২)। Advanced Number Theory। New York: Dover। আইএসবিএন 0-486-64023-X। 
• Cormen TH, Leiserson CE, Rivest RL, and Stein C (২০০১)। Introduction to Algorithms (2nd সংস্করণ)। MIT Press and McGraw–Hill। আইএসবিএন 0262032937। উদ্ধৃতি শৈলী রক্ষণাবেক্ষণ: একাধিক নাম: লেখকগণের তালিকা (link)
• Cox D, Little J, and O'Shea D (১৯৯৭)। Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (2nd সংস্করণ)। Springer-Verlag। আইএসবিএন 0-387-94680-2। উদ্ধৃতি শৈলী রক্ষণাবেক্ষণ: একাধিক নাম: লেখকগণের তালিকা (link)
• Dirichlet PGL (১৮৯৪)। Richard Dedekind, সম্পাদক। Vorlesungen über Zahlentheorie। Braunschweig: Vieweg। 
• Hardy GH, Wright EM [revised by D.R. Heath-Brown and J.H. Silverman]. (২০০৮)। An Introduction to the Theory of Numbers (6th সংস্করণ)। Oxford: Clarendon Press। 
• Knuth D (১৯৯৭)। The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd সংস্করণ)। Addison–Wesley। আইএসবিএন 0201896842। 
• LeVeque WJ (১৯৭৭)। Fundamentals of Number Theory। New York: Dover। আইএসবিএন 0-486-68906-9। 
• Mollin RA (২০০৮)। Fundamental Number Theory with Applications (2nd সংস্করণ)। Boca Raton: Chapman & Hall/CRC। আইএসবিএন 9781420066593। 
• Ore Ø (১৯৪৮)। Number Theory and Its History। New York: McGraw–Hill। 
• Rosen KH (২০০০)। Elementary Number Theory and its Applications (4th সংস্করণ)। Reading, MA: Addison–Wesley। আইএসবিএন 0201870738। 
• Schroeder MR (২০০৫)। Number Theory in Science and Communication (4th সংস্করণ)। Springer-Verlag। আইএসবিএন 0387158006। 
• Stark H (১৯৭৮)। An Introduction to Number Theory। MIT Press। আইএসবিএন 0-262-69060-8। 
• Stillwell J (১৯৯৭)। Numbers and Geometry। New York: Springer-Verlag। আইএসবিএন 0-387-98289-2। 
• Tattersall JJ (২০০৫)। Elementary number theory in nine chapters। Cambridge: Cambridge University Press। আইএসবিএন 9780521850148। 
• Uspensky JV, Heaslet MA (১৯৩৯)। Elementary Number Theory। New York: McGraw–Hill। 

বহিঃসংযোগ

• Demonstrations of Euclid's algorithm
• এরিক ডব্লিউ. ওয়াইস্টাইন সম্পাদিত ম্যাথওয়ার্ল্ড থেকে "Euclidean Algorithm"।
• Euclid's Algorithm at cut-the-knot
• Euclid's algorithm at PlanetMath
• The Euclidean Algorithm at MathPages
• Euclid's Game at cut-the-knot
• Music and Euclid's algorithm