महत्तम समापवर्त्य (GCD)

दो या अधिक पूर्णांकों का महत्तम समापवर्त्य (GCD) वह सबसे बड़ा धनात्मक पूर्णांक होता है जो प्रत्येक पूर्णांक को बिना किसी शेष के विभाजित करता है। इसे उच्चतम समापवर्त्य (HCF) भी कहा जाता है।

GCD ज्ञात करना

दो या अधिक पूर्णांकों का GCD ज्ञात करने के कई तरीके हैं। एक सामान्य तरीका यूक्लिडियन एल्गोरिद्म है, जो इस प्रकार कार्य करता है:

1. बड़े पूर्णांक को छोटे पूर्णांक से विभाजित करें।
2. शेष को लें और पिछले विभाजक को इस शेष से विभाजित करें।
3. चरण 1 और 2 को तब तक दोहराएं जब तक शेष 0 न हो जाए।
4. अंतिम गैर-शून्य शेष दो पूर्णांकों का GCD होता है।

उदाहरण के लिए, 12 और 18 का GCD ज्ञात करने के लिए हम इन चरणों का पालन करेंगे:

1. 18 ÷ 12 = 1 शेष 6
2. 12 ÷ 6 = 2 शेष 0

अंतिम गैर-शून्य शेष 6 है, इसलिए 12 और 18 का GCD 6 है।

GCD के गुण

GCD के कई महत्वपूर्ण गुण हैं, जिनमें शामिल हैं:

• दो पूर्णांकों का GCD हमेशा एक धनात्मक पूर्णांक होता है।
• दो पूर्णांकों का GCD उनके निरपेक्ष मानों के GCD के समान होता है।
• दो पूर्णांकों का GCD उनके सामान्य अभाज्य गुणनफलों के गुणनफल के बराबर होता है।
• दो पूर्णांकों का GCD उनके लघुत्तम समापवर्त्य (LCM) का एक समापवर्त्य होता है।

महत्तम समापवर्त्य ज्ञात करने के चरण

दो या अधिक पूर्णांकों का महत्तम समापवर्त्य (GCD) वह सबसे बड़ा धनात्मक पूर्णांक होता है जो प्रत्येक पूर्णांक को बिना किसी शेष के विभाजित करता है। इसे उच्चतम समापवर्त्य (HCF) भी कहा जाता है।

दो या अधिक पूर्णांकों का GCD खोजने के कई तरीके हैं। सबसे सामान्य तरीकों में से एक यूक्लिडियन एल्गोरिद्म है।

यूक्लिडियन एल्गोरिद्म

यूक्लिडियन एल्गोरिद्म दो पूर्णांकों का GCD खोजने का एक सरल और कुशल तरीका है। यह निम्न सिद्धांत पर आधारित है:

यदि $a$ और $b$ दो धनात्मक पूर्णांक हैं, तो $a$ और $b$ का GCD, $b$ और उस शेषफल का GCD है जब $a$ को $b$ से विभाजित किया जाता है।

दूसरे शब्दों में, हम दो पूर्णांकों का GCD बार-बार बड़े पूर्णांक को छोटे पूर्णांक से विभाजित कर शेषफल लेकर खोज सकते हैं। अंतिम गैर-शून्य शेषफल ही GCD होता है।

यहाँ दो पूर्णांकों का GCD यूक्लिडियन एल्गोरिद्म से खोजने के चरण दिए गए हैं:

1. मान लीजिए $a$ और $b$ दो पूर्णांक हैं।
2. यदि $b = 0$, तो $a$ और $b$ का GCD $a$ है।
3. अन्यथा, मान लीजिए $r$ वह शेषफल है जब $a$ को $b$ से विभाजित किया जाता है।
4. $a$ को $b$ से और $b$ को $r$ से प्रतिस्थापित करें।
5. चरण 2 से 4 तब तक दोहराएँ जब तक $b = 0$ न हो जाए।
6. $b$ का अंतिम गैर-शून्य मान ही $a$ और $b$ का GCD है।

उदाहरण

आइए यूक्लिडियन एल्गोरिद्म का उपयोग करके 12 और 18 का GCD खोजें।

1. मान लीजिए $a = 12$ और $b = 18$।
2. चूँकि $b \neq 0$, हम चरण 3 पर जाते हैं।
3. जब 12 को 18 से विभाजित किया जाता है तो शेषफल 6 आता है।
4. $a$ को $b$ से और $b$ को $r$ से प्रतिस्थापित करें। इसलिए, $a = 18$ और $b = 6$।
5. चरण 2 से 4 दोहराएँ।
6. $b$ का अंतिम गैर-शून्य मान 6 है। इसलिए, 12 और 18 का GCD 6 है।

