महत्तम सामान्य भाजक

गणित में, दो या अधिक पूर्णांक जो शून्य नहीं हैं सबसे बड़ा सामान्य भाजक (GCD), सबसे बड़ा धनात्मक पूर्णांक है जो प्रत्येक पूर्णांक को विभाजित करता है। दो पूर्णांक x , y के लिए, x और y का सबसे बड़ा सामान्य भाजक $\gcd(x,y)$ दर्शाया गया है। उदाहरण के लिए, 8 और 12 का GCD 4 है, यानी, $\gcd(8,12)=4$.

"सबसे बड़ा सामान्य भाजक" नाम में, विशेषण "महानतम" को "उच्चतम" और शब्द "विभाजक" को "कारक" द्वारा प्रतिस्थापित किया जा सकता है, ताकि अन्य नामों में उच्चतम सामान्य कारक (HCF), आदि शामिल हो। ऐतिहासिक रूप से, एक ही अवधारणा के लिए अन्य नामों में सबसे बड़ा सामान्य उपाय शामिल है।

इस धारणा को बहुपद (देखें बहुपद महानतम सामान्य भाजक) और अन्य कम्यूटेटिव रिंग्स तक बढ़ाया जा सकता है (नीचे § In commutative rings देखें)।

अवलोकन

परिभाषा

दो गैर-शून्य पूर्णांक a तथा b का सबसे बड़ा सामान्य भाजक (GCD) सबसे बड़ा धनात्मक पूर्णांक d है जिससे d, a तथा b दोनों का विभाजक है; अर्थात् पूर्णांक e तथा f है a = de तथा b = df, और d सबसे बड़ा पूर्णांक है। a तथा b को आम तौर पर gcd(a, b) के रूप में दर्शाया जाता है।

यह परिभाषा तब भी लागू होती है जब a तथा b में से कोई एक शून्य हो। इस मामले में, GCD गैर शून्य पूर्णांक का पूर्ण मान है: gcd(a, 0) = gcd(0, a) = |a|। यह विषय यूक्लिडियन एल्गोरिथ्म के अंतिम चरण के रूप में महत्वपूर्ण है।

उपरोक्त परिभाषा का उपयोग gcd(0, 0), को परिभाषित करने के लिए नहीं किया जा सकता है, क्योंकि 0 × n = 0, और शून्य का कोई सबसे बड़ा भाजक नहीं है। हालांकि, अगर सबसे बड़ा विभाजन संबंध के संदर्भ में समझा जाता है, तो शून्य अपना सबसे बड़ा विभाजक है इसलिए gcd(0, 0) को आमतौर पर 0 के रूप में परिभाषित किया जाता है। यह जीसीडी के लिए सामान्य पहचान को संरक्षित करता है, और विशेष रूप से बेज़आउट (Bézout ) की पहचान में, अर्थात् gcd(a, b) के रूप {a, b} बनाता है। इसका अनुसरण कई कंप्यूटर बीजगणित प्रणालियों द्वारा किया जाता है। बहरहाल, कुछ लेखक gcd(0, 0) को अपरिभाषित छोड़ देते हैं।

a तथा b का gcd विभाजन के पूर्वक्रम संबंध में उनका सबसे बड़ा सकारात्मक सामान्य भाजक है। इसका मतलब है कि a और b के सामान्य विभाजक वास्तव में अपने gcd के विभाजक हैं। यह आमतौर पर यूक्लिड के लेम्मा, अंकगणित के मौलिक प्रमेय या यूक्लिडियन एल्गोरिथ्म का उपयोग करके सिद्ध किया जाता है। gcd की अवधारणा के सामान्यीकरण के लिए उपयोग किया जाता है।

उदाहरण

संख्या 54 को कई अलग -अलग तरीकों से दो पूर्णांक के उत्पाद के रूप में व्यक्त किया जा सकता है:

$54\times 1=27\times 2=18\times 3=9\times 6.$

इस प्रकार 54 के विभाजकों की पूरी सूची है $1,2,3,6,9,18,27,54$। इसी तरह, 24 के विभाजक हैं $1,2,3,4,6,8,12,24$। इन दो सूचियों में सामान्य संख्या 54 और 24 के सामान्य विभाजक हैं, अर्थात्,

$1,2,3,6.$

