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

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

গণিতে ইউক্লিডীয় এলগরিদম হল গরিষ্ঠ সাধারণ গুণনীয়ক (গসাগু), বা গরিষ্ঠ সাধারণ উৎপাদক নির্ণয় করার জন্যে একটি কার্যকর পদ্ধতি। একে গ্রিক গণিতবিদ ইউক্লিডের নামানুসারে নামকরণ করা হয়েছে, যিনি এলিমেন্টস এর 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 এর চেয়ে ছোট না হয়।

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

• Cohen H (1993). A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. আইএসবিএন 0-387-55640-0. http://books.google.com/books?id=hXGr-9l1DXcC.
• Cohn H (1962). Advanced Number Theory. New York: Dover. আইএসবিএন 0-486-64023-X. http://books.google.com/books?id=yMGeElJ8M0wC.
• Cormen TH, Leiserson CE, Rivest RL, and Stein C (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw–Hill. আইএসবিএন 0262032937. http://books.google.com/books?id=NLngYyWFl_YC.
• Cox D, Little J, and O'Shea D (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (2nd ed.). Springer-Verlag. আইএসবিএন 0-387-94680-2. http://books.google.com/books?id=7eLkq0wQytAC.
• Dirichlet PGL (1894). Richard Dedekind. ed. Vorlesungen über Zahlentheorie. Braunschweig: Vieweg.
• Hardy GH, Wright EM [revised by D.R. Heath-Brown and J.H. Silverman]. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford: Clarendon Press. http://books.google.com/books?id=rey9wfSaJ9EC.
• Knuth D (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison–Wesley. আইএসবিএন 0201896842.
• LeVeque WJ (1977). Fundamentals of Number Theory. New York: Dover. আইএসবিএন 0-486-68906-9.
• Mollin RA (2008). Fundamental Number Theory with Applications (2nd ed.). Boca Raton: Chapman & Hall/CRC. আইএসবিএন 9781420066593.
• Ore Ø (1948). Number Theory and Its History. New York: McGraw–Hill.
• Rosen KH (2000). Elementary Number Theory and its Applications (4th ed.). Reading, MA: Addison–Wesley. আইএসবিএন 0201870738.
• Schroeder MR (2005). Number Theory in Science and Communication (4th ed.). Springer-Verlag. আইএসবিএন 0387158006.
• Stark H (1978). An Introduction to Number Theory. MIT Press. আইএসবিএন 0-262-69060-8.
• Stillwell J (1997). Numbers and Geometry. New York: Springer-Verlag. আইএসবিএন 0-387-98289-2.
• Tattersall JJ (2005). Elementary number theory in nine chapters. Cambridge: Cambridge University Press. আইএসবিএন 9780521850148.
• Uspensky JV, Heaslet MA (1939). Elementary Number Theory. New York: McGraw–Hill.

বহিঃসংযোগ

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