यूक्लिडियन एल्गोरिद्म दो या अधिक पूर्णांकों का GCD खोजने के लिए एक सरल और कुशल विधि है। यह सिद्धांत पर आधारित है कि दो पूर्णांकों का GCD उसी प्रकार का होता है जैसे बड़े पूर्णांक और छोटे पूर्णांक से बड़े पूर्णांक को विभाजित करने पर आने वाले शेषफल का GCD होता है।

GCD (ग्रेटेस्ट कॉमन डिवाइज़र) खोजने की विधियाँ

दो या अधिक पूर्णांकों का महत्तम समापवर्त्य (GCD) सबसे बड़ा धनात्मक पूर्णांक होता है जो प्रत्येक पूर्णांक को बिना शेष दिए विभाजित करता है। GCD खोजना संख्या सिद्धांत में एक मौलिक संक्रिया है और इसका गणित और कंप्यूटर विज्ञान में विभिन्न अनुप्रयोग हैं। यहाँ GCD खोजने के लिए कुछ सामान्यतः प्रयुक्त तरीके दिए गए हैं:

1. यूक्लिडियन एल्गोरिद्म:

यूक्लिडियन एल्गोरिद्म दो पूर्णांकों का GCD खोजने के लिए एक कुशल विधि है। यह सिद्धांत पर आधारित है कि दो पूर्णांकों का GCD उनके शेषफल का GCD होता है जब बड़े पूर्णांक को छोटे पूर्णांक से विभाजित किया जाता है। एल्गोरिद्म इस प्रकार कार्य करता है:

• मान लीजिए $a$ और $b$ वे दो पूर्णांक हैं जिनका GCD हम खोजना चाहते हैं।
• यदि $b = 0$, तो GCD $a$ है।
• अन्यथा, जब $a$ को $b$ से विभाजित किया जाता है तो शेषफल $r$ निकालें।
• $a$ को $b$ से और $b$ को $r$ से प्रतिस्थापित करें।
• चरण 2 और 3 को तब तक दोहराएँ जब तक $b = 0$ न हो।
• $b$ का अंतिम अशून्य मान $a$ और $b$ का GCD होता है।

उदाहरण के लिए, 12 और 18 का GCD यूक्लिडियन एल्गोरिद्म से खोजने के लिए:

• $18 = 12 \times 1 + 6$
• $12 = 6 \times 2 + 0$
• अंतिम अशून्य शेषफल 6 है, इसलिए 12 और 18 का GCD 6 है।

2. अभाज्य गुणनफल विधि:

अभाज्य गुणनफल विधि में दो पूर्णांकों को उनके अभाज्य गुणनफलों के रूप में व्यक्त किया जाता है और फिर उभयनिष्ठ अभाज्य गुणनफलों की पहचान की जाती है। GCD उभयनिष्ठ अभाज्य गुणनफलों का गुणनफल होता है।

उदाहरण के लिए, अभाज्य गुणनफल विधि का उपयोग करके 12 और 18 का GCD ज्ञात करने के लिए:

• $12 = 2^2 \times 3$
• $18 = 2 \times 3^2$
• उभयनिष्ठ अभाज्य गुणनफल 3 है, इसलिए 12 और 18 का GCD 3 है।

3. बाइनरी GCD एल्गोरिद्म:

बाइनरी GCD एल्गोरिद्म दो पूर्णांकों का GCD ज्ञात करने के लिए एक तेज़ और कुशल विधि है। यह सिद्धांत पर आधारित है कि दो पूर्णांकों का GCD उन पूर्णांकों के रैखिक संयोजन के रूप में व्यक्त किया जा सकता है। यह एल्गोरिद्म पूर्णांकों को बार-बार आधा करता है और रैखिक संयोजन को अद्यतन करता है जब तक कि एक पूर्णांक 0 न हो जाए।

उदाहरण के लिए, बाइनरी GCD एल्गोरिद्म का उपयोग करके 12 और 18 का GCD ज्ञात करने के लिए:

• $12 = 2^2 \times 3$
• $18 = 2 \times 3^2$
• उभयनिष्ठ अभाज्य गुणनफल 3 है, इसलिए 12 और 18 का GCD 3 है।

यूक्लिड एल्गोरिद्म, अभाज्य गुणनफल विधि और बाइनरी GCD एल्गोरिद्म दो या अधिक पूर्णांकों का महत्तम समापवर्तक (GCD) ज्ञात करने के लिए प्रयोग में आने वाली तीन सामान्य विधियाँ हैं। प्रत्येक विधि की अपनी विशिष्ट परिस्थितियों और शामिल पूर्णांकों के आकार के आधार पर अपनी-अपनी विशेषताएँ और अनुप्रयोग होते हैं।

महत्तम समापवर्तक के हल किए गए उदाहरण

दो या अधिक पूर्णांकों का महत्तम समापवर्तक (GCD) सबसे बड़ा धनात्मक पूर्णांक होता है जो प्रत्येक पूर्णांक को बिना किसी शेषफल के विभाजित करता है।