इनमें से, सबसे महान 6 है, इसलिए यह सबसे बड़ा सामान्य भाजक है:

$\gcd(54,24)=6.$

इस तरह से दो नंबरों के सभी विभाजकों की गणना करना आमतौर पर कुशल नहीं होता है, विशेष रूप से बड़ी संख्या के लिए जिनमें कई विभाजक होते हैं। गणना में अधिक कुशल तरीकों का वर्णन किया गया है § Calculation।

सह अभाज्य संख्या

Main article: Coprime integers

दो संख्याओं को अपेक्षाकृत अभाज्य या सह अभाज्य कहा जाता है, यदि उनका सबसे बड़ा सामान्य विभाजक 1 के बराबर है। उदाहरण के लिए, 9 और 28 सहअभाज्य हैं।

एक ज्यामितीय दृश्य

एक 24-बाय -60 आयत दस 12-बाई -12 वर्ग टाइलों के साथ कवर किया गया है, जहां 12 24 और 60 का जीसीडी है। आम तौर पर, एक-बी-बी आयत को साइड लंबाई के वर्ग टाइलों के साथ कवर किया जा सकता है।केवल अगर C A और B का एक सामान्य भाजक है।

उदाहरण के लिए, एक 24-बाय (by) -60 आयताकार क्षेत्र को एक ग्रिड में विभाजित किया जा सकता है: 1-बाय -1 वर्ग, 2-बाय -2 वर्ग, 3-बाय -3 वर्ग, 4-बाय -4 वर्ग, 6-बाई-6 वर्ग या 12-बाय -12 वर्ग। इसलिए 12, 24 और 60 का सबसे बड़ा सामान्य विभाजक है। 24-बाय -60 आयताकार क्षेत्र को 12-12 वर्गों के ग्रिड में विभाजित किया जा सकता है, जिसमें एक छोर (24/12 = 2) के साथ दो चौकोर और अन्य (60/12 = 5) के साथ पांच वर्ग हैं।

अनुप्रयोग

भिन्नों को कम करना

Further information: Irreducible fraction

सबसे बड़ा सामान्य भाजक भिन्नों को निम्नतम पदों तक कम करने के लिए उपयोगी है। उदाहरण के लिए, gcd(42, 56) = 14, इसलिए,

${\frac {42}{56}}={\frac {3\cdot 14}{4\cdot 14}}={\frac {3}{4}}.$

लघुतम समापवर्त्य

Further information: Least common multiple

दो पूर्णांकों का लघुत्तम समापवर्त्य, जो दोनों शून्य नहीं हैं, उनके संबंध का उपयोग करके उनके सबसे बड़े सामान्य भाजक से गणना की जा सकती है

$\operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}.$

गणना

अभाज्य गुणनखंड का उपयोग करना

दो संख्याओं के अभाज्य गुणनखंडों और कारकों की तुलना करके सबसे बड़े सामान्य विभाजकों की गणना की जा सकती है। उदाहरण के लिए, gcd (48, 180) की गणना करने के लिए, हम अभाज्य गुणनखंड 48 = 24 · 31 और 180 = 22 · 32 · 51; GCD तब 2min (4,2) · 3min (1,2) · 5min (0,1) = 22 · 31 · 50 = 12 है, जैसा कि वेन आरेख में दिखाया गया है। संबंधित एलसीएम तब 2max(4,2) · 3max(1,2) · 5max(0,1) = 24 · 32 · 51 = 720 है।

