यूक्लिड एल्गोरिदम कैलकुलेटर

a = q * b + r, इसलिए gcd(a, b) = gcd(b, r); r = 0 होने तक दोहराइए, और तब b ही जवाब है

a = q * b + r

एल्गोरिदम का एक चक्र, समीकरण के रूप में लिखा हुआ। इस चक्र में a दोनों संख्याओं में से बड़ी है, b छोटी, q यह बताता है कि b, a में पूरी-पूरी कितनी बार जाता है, और r वह है जो बच जाता है। पेज के चरण ठीक इसी लिपि में छपते हैं: 1071 = 2 * 462 + 147 एक चक्र है

a, b

वे दो संख्याएँ जिनकी तुलना हो रही है। हर चक्र में इनकी भूमिका बदल जाती है — एक चक्र का b अगले चक्र का a बन जाता है, और r नया b बन जाता है। इसी अदल-बदल की वजह से इनपुट फ़ील्ड के नाम भाज्य और भाजक नहीं हैं: पहले चक्र में 1071 भाज्य है, दूसरे चक्र में 462, और जो नाम एक चक्र के लिए सही हो वह बाक़ी चक्रों के लिए ग़लत है

q

भागफल, यानी b, a में पूरे-पूरे कितनी बार जाता है। यह हमेशा कम से कम 1 होता है, क्योंकि चक्र शुरू होने से पहले जोड़ी को घटते क्रम में लगाया जाता है — और इसीलिए यहाँ q = 0 कभी नहीं दिखेगा। केवल आख़िरी चक्र में q बेढब नहीं लगता, जहाँ शेषफल शून्य है और भाग ठीक-ठीक बैठता है

r

शेषफल, जो हमेशा b से छोटा होता है और कभी ऋणात्मक नहीं। एल्गोरिदम का रुकने का नियम r = 0 है, और वह आख़िरी चक्र के रूप में छपता है, छोड़ा नहीं जाता: 147 = 7 * 21 + 0 वह पंक्ति है जो कहती है कि खोज ख़त्म और जवाब 21 है

gcd(a, b)

महत्तम समापवर्तक: वह सबसे बड़ी पूर्ण संख्या जो a और b दोनों को बराबर बाँट दे। जवाब आख़िरी चक्र का b है, सीधे चक्र से उठाया हुआ, दोबारा गिना हुआ नहीं। 1071 और 462 के लिए वह 21 है, इसीलिए 1071 = 21 × 51 और 462 = 21 × 22, और इन दोनों को इससे बड़ी कोई संख्या नहीं बाँटती

610 = 1 * 377 + 233

सबसे बुरे मामले का पहला चक्र: लगातार दो फ़िबोनाची संख्याएँ। यहाँ हर भागफल 1 है और संख्याएँ मुश्किल से सिकुड़ती हैं, और यही इस जोड़ी को तेरह चक्रों तक खींचता है। लामे प्रमेय कहती है कि इस आकार की कोई जोड़ी इससे ज़्यादा चक्र नहीं ले सकती

भिन्न को छोटा करना इसका रोज़मर्रा का इस्तेमाल है। 462/1071 को न्यूनतम रूप में लिखने के लिए दोनों का महत्तम समापवर्तक चाहिए, और यह पेज वह भी देता है और उसका सबूत भी — 21, और वे तीन चक्र जिन्होंने उसे निकाला। ऊपर और नीचे दोनों को 21 से भाग देने पर 22/51 मिलता है, और छपे हुए चरण ही वह चीज़ हैं जिनसे आप इस छोटा करने को मान लेने के बजाय जाँच सकते हैं। यही ज़रूरत हर उस जगह आती है जहाँ किसी अनुपात को सरल करना हो: गियर के अनुपात, स्क्रीन के पहलू अनुपात, नक़्शे के पैमाने, और कोई भी दो माप जिन्हें दो संख्याओं की जोड़ी के बजाय एक अनुपात की तरह लिखना हो। दूसरा इस्तेमाल कोड और क्लासरूम में है, जहाँ इस एल्गोरिदम को पहला दिलचस्प एल्गोरिदम पढ़ाया जाता है: यह रुकता है, यह तेज़ है, और इसका सही होना एक ही समीकरण में दिख जाता है। यह मॉड्यूलर इनवर्स निकालने का भी मानक तरीक़ा है — उसका विस्तृत रूप इन्हीं चक्रों के साथ दो अतिरिक्त संख्याएँ ले चलता है — और वही क़दम RSA कुंजी बनाने के अंदर बैठा है। तीसरा इस्तेमाल गुणनखंडन पर एक नज़रिया जाँचना है। यह पता लगाना कि 1071 = 3 × 357 है और 462 = 2 × 3 × 7 × 11, काम है; यह पता लगाना कि उनका महत्तम समापवर्तक 21 है, तीन भाग हैं — इसलिए पहले यह पेज चलाने से पता चल जाता है कि शुरू करने से पहले छोटा करना आसान होने वाला है या नहीं। जब सिर्फ़ जवाब चाहिए और प्रक्रिया नहीं, तो gcf कैलकुलेटर वही सवाल छोटे रूप में पूछता है और दो से ज़्यादा संख्याएँ एक साथ सँभाल लेता है; lcm कैलकुलेटर इसी भाजक से लघुत्तम समापवर्त्य निकालता है, क्योंकि lcm = (a / gcd) * b; और शेषफल कैलकुलेटर बताता है कि ऋणात्मक संख्याओं के साथ एक अकेले शेषफल का क्या मतलब है — वह मामला इस पेज पर कभी आता ही नहीं।

