गणना दर्ज करें

सूत्र (फॉर्मूला)

Show calculation steps (1)

LCM (from GCD)

LCM is derived as the product of a and b divided by their GCD.

परिणाम

महत्तम समापवर्तक

gcd(48, 36)

GCD	12
LCM	144

यूक्लिड एल्गोरिदम क्या है?

यूक्लिड एल्गोरिदम गणित के सबसे पुराने ज्ञात एल्गोरिदम में से एक है, जिसका वर्णन यूनानी गणितज्ञ यूक्लिड ने लगभग 300 ईसा पूर्व किया था। यह दो पूर्ण संख्याओं का महत्तम समापवर्तक (GCD) निकालता है — यानी वह सबसे बड़ी संख्या जो दोनों को बिना कोई शेषफल छोड़े पूरी तरह विभाजित कर दे। यह कैलकुलेटर किसी भी दो ऋणेतर (non-negative) पूर्णांकों पर इस एल्गोरिदम को लागू करता है और साथ ही उनका लघुत्तम समापवर्त्य (LCM) भी बताता है।

इसका उपयोग कैसे करें

अपनी दोनों संख्याएं a और b वाले खानों में दर्ज करें और सबमिट करें। कैलकुलेटर मुख्य परिणाम के रूप में GCD और द्वितीयक मान के रूप में LCM दिखाता है। संख्याओं का क्रम मायने नहीं रखता — $\gcd(48, 36)$ और $\gcd(36, 48)$ बराबर ही होते हैं। ऋणात्मक मानों को उनके निरपेक्ष मान (absolute value) के अनुसार लिया जाता है, और यदि कोई एक संख्या 0 हो तो GCD बस दूसरी संख्या ही होती है।

सूत्र की व्याख्या

यह एल्गोरिदम एक सरल अंतर्दृष्टि पर आधारित है: a और b का कोई भी सार्व विभाजक उनके शेषफल a mod b को भी विभाजित करता है। इसलिए हम बार-बार बड़ी संख्या को शेषफल से बदलते जाते हैं:

$$\gcd(a,b) = \gcd(b,\, a \bmod b), \quad \gcd(a,0) = a$$

हर चरण में संख्याएं तेज़ी से घटती हैं, इसलिए बहुत बड़ी संख्याएं भी कुछ ही दोहरावों में हल हो जाती हैं। इसके बाद LCM की गणना $$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$$ से की जाती है।

विभाजन चरणों की शृंखला जो दो संख्याओं को उनके म.स.प. तक घटाती है — हर चरण $(a, b)$ को $(b, a \bmod b)$ से बदलता है जब तक शेषफल शून्य न हो जाए।

हल किया हुआ उदाहरण

$\gcd(48, 36)$ निकालिए:

$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = 12$$

तो GCD हुआ 12, और $$\text{LCM} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$

वर्गों में बँटा आयत जो म.स.प. को सबसे बड़े टाइलिंग वर्ग के रूप में दर्शाता है — ज्यामितीय रूप से, म.स.प. उस सबसे बड़े वर्ग की भुजा है जो $a \times b$ आयत को भरता है।

अक्सर पूछे जाने वाले प्रश्न

अगर दोनों संख्याएं 0 हों तो क्या होगा? यहां 0 और 0 का GCD 0 माना गया है, और LCM भी 0 है क्योंकि कोई धनात्मक गुणज मौजूद नहीं होता।

यह गुणनखंड सूचीबद्ध करने से तेज़ क्यों है? हर विभाजक ढूंढने के बजाय यह एल्गोरिदम शेषफल वाली युक्ति का उपयोग करता है, जो हर चरण में समस्या का आकार नाटकीय रूप से घटा देता है — आमतौर पर लघुगणकीय (logarithmic) समय में।

क्या यह बहुत बड़ी संख्याएं संभाल सकता है? हां। यूक्लिड एल्गोरिदम कई अंकों वाली संख्याओं के लिए भी कुशल है और इसे केवल थोड़े से modulo संक्रियाओं की ज़रूरत पड़ती है।

संबंधित कैलकुलेटर