[[File:least common multiple.svg|300px

अभ्यास में, यह विधि केवल छोटी संख्या के लिए संभव है, क्योंकि अभाज्य गुणनखंडों की गणना में बहुत अधिक समय लगता है।

यूक्लिड का एल्गोरिथम

Main article: Euclidean algorithm

सबसे बड़े सामान्य भाजक की गणना के लिए यूक्लिड द्वारा शुरू की गई विधि इस तथ्य पर आधारित है कि, दो धनात्मक पूर्णांक a तथा b इस तरह दिए गए हैं कि a > b, a तथा b के सामान्य भाजक वही हैं जो a – b तथा b के सामान्य भाजक हैं।

इसलिए, दो धनात्मक पूर्णांक के सबसे बड़े सामान्य भाजक की गणना करने के लिए यूक्लिड की विधि बड़ी संख्या को संख्याओं के अंतर से प्रतिस्थापित करने के लिए है, और दो संख्याओं के बराबर होने तक इसे दोहराते हैं: यह उनका सबसे बड़ा सामान्य विभाजक है।

उदाहरण के लिए, गणना करने के लिए gcd(48,18), एक निम्नानुसार आगे बढ़ता है:

${\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(48-18,18)=\gcd(30,18)&&\to \quad \gcd(30-18,18)=\gcd(12,18)\\&\to \quad \gcd(12,18-12)=\gcd(12,6)&&\to \quad \gcd(12-6,6)=\gcd(6,6).\end{aligned}}$

इसलिए gcd(48, 18) = 6।

यह विधि बहुत धीमी हो सकती है यदि एक संख्या दूसरे की तुलना में बहुत बड़ी हो। तो, जिस संस्करण का अनुसरण किया जाता है वह आमतौर पर पसंद किया जाता है।

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

Main article: Euclidean algorithm

एनीमेशन 62 और 36 के सबसे बड़े सामान्य भाजक को खोजने के लिए यूक्लिडियन एल्गोरिथ्म का एक अनुप्रयोग दिखा रहा है, जो 2 है।

एक अधिक कुशल विधि यूक्लिडियन एल्गोरिथ्म है, एक संस्करण जिसमें दो संख्याओं का अंतर है a तथा b यूक्लिडियन डिवीजन के शेष भाग द्वारा प्रतिस्थापित किया जाता है (जिसे शेष के साथ भी कहा जाता है) a द्वारा b।

इस शेष के रूप में निरूपित करना a mod b, एल्गोरिथ्म प्रतिस्थापित करता है (a, b) द्वारा (b, a mod b) बार -बार जब तक यह जोड़ी है (d, 0), कहाँ पे d सबसे बड़ा आम भाजक है।

उदाहरण के लिए, GCD (48,18) की गणना करने के लिए, गणना इस प्रकार है:

${\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(18,48{\bmod {1}}8)=\gcd(18,12)\\&\to \quad \gcd(12,18{\bmod {1}}2)=\gcd(12,6)\\&\to \quad \gcd(6,12{\bmod {6}})=\gcd(6,0).\end{aligned}}$

यह फिर से देता है gcd(48, 18) = 6।

लेहमर का जीसीडी एल्गोरिथ्म

Main article: Lehmer's GCD algorithm

लेहमर का एल्गोरिथ्म इस अवलोकन पर आधारित है कि यूक्लिड के एल्गोरिथ्म द्वारा उत्पादित प्रारंभिक उद्धरण केवल पहले कुछ अंकों के आधार पर निर्धारित किए जा सकते हैं; यह उन संख्याओं के लिए उपयोगी है जो कंप्यूटर शब्द से बड़े हैं। संक्षेप में, एक प्रारंभिक अंकों को निकालता है, आमतौर पर एक या दो कंप्यूटर शब्द बनाता है, और इन छोटी संख्याओं पर यूक्लिड के एल्गोरिदम को चलाता है, जब तक कि यह गारंटी दी जाती है कि उद्धरण उन लोगों के साथ समान हैं जो मूल संख्याओं के साथ प्राप्त किए जाएंगे। मूल संख्याओं को कम करने के लिए उद्धरणों को एक छोटे 2-बाय -2 परिवर्तन मैट्रिक्स (एकल-शब्द पूर्णांक का एक मैट्रिक्स) में एकत्र किया जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि संख्याएं छोटी न हों कि बाइनरी एल्गोरिथ्म (नीचे देखें) अधिक कुशल है।

यह एल्गोरिथ्म गति में सुधार करता है, क्योंकि यह बहुत बड़ी संख्या में संचालन की संख्या को कम करता है, और अधिकांश संचालन के लिए हार्डवेयर अंकगणित का उपयोग कर सकता है। वास्तव में, अधिकांश उद्धरण बहुत छोटे होते हैं, इसलिए यूक्लिडियन एल्गोरिथ्म के चरणों की एक उचित संख्या एकल-शब्द पूर्णांक के 2-बाई -2 मैट्रिक्स में एकत्र की जा सकती है। जब लेहमर के एल्गोरिथ्म एक भागफल का सामना करते हैं जो बहुत बड़ा है, तो इसे यूक्लिडियन एल्गोरिथ्म के एक पुनरावृत्ति पर वापस गिरना चाहिए, जिसमें बड़ी संख्या के यूक्लिडियन डिवीजन हैं।

बाइनरी जीसीडी एल्गोरिथ्म

Main article: Binary GCD algorithm

बाइनरी जीसीडी एल्गोरिथ्म केवल घटाव और विभाजन का उपयोग 2 से करता है। विधि निम्नानुसार है: ए और बी को दो गैर-नकारात्मक पूर्णांक होने दें।चलो पूर्णांक d 0. पाँच संभावनाएं हैं:

• ए = बी।

जीसीडी (ए, ए) = ए के रूप में, वांछित जीसीडी एक × 2 है^D (जैसा कि A और B को अन्य मामलों में बदल दिया जाता है, और D कई बार रिकॉर्ड करता है कि A और B दोनों को अगले चरण में 2 से विभाजित किया गया है, प्रारंभिक जोड़ी का GCD एक का उत्पाद हैऔर 2^d )।

• ए और बी दोनों भी हैं।

तब 2 एक सामान्य भाजक है। ए और बी दोनों को 2 से विभाजित करें, 1 से 1 से वृद्धि डी को रिकॉर्ड करने के लिए 2 बार एक सामान्य विभाजक है और जारी रखें।

• A सम है और B अजीब है।

तब 2 एक सामान्य भाजक नहीं है। ए को 2 से विभाजित करें और जारी रखें।

• A अजीब है और B भी है।

तब 2 एक सामान्य भाजक नहीं है। बी को 2 से विभाजित करें और जारी रखें।

• ए और बी दोनों विषम हैं।

GCD (a, b) = gcd (b, a) के रूप में, यदि a <b तो आदान -प्रदान a और b। संख्या C = A - B सकारात्मक और एक से छोटा है। कोई भी संख्या जो ए और बी को विभाजित करती है, उसे सी को भी विभाजित करना चाहिए, इसलिए ए और बी का प्रत्येक सामान्य विभाजक भी बी और सी का एक सामान्य भाजक है। इसी तरह, ए = बी + सी और बी और सी का प्रत्येक सामान्य भाजक भी ए और बी का एक सामान्य भाजक है। तो दो जोड़े (ए, बी) और (बी, सी) में एक ही सामान्य विभाजक हैं, और इस प्रकार जीसीडी (ए, बी) = जीसीडी (बी, सी)। इसके अलावा, जैसा कि ए और बी दोनों विषम हैं, सी भी है, प्रक्रिया को जीसीडी को बदलने के बिना छोटे नंबरों (सी/2, बी) द्वारा प्रतिस्थापित जोड़ी (ए, बी) के साथ जारी रखा जा सकता है।

उपरोक्त चरणों में से प्रत्येक को गैर-नकारात्मक छोड़ते समय ए और बी में से कम से कम एक को कम कर देता है और इसलिए केवल समय की एक परिमित संख्या को दोहराया जा सकता है। इस प्रकार अंततः प्रक्रिया में ए = बी, रोक के मामले में परिणाम होता है। फिर GCD एक × 2 है^D ।

उदाहरण: (ए, बी, डी) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → →(3, 3, 1);मूल GCD इस प्रकार 2 का उत्पाद 6 है^d = 2¹ और a = b = 3।

बाइनरी जीसीडी एल्गोरिथ्म विशेष रूप से बाइनरी कंप्यूटर पर लागू करना आसान है।इसकी कम्प्यूटेशनल जटिलता है

$O((\log a+\log b)^{2})$

कम्प्यूटेशनल जटिलता आमतौर पर लंबाई के संदर्भ में दी जाती है n इनपुट की।यहाँ, यह लंबाई है $n=\log a+\log b,$ और जटिलता इस प्रकार है

$O(n^{2})$।

अन्य तरीके

$\gcd(1,x)=y,$ या थोमा का कार्य।नीचे की ओर हैचिंग एलिप्स को इंगित करता है (यानी अत्यधिक उच्च घनत्व के कारण डॉट्स की चूक)।

यदि ए और बी दोनों नॉनज़ेरो हैं, तो ए और बी के सबसे बड़े सामान्य विभाजक को ए और एनबीएसपी के कम से कम सामान्य मल्टीपल (एलसीएम) का उपयोग करके गणना की जा सकती है;

$\gcd(a,b)={\frac {|a\cdot b|}{\operatorname {lcm} (a,b)}}$,

लेकिन अधिक सामान्यतः LCM की गणना GCD से की जाती है।

थोमा के फ़ंक्शन f का उपयोग करना,

$\gcd(a,b)=af\left({\frac {b}{a}}\right),$

जो ए और बी तर्कसंगत संख्याओं या सराहनीय वास्तविक संख्याओं को सामान्य करता है।

कीथ स्लाविन ने दिखाया है कि विषम a & nbsp; and & nbsp; 1 के लिए:

$\gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})$