1. किताबों वाली जोड़ी: 1071 और 462

   1. 462, 1071 में कितनी बार जाता है? दो बार, और 2 × 462 = 924, इसलिए 1071 − 924 = 147 बचता है
   2. अब जोड़ी 462 और 147 है: 147, 462 में तीन बार जाता है, 3 × 147 = 441, इसलिए 21 बचता है
   3. अब जोड़ी 147 और 21 है: 21, 147 में ठीक सात बार जाता है, कुछ नहीं बचता
   4. शेषफल शून्य है, इसलिए एल्गोरिदम रुक जाता है और जवाब 21 है

   यही डिफ़ॉल्ट इनपुट है, और वही हल किया हुआ उदाहरण जिसके साथ यह एल्गोरिदम आम तौर पर पढ़ाया जाता है। नतीजे पर दो जाँचें करना काम का है। दोनों संख्याओं को 21 से भाग दीजिए तो 51 और 22 मिलते हैं, जिनमें कोई साझा गुणनखंड नहीं है — और यही 21 को सिर्फ़ एक सामान्य भाजक नहीं, महत्तम बनाता है। और यह भी देखिए कि यहाँ कहीं गुणनखंडन हुआ ही नहीं: किसी को 1071 के गुणनखंड परीक्षण-भाग से ढूँढ़ने हों तो 32 तक जाना पड़े, जबकि एल्गोरिदम ने हर बार किसी संख्या को उसी संख्या से भाग दिया जो उसके पास पहले से थी। तीन चक्र, और हर चक्र पिछले से सस्ता।

2. एक ही चक्र काफ़ी है: 12 और 60

   1. जोड़ी को घटते क्रम में लगाइए: पहले 60, फिर 12
   2. 60 = 5 × 12 + 0, यानी 12, 60 को ठीक-ठीक बाँट देता है
   3. शेषफल तुरंत शून्य हो गया, इसलिए एल्गोरिदम एक ही चक्र में रुक जाता है
   4. जवाब 12 है — दोनों में से छोटी संख्या, क्योंकि वह बड़ी को बाँट देती है

   सबसे छोटा ग़ैर-तुच्छ चक्र, और वह मामला जो दिखाता है कि आख़िरी चक्र छोड़े जाने के बजाय क्यों छापा जाता है। 60 = 5 * 12 + 0 पंक्ति ही पूरा जवाब है: वह कहती है कि शेषफल शून्य पर पहुँच गया, और यह इस एल्गोरिदम के रुकने का अकेला रास्ता है। वह पंक्ति हटा दीजिए और चरण ख़ाली रह जाएँगे — और पाठक के पास यह जानने का कोई तरीक़ा नहीं बचेगा कि यह एक-चक्र का जवाब है या पेज चला ही नहीं। जब भी कोई संख्या दूसरी को ठीक-ठीक बाँटती है, महत्तम समापवर्तक सीधे उनमें से छोटी संख्या होती है।

3. सहअभाज्य संख्याएँ: 9 और 20

   1. 20 = 2 × 9 + 2, इसलिए जोड़ी 9 और 2 बन जाती है
   2. 9 = 4 × 2 + 1, इसलिए जोड़ी 2 और 1 बन जाती है
   3. 2 = 2 × 1 + 0, इसलिए एल्गोरिदम रुक जाता है
   4. जवाब 1 है, यानी 9 और 20 में 1 से बड़ा कोई साझा गुणनखंड नहीं है

   1 आना असली जवाब है, नाकामी नहीं, और उसका नाम भी है: ऐसी संख्याएँ सहअभाज्य होती हैं। यह यह भी बताता है कि भिन्न 9/20 पहले से न्यूनतम रूप में है, इसलिए छोटा करने की कोई गुंजाइश नहीं। ध्यान दीजिए कि चक्र ढहा नहीं — एल्गोरिदम तीन क़दमों में उतरकर 1 तक गया, क्योंकि कोई भी संख्या दूसरी को ठीक-ठीक नहीं बाँटती। जैसे-जैसे संख्याएँ बड़ी होती हैं, सहअभाज्य जोड़ियाँ आम मामला बन जाती हैं: दो संख्याओं का कोई साझा गुणनखंड होने की संभावना तेज़ी से गिरती है, और यही बात इस विधि को क्रिप्टोग्राफ़ी में मॉड्यूलर इनवर्स बनाने के लिए काम की बनाती है।

