लेखक:
Joan Hall
निर्माण की तारीख:
1 फ़रवरी 2021
डेट अपडेट करें:
1 जुलाई 2024
![यूक्लिडियन एल्गोरिथम का उपयोग करके सबसे बड़ा सामान्य भाजक कैसे खोजें](https://i.ytimg.com/vi/JUzYl1TYMcU/hqdefault.jpg)
विषय
दो पूर्णांकों का सबसे बड़ा सामान्य भाजक (GCD) सबसे बड़ा पूर्णांक होता है जो उनमें से प्रत्येक संख्या को विभाजित करता है। उदाहरण के लिए, 20 और 16 के लिए gcd 4 है (16 और 20 दोनों में बड़े भाजक हैं, लेकिन वे सामान्य नहीं हैं - उदाहरण के लिए, 8 16 का भाजक है, लेकिन 20 का भाजक नहीं है)। जीसीडी खोजने के लिए एक सरल और व्यवस्थित विधि है, जिसे "यूक्लिड का एल्गोरिथम" कहा जाता है। यह लेख आपको दिखाएगा कि दो पूर्णांकों का सबसे बड़ा सामान्य भाजक कैसे खोजा जाए।
कदम
विधि 1 में से 2: विभक्त एल्गोरिथम
1 किसी भी ऋण चिह्न को छोड़ दें।
2 शब्दावली सीखें: 32 को 5 से भाग देने पर,
- 32 - लाभांश
- 5 - भाजक
- 6 - निजी
- 2 - शेष
3 बड़ी संख्या ज्ञात कीजिए। यह विभाज्य होगा, और छोटी संख्या भाजक होगी।
4 निम्नलिखित एल्गोरिथम लिखिए: (लाभांश) = (भाजक) * (भागफल) + (शेष)
5 भाज्य के स्थान पर बड़ी संख्या और भाजक के स्थान पर छोटी संख्या लगाइए।
6 ज्ञात कीजिए कि बड़ी संख्या को छोटी संख्या से कितनी बार विभाजित किया जाता है, और भागफल के स्थान पर परिणाम लिखें।
7 शेष का पता लगाएं और इसे एल्गोरिथम में उपयुक्त स्थिति में लिखें।
8 एल्गोरिथ्म को फिर से लिखें, लेकिन (ए) पिछले भाजक को नए लाभांश के रूप में लिखें, और (बी) पिछले शेष को नए भाजक के रूप में लिखें।
9 पिछले चरण को तब तक दोहराएं जब तक कि शेष 0 न हो जाए।
10 अंतिम भाजक सबसे बड़ा सामान्य भाजक (GCD) होगा।
11 उदाहरण के लिए, आइए 108 और 30 के लिए GCD खोजें:
12 ध्यान दें कि पहली पंक्ति से संख्याएँ 30 और 18 कैसे दूसरी पंक्ति बनाती हैं। फिर 18 और 12 तीसरी पंक्ति बनाते हैं, और 12 और 6 चौथी पंक्ति बनाते हैं। 3, 1, 1, और 2 के गुणजों का उपयोग नहीं किया जाता है। वे भाजक द्वारा विभाज्य होने की संख्या का प्रतिनिधित्व करते हैं और इसलिए प्रत्येक पंक्ति के लिए अद्वितीय हैं।
विधि २ का २: प्रधान कारक
1 किसी भी ऋण चिह्न को छोड़ दें।
2 संख्याओं के अभाज्य गुणनखंड ज्ञात कीजिए। उन्हें चित्र में दिखाए अनुसार प्रस्तुत करें।
- उदाहरण के लिए, 24 और 18 के लिए:
- 24- 2 x 2 x 2 x 3
- 18- 2 x 3 x 3
- उदाहरण के लिए, 50 और 35 के लिए:
- 50- 2 x 5 x 5
- 35- 5 x 7
- उदाहरण के लिए, 24 और 18 के लिए:
3 सामान्य अभाज्य गुणनखंड ज्ञात कीजिए।
- उदाहरण के लिए, 24 और 18 के लिए:
- 24- 2 एक्स 2 एक्स 2 एक्स 3
- 18- 2 एक्स 3 एक्स 3
- उदाहरण के लिए, 50 और 35 के लिए:
- 50 - 2 x 5 एक्स 5
- 35- 5 एक्स 7
- उदाहरण के लिए, 24 और 18 के लिए:
4 सामान्य अभाज्य गुणनखंडों को गुणा करें।
- 24 और 18 के लिए, गुणा करें 2 तथा 3 और पाओ 6... 6 24 और 18 का सबसे बड़ा सामान्य भाजक है।
- 50 और 35 के लिए गुणा करने के लिए कुछ भी नहीं है। 5 एकमात्र सामान्य अभाज्य कारक है, और यह GCD है।
5 बनाया गया!
टिप्स
- इसे लिखने का एक तरीका है: लाभांश> आधुनिक विभक्त> = शेष; जीसीडी (ए, बी) = बी अगर मॉड बी = 0, और जीसीडी (ए, बी) = जीसीडी (बी, एक मॉड बी) अन्यथा।
- एक उदाहरण के रूप में, आइए GCD (-77.91) को खोजें। सबसे पहले, -77 के बजाय 77 का उपयोग करें: GCD (-77.91) GCD (77.91) में परिवर्तित होता है। 77 91 से कम है, इसलिए हमें उन्हें स्वैप करना होगा, लेकिन विचार करें कि अगर हम नहीं करते हैं तो एल्गोरिदम कैसे काम करता है। 77 मॉड 91 की गणना करते समय, हमें 77 (77 = 91 x 0 + 77) मिलता है। चूंकि यह शून्य नहीं है, हम स्थिति (बी, ए मॉड बी) पर विचार करते हैं, यानी जीसीडी (77.91) = जीसीडी (91.77)। ९१ मॉड ७७ = १४ (१४ शेष है)। यह शून्य नहीं है, इसलिए GCD (91.77) GCD (77.14) हो जाता है। 77 mod 14 = 7. यह शून्य नहीं है, इसलिए GCD (77.14) GCD (14.7) बन जाता है। १४ मॉड ७ = ० (चूंकि १४/७ = २ शेष के बिना)। उत्तर: जीसीडी (-७७.९१) = ७.
- वर्णित विधि भिन्नों को सरल बनाने के लिए बहुत उपयोगी है। ऊपर के उदाहरण में: -77/91 = -11/13, क्योंकि 7 -77 और 91 का सबसे बड़ा सामान्य भाजक है।
- यदि ए और बी शून्य के बराबर हैं, तो कोई भी गैर-शून्य संख्या उनका भाजक है, इसलिए इस मामले में कोई जीसीडी नहीं है (गणितज्ञ केवल यह मानते हैं कि 0 और 0 का सबसे बड़ा सामान्य भाजक 0 है)।