जो एक फ़ंक्शन है जिसका मूल्यांकन जटिल b के लिए किया जा सकता है। वोल्फगैंग श्रेम ने दिखाया है कि

$\gcd(a,b)=\sum \limits _{k=1}^{a}\exp(2\pi ikb/a)\cdot \sum \limits _{d\left|a\right.}{\frac {c_{d}(k)}{d}}$

सभी सकारात्मक पूर्णांक के लिए चर बी में एक संपूर्ण कार्य है जहां सी_d(k) रामानुजन का योग है।

जटिलता

सबसे बड़े सामान्य विभाजकों की गणना की कम्प्यूटेशनल जटिलता का व्यापक रूप से अध्ययन किया गया है। यदि कोई Euclidean एल्गोरिथ्म और गुणा और विभाजन के लिए प्राथमिक एल्गोरिदम का उपयोग करता है, n बिट्स है $O(n^{2}).$ इसका मतलब यह है कि सबसे बड़ी आम भाजक की गणना, एक निरंतर कारक तक है, गुणन के समान जटिलता।

हालांकि, यदि एक तेज़ गुणा एल्गोरिथ्म का उपयोग किया जाता है, तो कोई जटिलता में सुधार के लिए यूक्लिडियन एल्गोरिथ्म को संशोधित कर सकता है, लेकिन एक सबसे बड़ी सामान्य विभाजक की गणना गुणन की तुलना में धीमी हो जाती है।अधिक सटीक रूप से, यदि दो पूर्णांक के गुणन n बिट्स का समय लगता है T(n), तब सबसे बड़ी आम भाजक के लिए सबसे तेज़ ज्ञात एल्गोरिथ्म एक जटिलता है $O\left(T(n)\log n\right).$ इसका तात्पर्य यह है कि सबसे तेज ज्ञात एल्गोरिथ्म की एक जटिलता है $O\left(n\,(\log n)^{2}\right).$ पिछली जटिलताएं गणना के सामान्य मॉडल, विशेष रूप से मल्टीटेप ट्यूरिंग मशीनों और यादृच्छिक-पहुंच मशीनों के लिए मान्य हैं।