दोनों संख्याएँ पूर्ण होनी चाहिए, और दोनों 1 से 1000000 के बीच होनी चाहिए। शून्य कोई ख़ास मामला मानकर सँभाला नहीं जाता, ठुकरा दिया जाता है। a और 0 का महत्तम समापवर्तक a होता है, जो बिलकुल ठीक जवाब है, पर यह पेज उसे दिखा नहीं सकता: पहला चक्र a = q * 0 + r बनेगा, और वह q कहीं मौजूद ही नहीं है। बीच में छेद छोड़कर कोई प्रक्रिया छापने के बजाय पेज वह इनपुट लेने से इनकार कर देता है। ऋणात्मक संख्याएँ भी इसी वजह से ठुकरा दी जाती हैं — जिस रूप में चरण छपते हैं वह मान लेता है कि दोनों संख्याएँ कम से कम 1 हैं, और ऋणात्मक ऑपरेंड के लिए भागफल और शेषफल का मतलब तय करने वाला एक नियम चाहिए जो यह पेज कहीं नहीं लिखता। 1000000 की छत एल्गोरिदम के बारे में नहीं है, वह इससे कहीं बड़ी संख्याओं पर ख़ुशी-ख़ुशी चलेगा; वह इसलिए है कि रास्ते में हुआ हर घटाव, गुणा और शेषफल साधारण दोहरी-परिशुद्धता वाले अंकगणित में ठीक-ठीक रहे, और छपे हुए चरण इतने लंबे न हो जाएँ कि पढ़े ही न जाएँ। दो काफ़ी छोटी संख्याएँ फिर भी बहुत चक्र ले सकती हैं — 610 और 377 तेरह लेती हैं — पर व्यवहार में गिनती छत से बँधी रहती है, और संदर्भ तालिका में चक्रों की एक कॉलम इसीलिए है कि आप उसे बदलते हुए देख सकें। चरण समीकरणों के रूप में छपते हैं — a = q * b + r, अर्धविराम से जुड़े हुए — लंबी भाग विधि के रूप में नहीं, इसलिए अगर आप वह परिचित भाग का कोष्ठक ढूँढ़ रहे हैं तो यह पेज वह नहीं देगा। दोनों इनपुट आपस में बदले जा सकते हैं: पेज शुरू करने से पहले उन्हें घटते क्रम में लगा देता है, इसलिए आप इस पेज से यह नहीं देख सकते कि 3 = 0 * 5 + 3 कैसा लगता है — वह चक्र बनता ही नहीं। अगर आपकी संख्याएँ ऋणात्मक हो सकती हैं, या शेषफल की परिपाटी खुलकर लिखी हुई चाहिए, तो वह सवाल शेषफल कैलकुलेटर का है।

महत्तम समापवर्तक एक वाक्य में क्या है?

वह सबसे बड़ी पूर्ण संख्या जो दोनों संख्याओं को ठीक-ठीक बाँट दे, कुछ बचे बिना। 1071 और 462 के लिए वह 21 है: 1071 = 21 × 51 और 462 = 21 × 22, और 51 तथा 22 में कोई साझा गुणनखंड नहीं है, और यही 21 को महत्तम बनाता है। ध्यान दीजिए कि 3 और 7 भी दोनों संख्याओं को बाँटते हैं — वे सामान्य भाजक हैं, बस महत्तम नहीं। पेज का मुख्य परिणाम हमेशा यही संख्या होती है, और उसके नीचे के चरण उसका सबूत हैं।

आख़िरी चक्र हमेशा + 0 पर ही क्यों ख़त्म होता है?

क्योंकि शून्य शेषफल ही वह अकेली चीज़ है जो एल्गोरिदम को रोकती है। चक्र जोड़ी को उसके छोटे रूप से बदलता जाता है — दूसरी संख्या और शेषफल — और संख्याएँ हर चक्र गिरती हैं, इसलिए एक समय शून्य तक पहुँचना तय है। 147 = 7 * 21 + 0 वह चक्र है जहाँ यह होता है, और महत्तम समापवर्तक उसी चक्र का भाजक है, 21। पेज उसे छिपाने के बजाय छापता है, क्योंकि आख़िरी ग़ैर-शून्य शेषफल पर रुकी हुई चरण-सूची पाठक पर यह छोड़ देती कि वह ख़ुद समझे कि खोज ख़त्म हो चुकी है।