उदाहरण 1: 12 और 18 का GCD ज्ञात कीजिए।

हल:

1. 12 के गुणनफलों की सूची बनाइए: 1, 2, 3, 4, 6, 12
2. 18 के गुणनफलों की सूची बनाइए: 1, 2, 3, 6, 9, 18
3. 12 और 18 के उभयनिष्ठ गुणनफल 1, 2, 3 और 6 हैं।
4. 12 और 18 का महत्तम उभयनिष्ठ गुणनफल 6 है।

उदाहरण 2: 24, 36 और 48 का GCD ज्ञात कीजिए।

हल:

1. 24 के गुणनफलों की सूची बनाइए: 1, 2, 3, 4, 6, 8, 12, 24
2. 36 के गुणनफलों की सूची बनाइए: 1, 2, 3, 4, 6, 9, 12, 18, 36
3. 48 के गुणनफलों की सूची बनाइए: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
4. 24, 36 और 48 के उभयनिष्ठ गुणनफल 1, 2, 3, 4, 6 और 12 हैं।
5. 24, 36 और 48 का महत्तम उभयनिष्ठ गुणनफल 12 है।

उदाहरण 3: 1071 और 462 का GCD ज्ञात कीजिए।

हल:

1. यूक्लिडियन एल्गोरिद्म का प्रयोग कीजिए:

• 1071 को 462 से विभाजित कीजिए: 1071 ÷ 462 = 2 शेष 147
• 462 को 147 से विभाजित कीजिए: 462 ÷ 147 = 3 शेष 27
• 147 को 27 से विभाजित कीजिए: 147 ÷ 27 = 5 शेष 12
• 27 को 12 से विभाजित कीजिए: 27 ÷ 12 = 2 शेष 3
• 12 को 3 से विभाजित कीजिए: 12 ÷ 3 = 4 शेष 0

2. अंतिम अशून्य शेष 3 है।
3. इसलिए, 1071 और 462 का GCD 3 है।

GCD के अनुप्रयोग

GCD के गणित और कंप्यूटर विज्ञान में कई अनुप्रयोग हैं। कुछ अनुप्रयोग इस प्रकार हैं:

• दो या अधिक पूर्णांकों का लघुतम समापवर्त्य (LCM) ज्ञात करना
• भिन्नों को सरल करना
• डायोफैंटाइन समीकरणों को हल करना
• बहुपदों के समुच्चय का महत्तम समापवर्त्य ज्ञात करना
• क्रिप्टोग्राफी

महत्तम समापवर्त्य अक्सर पूछे जाने वाले प्रश्न

दो संख्याओं का महत्तम समापवर्त्य (GCD) क्या होता है?

दो संख्याओं का महत्तम समापवर्तक (GCD) वह सबसे बड़ा धनात्मक पूर्णांक होता है जो दोनों संख्याओं को बिना किसी शेष के विभाजित करता है।

आप दो संख्याओं का GCD कैसे खोजते हैं?

दो संख्याओं का GCD खोजने के कई तरीके हैं। एक सामान्य तरीका यूक्लिडियन एल्गोरिद्म है, जिसमें बड़ी संख्या को छोटी संख्या से बार-बार विभाजित करना और शेष लेना शामिल होता है। GCD अंतिम गैर-शून्य शेष होता है।

दो अभाज्य संख्याओं का GCD क्या होता है?

दो अभाज्य संख्याओं का GCD 1 होता है।

दो संख्याओं का GCD क्या होता है जिनमें एक उभयनिष्ठ गुणनफल हो?

यदि दो संख्याओं में एक उभयनिष्ठ गुणनफल हो, तो उनका GCD उस उभयनिष्ठ गुणनफल और उस उभयनिष्ठ गुणनफल से विभाजित संख्याओं के GCD के गुणनफल के बराबर होता है।

दो संख्याओं का GCD क्या होता है जो सह-अभाज्य हैं?

दो संख्याएँ सह-अभाज्य होती हैं यदि उनमें 1 के अलावा कोई उभयनिष्ठ गुणनफल न हो। सह-अभाज्य संख्याओं का GCD 1 होता है।

किसी संख्या और 0 का GCD क्या होता है?

किसी संख्या और 0 का GCD वह संख्या स्वयं होती है।

किसी संख्या और 1 का GCD क्या होता है?

किसी संख्या और 1 का GCD 1 होता है।

किसी संख्या और उसी संख्या का GCD क्या होता है?

किसी संख्या और उसी संख्या का GCD वह संख्या स्वयं होती है।

किसी संख्या और उसके ऋणात्मक का GCD क्या होता है?

किसी संख्या और उसके ऋणात्मक का GCD उस संख्या का निरपेक्ष मान होता है।

किसी संख्या और उसके व्युत्क्रम का GCD क्या होता है?

किसी संख्या और उसके व्युत्क्रम का GCD 1 होता है।