सबसे महान सामान्य विभाजकों की गणना इस प्रकार क्वासिलिनियर समय में समस्याओं के वर्ग से संबंधित है।एक फोर्टियोरी, इसी निर्णय की समस्या बहुपद समय में हल करने योग्य समस्याओं के वर्ग पी से संबंधित है।जीसीडी समस्या नेकां में होने के लिए ज्ञात नहीं है, और इसलिए इसे कुशलता से समानांतर करने का कोई ज्ञात तरीका नहीं है;न ही यह पी-पूर्ण होने के लिए जाना जाता है, जिसका अर्थ है कि जीसीडी संगणना को कुशलतापूर्वक समानांतर करने के लिए संभव होने की संभावना नहीं है।Shallcross et al।दिखाया गया है कि एक संबंधित समस्या (EUGCD, यूक्लिडियन एल्गोरिथ्म के दौरान उत्पन्न होने वाले शेष अनुक्रम को निर्धारित करना) दो चर के साथ पूर्णांक रैखिक प्रोग्रामिंग की समस्या के लिए NC- बराबर है;यदि या तो समस्या 'NC' में है या 'p- पूर्ण' है, तो दूसरा भी है। चूंकि NC में NL होता है, यह भी अज्ञात है कि क्या GCD की गणना के लिए एक अंतरिक्ष-कुशल एल्गोरिथ्म मौजूद है, यहां तक कि Nondeterministic turing मशीनों के लिए भी।