दोनों संख्याएँ किस क्रम में टाइप करता हूँ, इससे कुछ फ़र्क़ पड़ता है?

नहीं। पेज पहले चक्र से पहले उन्हें घटते क्रम में लगा देता है, इसलिए 462 और 1071 ठीक वही तीन पंक्तियाँ छापते हैं जो 1071 और 462। यह एक चुनाव है, एल्गोरिदम का गुण नहीं — नियम gcd(a, b) = gcd(b, a) का मतलब है कि किसी भी क्रम में जवाब सही आता है — पर बिना छँटाई के, 3 और 5 की जोड़ी की पहली पंक्ति 3 = 0 * 5 + 3 पढ़ती, जो वैध भाग है पर लगता है जैसे छोटी संख्या को बड़ी से भाग देना भी इस विधि का हिस्सा हो। इसी वजह से इनपुट फ़ील्ड के नाम पहली संख्या और दूसरी संख्या हैं, भाज्य और भाजक नहीं: वे दोनों भूमिकाएँ हर चक्र में बदल जाती हैं।

जवाब 1 आने का क्या मतलब है?

कि दोनों संख्याओं में 1 से बड़ा कोई साझा गुणनखंड नहीं है, और यह पूरा जवाब है, कोई नाकामी नहीं। ऐसी संख्याओं को सहअभाज्य कहते हैं, और इस पेज की 9 और 20 की जोड़ी उसका एक उदाहरण है। यह एक काम की बात भी बताता है: भिन्न 9/20 पहले से न्यूनतम रूप में है, इसलिए छोटा करने की कोई गुंजाइश नहीं। जैसे-जैसे संख्याएँ बड़ी होती हैं, सहअभाज्य जोड़ियाँ आम मामला बन जाती हैं, और इसीलिए यह विधि क्रिप्टोग्राफ़ी में मायने रखती है — RSA कुंजी बनाने का मतलब है ऐसी संख्याएँ ढूँढ़ना जिनका किसी दी हुई संख्या से कोई साझा गुणनखंड न हो।

क्या बड़ी संख्याओं में हमेशा ज़्यादा चक्र लगेंगे?

नहीं, और संदर्भ तालिका इसी को ठोस बनाने के लिए है। 1000000 और 999998 दो चक्रों में निपट जाती हैं, जबकि 610 और 377 — तीन-तीन अंकों की — तेरह लेती हैं। बहुत चक्रों के लिए मजबूर करने वाली चीज़ आकार नहीं, यह है कि संख्याएँ कितनी धीरे सिकुड़ती हैं, और सबसे धीरे सिकुड़ने वाली जोड़ियाँ लगातार फ़िबोनाची संख्याएँ होती हैं, जहाँ हर शेषफल भाजक के क़रीब होता है। यही नतीजा लामे प्रमेय है, और यह चक्रों की गिनती पर ऐसी छत लगाता है जो सिर्फ़ अंकों की संख्या के साथ बढ़ती है — इसीलिए इस एल्गोरिदम को तेज़ माना जाता है।

यह दोनों संख्याओं का गुणनखंड कर लेने से अलग कैसे है?

गुणनखंड करना कहीं ज़्यादा काम है, और वह काम यह पेज कभी नहीं करता। 1071 के गुणनखंड परीक्षण-भाग से ढूँढ़ने के लिए उसके वर्गमूल तक के भाजक आज़माने पड़ते, यानी क़रीब 32 तक; एल्गोरिदम इसके बजाय किसी संख्या को उसी संख्या से भाग देता है जो उसके पास पहले से है, और तीन चक्रों में निपट जाता है। इतनी छोटी संख्याओं पर फ़र्क़ दिखता नहीं, पर संख्याएँ बढ़ने के साथ गुणनखंडन बहुत तेज़ी से कठिन होता जाता है जबकि यूक्लिड एल्गोरिदम को फ़र्क़ ही नहीं पड़ता। यही खाई इसके पढ़ाए जाने की पूरी वजह है — और इसीलिए ऊपर का जवाब दूसरी गणना से नहीं, चक्र के भीतर से निकलता है: दोनों चलाने पर यह जोखिम बनता है कि छपे हुए चरण उनके ऊपर छपी संख्या से सहमत न हों।

• Euclidean Algorithm — the recurrence gcd(a, b) = gcd(b, a mod b), the proof that it terminates, and the connection to continued fractions — Wolfram MathWorld (United States)
• Greatest Common Divisor — what the greatest common factor is, and why gcd(a, 0) = a is the base case the algorithm stops on — Wolfram MathWorld (United States)
• Lamé's Theorem — the result that the pair taking the most rounds for its size is always a pair of consecutive Fibonacci numbers — Wolfram MathWorld (United States)