यद्यपि समस्या NC में होने के लिए ज्ञात नहीं है, समानांतर एल्गोरिदम यूक्लिडियन एल्गोरिथ्म की तुलना में तेजी से तेजस्वी रूप से मौजूद हैं;सबसे तेज़ ज्ञात नियतात्मक एल्गोरिथ्म चोर और गोल्ड्रेच द्वारा है, जो (CRCW-PRAM मॉडल में) समस्या को हल कर सकता है O(n/log n) इसके साथ समय n^1+ε प्रोसेसर। यादृच्छिक एल्गोरिदम समस्या को हल कर सकते हैं O((log n)²) समय पर $\exp \left(O\left({\sqrt {n\log n}}\right)\right)$ प्रोसेसर (यह सुपरपोलिनोमियल है)।

गुण

• ए और बी का हर आम भाजक का भाजक है gcd(a, b)।
• gcd(a, b), जहां ए और बी दोनों शून्य नहीं हैं, वैकल्पिक रूप से और समान रूप से सबसे छोटे सकारात्मक पूर्णांक के रूप में परिभाषित किए जा सकते हैं जो कि रूप में लिखा जा सकता है d = a⋅p + b⋅q, जहां पी और क्यू पूर्णांक हैं।इस अभिव्यक्ति को Bézout की पहचान कहा जाता है।इस तरह की संख्या P और Q को विस्तारित Euclidean एल्गोरिथ्म के साथ गणना की जा सकती है।
• gcd(a, 0) = |a|, के लिये a ≠ 0, चूंकि कोई भी संख्या 0 का भाजक है, और एक का सबसे बड़ा विभाजक है |a|. यह आमतौर पर यूक्लिडियन एल्गोरिथ्म में आधार मामले के रूप में उपयोग किया जाता है।
• यदि कोई उत्पाद b⋅c को विभाजित करता है, और gcd(a, b) = d, फिर ए/डी विभाजित सी।
• यदि एम एक सकारात्मक पूर्णांक है, तो gcd(m⋅a, m⋅b) = m⋅gcd(a, b)।
• यदि एम कोई पूर्णांक है, तो gcd(a + m⋅b, b) = gcd(a, b)।समान रूप से, gcd(a mod b,b) = gcd(a,b)।
• यदि एम ए और बी का एक सकारात्मक सामान्य विभाजक है, तो gcd(a/m, b/m) = gcd(a, b)/m।
• GCD एक कम्यूटेटिव फ़ंक्शन है: gcd(a, b) = gcd(b, a)।
• GCD एक साहचर्य कार्य है: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)।इस प्रकार gcd(a, b, c, ...) कई तर्कों के जीसीडी को निरूपित करने के लिए इस्तेमाल किया जा सकता है।
• GCD निम्नलिखित अर्थों में एक गुणक कार्य है: यदि a₁ और एक₂ अपेक्षाकृत प्रमुख हैं, फिर gcd(a₁⋅a₂, b) = gcd(a₁, b)⋅gcd(a₂, b)।
• gcd(a, b) कम से कम आम कई से संबंधित है lcm(a, b): अपने पास

  gcd(a, b)⋅lcm(a, b) = |a⋅b|।

इस सूत्र का उपयोग अक्सर कम से कम सामान्य गुणकों की गणना करने के लिए किया जाता है: एक पहले यूक्लिड के एल्गोरिथ्म के साथ जीसीडी की गणना करता है और फिर दिए गए नंबरों के उत्पाद को उनके जीसीडी द्वारा विभाजित करता है।

• वितरण के निम्नलिखित संस्करण सही हैं:

  gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))

  lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))।

• अगर हमारे पास अद्वितीय प्रमुख कारक है a = p₁^e₁ p₂^e₂ ⋅⋅⋅ p_m^e_m तथा b = p₁^f₁ p₂^f₂ ⋅⋅⋅ p_m^f_m कहाँ पे e_i ≥ 0 तथा f_i ≥ 0, फिर ए और बी का जीसीडी है

  gcd(a,b) = p₁^{min(e₁,f₁)} p₂^{min(e₂,f₂)} ⋅⋅⋅ p_m^min(e_m,f_m)।

• कभी -कभी परिभाषित करना उपयोगी होता है gcd(0, 0) = 0 तथा lcm(0, 0) = 0 क्योंकि तब प्राकृतिक संख्याएँ GCD के साथ एक पूर्ण वितरण जाली बन जाती हैं, जैसे कि मिलिए और LCM ऑपरेशन के रूप में। परिभाषा का यह विस्तार नीचे दिए गए कम्यूटेटिव रिंग्स के लिए सामान्यीकरण के साथ भी संगत है।
• एक कार्टेशियन समन्वय प्रणाली में, gcd(a, b) अंकों में शामिल होने वाले स्ट्रेट लाइन सेगमेंट पर इंटीग्रल निर्देशांक के साथ अंकों के बीच सेगमेंट की संख्या के रूप में व्याख्या की जा सकती है (0, 0) तथा (a, b)।
• गैर-नकारात्मक पूर्णांक ए और बी के लिए, जहां ए और बी दोनों शून्य नहीं हैं, आधार & nbsp में यूक्लिडियन एल्गोरिथ्म पर विचार करके साबित करने योग्य हैं; n:

  gcd(n^a − 1, n^b − 1) = n^gcd(a,b) − 1।

• एक पहचान जिसमें यूलर के टोटिंट फ़ंक्शन शामिल हैं:

  $\gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).$

• $\sum _{k=1}^{n}\gcd(k,n)=n\prod _{p|n}\left(1+\nu _{p}(n)\left(1-{\frac {1}{p}}\right)\right)$ कहाँ पे $\nu _{p}(n)$ पी-एडिक वैल्यूएशन है।

संभावनाएं और अपेक्षित मूल्य

1972 में, जेम्स ई। निमन ने दिखाया कि k पूर्णांक, स्वतंत्र रूप से और समान रूप से {1, & nbsp; ..., & nbsp; n} से चुने गए, संभावना 1/ζ (k) के साथ कॉपरीम हैं, जैसा कि n अनंत में जाता है, जहां ζ संदर्भित करता हैRiemann Zeta फ़ंक्शन के लिए। (एक व्युत्पत्ति के लिए कोपरीट देखें।) यह परिणाम 1987 में बढ़ाया गया था ताकि यह दिखाया जा सके कि K यादृच्छिक पूर्णांक में सबसे बड़ी सामान्य विभाजक d है d है^{−k /ζ (k)। इस जानकारी का उपयोग करते हुए, सबसे महान सामान्य विभाजक फ़ंक्शन का अपेक्षित मूल्य k & nbsp; = & nbsp; 2 होने पर मौजूद नहीं है।इस मामले में संभावना है कि GCD के बराबर D है−2 /z (2), और z (2) = p के बाद से2 /6 हमारे पास है}

$\mathrm {E} (\mathrm {2} )=\sum _{d=1}^{\infty }d{\frac {6}{\pi ^{2}d^{2}}}={\frac {6}{\pi ^{2}}}\sum _{d=1}^{\infty }{\frac {1}{d}}.$

यह अंतिम योग हार्मोनिक श्रृंखला है, जो विचलन करता है।हालाँकि, जब k & nbsp; and & nbsp; 3, अपेक्षित मूल्य अच्छी तरह से परिभाषित है, और उपरोक्त तर्क द्वारा, यह है

$\mathrm {E} (k)=\sum _{d=1}^{\infty }d^{1-k}\zeta (k)^{-1}={\frac {\zeta (k-1)}{\zeta (k)}}.$

K & nbsp; = & nbsp; 3 के लिए, यह लगभग 1.3684 के बराबर है।K & nbsp; = & nbsp; 4 के लिए, यह लगभग & nbsp; 1.1106 है।

कम्यूटेटिव रिंग्स में

See also: divisor (ring theory)

महानतम सामान्य भाजक की धारणा को आम तौर पर एक मनमानी कम्यूटेटिव रिंग के तत्वों के लिए परिभाषित किया जा सकता है, हालांकि सामान्य रूप से तत्वों के प्रत्येक जोड़े के लिए एक मौजूद नहीं है।

यदि R एक कम्यूटेटिव रिंग है, और a तथा b में हैं R, फिर एक तत्व d का R का एक सामान्य भाजक कहा जाता है a तथा b अगर यह दोनों को विभाजित करता है a तथा b (यानी, अगर तत्व हैं x तथा y में R ऐसा कि d · x & nbsp; = & nbsp; a और d · y & nbsp; = & nbsp; b)। यदि d का एक सामान्य भाजक है a तथा b, और हर आम भाजक a तथा b विभाजित d, फिर d का एक सबसे बड़ा सामान्य भाजक कहा जाता है a और बी।

इस परिभाषा के साथ, दो तत्व a तथा b बहुत अच्छी तरह से कई सबसे महान सामान्य विभाजक हो सकते हैं, या कोई भी नहीं।यदि R एक अभिन्न डोमेन है तो किसी भी दो GCD का a तथा b एसोसिएट तत्व होना चाहिए, क्योंकि परिभाषा के अनुसार या तो एक को दूसरे को विभाजित करना चाहिए;वास्तव में यदि कोई GCD मौजूद है, तो इसका कोई भी सहयोगी GCD भी है।एक जीसीडी के अस्तित्व को मनमाने ढंग से अभिन्न डोमेन में आश्वासन नहीं दिया जाता है।हालांकि, यदि R एक अद्वितीय कारककरण डोमेन है, तो किसी भी दो तत्वों में एक GCD होता है, और अधिक आम तौर पर यह GCD डोमेन में सच है। यदि R एक यूक्लिडियन डोमेन है जिसमें यूक्लिडियन डिवीजन को एल्गोरिथम रूप से दिया जाता है (जैसा कि उदाहरण के लिए मामला है जब आर = एफ [एक्स] जहां F एक क्षेत्र है, या जब R गौसियन पूर्णांक की अंगूठी है), फिर सबसे बड़ी आम दिविसियों की गणना डिवीजन प्रक्रिया के आधार पर यूक्लिडियन एल्गोरिथ्म के एक रूप का उपयोग करके की जा सकती है।

निम्नलिखित दो तत्वों के साथ एक अभिन्न डोमेन का एक उदाहरण है जिसमें जीसीडी नहीं है:

$R=\mathbb {Z} \left[{\sqrt {-3}}\,\,\right],\quad a=4=2\cdot 2=\left(1+{\sqrt {-3}}\,\,\right)\left(1-{\sqrt {-3}}\,\,\right),\quad b=\left(1+{\sqrt {-3}}\,\,\right)\cdot 2.$

तत्व 2 और 1 & nbsp;+& nbsp;√−3 दो अधिकतम सामान्य विभाजक हैं (यानी, कोई भी सामान्य विभाजक जो 2 में से कई है, 2 से जुड़ा हुआ है, वही 1 & nbsp;+& nbsp;√−3, लेकिन वे जुड़े नहीं हैं, इसलिए इसका कोई सबसे बड़ा सामान्य भाजक नहीं है a और & nbsp; b।

किसी भी कम्यूटेटिव रिंग में, बेज़आउट प्रॉपर्टी के अनुरूप, हम फॉर्म के तत्वों के संग्रह पर विचार करें। p तथा q रिंग पर रेंज।यह द्वारा उत्पन्न आदर्श है a तथा b, और केवल (a, & nbsp; b) को निरूपित किया गया है।एक अंगूठी में जिनके आदर्श प्रिंसिपल (एक प्रमुख आदर्श डोमेन या पीआईडी) हैं, यह आदर्श कुछ रिंग तत्व डी के गुणकों के सेट के समान होगा;फिर यह d का एक सबसे बड़ा सामान्य भाजक है a और बी।लेकिन आदर्श (a, & nbsp; b) तब भी उपयोगी हो सकता है जब कोई सबसे बड़ा सामान्य भाजक नहीं होता है a और बी।(वास्तव में, अर्न्स्ट कुमर ने इस आदर्श का उपयोग फर्मेट के अंतिम प्रमेय के अपने उपचार में एक जीसीडी के लिए एक प्रतिस्थापन के रूप में किया, हालांकि उन्होंने इसे कुछ काल्पनिक, या आदर्श, रिंग तत्व के गुणकों के सेट के रूप में कल्पना की थी d, रिंग-थ्योरिटिक शब्द।)

यह भी देखें

• Bézout डोमेन
• न्यूनतम सार्व भाजक
• एकात्मक विभाजक

संदर्भ

• Andrews, George E. (1994) [1971], Number Theory, Dover, ISBN 9780486682525
• Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (Fifth ed.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 71081766

अग्रिम पठन

• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.2: The Greatest Common Divisor, pp. 333–356.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp. 856–862.
• Saunders Mac Lane and Garrett Birkhoff. A Survey of Modern Algebra, Fourth Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1–7: "The Euclidean Algorithm."