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

गणित में, दो या दो से अधिक पूर्णांकों का महत्तम समापवर्तक (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 है। अभ्यास में, यह विधि केवल छोटी संख्या के लिए संभव है, क्योंकि अभाज्य गुणनखंडों की गणना में बहुत अधिक समय लगता है।

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

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

1:57

एनीमेशन 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।

लेहमर का GCD एल्गोरिथ्म

Main article: Lehmer's GCD algorithm

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

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

बाइनरी GCD एल्गोरिथ्म

Main article: Binary GCD algorithm

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

• a = b।

gcd (a, a) = a, वांछित gcd a x 2d है (जैसा कि a और b अन्य मामलों में बदल जाते हैं, और d रिकॉर्ड करता है कि a और b दोनों को अगले चरण में 2 से विभाजित किया गया है, प्रारंभिक जोड़ी का gcd a और 2d का उत्पाद है।

• a और b दोनों सम हैं।

तब 2 एक सामान्य भाजक है। a और b दोनों को 2 से विभाजित करें, d को 1 से बढ़ाएँ ताकि 2 की संख्या एक सामान्य भाजक हो और जारी रहे।

• A सम है और B विषम है।

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

• A विषम है और B सम है।

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

• a और b दोनों विषम हैं।

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

उपरोक्त चरणों में से प्रत्येक गैर-ऋणात्मक छोड़ते हुए a और b में से कम से कम एक को कम करता है और इसलिए इसे केवल परिमित संख्या में ही दोहराया जा सकता है। इस प्रकार अंततः प्रक्रिया में a = b, रोकने के मामले में परिणाम देती है। तब gcd एक x 2d है।

उदाहरण: (a, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → →(3, 3, 1) इस प्रकार मूल GCD 2d = 21 और a= b= 3 का गुणनफल 6 है।

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

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

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

$O(n^{2})$।

अन्य तरीके

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

यदि a और b दोनों अशून्य हैं, तो a और b के बड़े सामान्य भाजक की गणना a और b के कम से कम सामान्य गुणक (LCM) का उपयोग करके की जा सकती है:

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

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

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

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

जो a और b परिमेय संख्याओं या अनुरूपणीय वास्तविक संख्याओं का सामान्यीकरण करता है।

कीथ स्लाविन (Keith Slavin) ने दिखाया है कि विषम 1 के लिए:

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

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

$\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}}$

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

जटिलता

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

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

पिछली जटिलताएं गणना के सामान्य मॉडल, विशेष रूप से मल्टीटेप ट्यूरिंग मशीनों और रैंडम-एक्सेस मशीनों के लिए मान्य हैं।

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

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

गुण

• a और b का प्रत्येक सामान्य विभाजक gcd(a, b) का एक विभाजक है।
• gcd(a, b), जहां जहां a और b दोनों शून्य नहीं हैं, को वैकल्पिक रूप से और समतुल्य रूप से छोटे धनात्मक पूर्णांक d के रूप में परिभाषित किया जा सकता है जिसे d = a⋅p + b⋅q के रूप में लिखा जा सकता है, जहाँ p और q पूर्णांक हैं। इस अभिव्यक्ति को बेज़ाउट (Bézout) की पहचान कहा जाता है। इस तरह की संख्या p और q की गणना विस्तारित यूक्लिडियन (Euclidean) एल्गोरिथ्म के साथ की जा सकती है।
• gcd(a, 0) = |a|, के लिये a ≠ 0, चूंकि कोई भी संख्या 0 का भाजक है, और |a| का महत्तम विभाजक है। यह आमतौर पर यूक्लिडियन एल्गोरिथ्म में आधार मामले के रूप में उपयोग किया जाता है।
• यदि a उत्पाद b⋅c और gcd(a, b) = d को विभाजित करता है, तो a/d c को विभाजित करता है।
• यदि m एक धनात्मक पूर्णांक है, तो gcd(m⋅a, m⋅b) = m⋅gcd(a, b)।
• यदि m कोई पूर्णांक है, तो gcd(a + m⋅b, b) = gcd(a, b)।समान रूप से, gcd(a mod b,b) = gcd(a,b)।
• यदि m 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 को दर्शाने के लिए किया जा सकता है।
• 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 की गणना करता है और फिर दी गई संख्याओं के उत्पाद को उनके gcd द्वारा विभाजित करता है।

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

  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, फिर a और b का gcd है

  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) को मिलाने वाले सीधी रेखा खंड पर अभिन्न निर्देशांक वाले बिंदुओं के बीच खंडों की संख्या के रूप में व्याख्या की जा सकती है।
• गैर-ऋणात्मक पूर्णांक a और b के लिए, जहां a और b दोनों शून्य नहीं हैं, आधार 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 में, जेम्स ई निमन (James E. Nymann ) ने दिखाया कि k पूर्णांक, स्वतंत्र रूप से और समान रूप से {1, ..., n} से चुने गए, प्रायिकता 1/ζ(k) के साथ सहअभाज्य हैं, क्योंकि n अनंत तक जाता है, जहां रीमैन ज़ेटा को संदर्भित करता है। ( व्युत्पत्ति के लिए सह अभाज्य देखें।) इस परिणाम को 1987 में यह दिखाने के लिए बढ़ाया गया था कि k यादृच्छिक पूर्णांकों में महत्तम समापवर्तक d होने की संभावना d−k/ζ(k) है।

इस जानकारी का उपयोग करते हुए, बड़े सामान्य भाजक फलन का अपेक्षित मान देखा जा सकता है (अनौपचारिक रूप से) जब k = 2 मौजूद नहीं होता है। इस मामले में GCD के d के बराबर होने की संभावना d−2/ζ(2) है, और चूंकि (2) = π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}}.$

यह अंतिम संकलन हार्मोनिक श्रृंखला है, जो विचलन करता है।हालाँकि जब k3, अपेक्षित मान अच्छी तरह से परिभाषित है, और उपरोक्त तर्क द्वारा, यह है

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

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

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

See also: divisor (ring theory)

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

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

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

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

$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 + √−3 अधिकतम सामान्य विभाजक हैं अर्थात, कोई भी सामान्य भाजक जो 2 का गुणज है, 2 से जुड़ा है, वही √−3, के लिए धारण करता है, लेकिन वे संबद्ध नहीं हैं, इसलिए वहां a और b का महत्तम समापवर्तक नहीं है।।

बेज़ाउट संपत्ति के अनुरूप, हम किसी भी कम्यूटेटिव रिंग में, फॉर्म के तत्वों के संग्रह पर विचार कर सकते हैं, जहां p तथा q रिंग के ऊपर रेंज करते हैं। यह a तथा b द्वारा उत्पन्न आदर्श है और केवल (a तथा b) के रूप में दर्शाया जाता है। एक वलय में जिसके सभी आदर्श प्रमुख हैं (एक प्रमुख आदर्श डोमेन या PID) हैं, यह आदर्श कुछ वलय तत्व d के गुणकों समुच्चय के समान होगा; तो यह d, a और b का एक महत्तम समापवर्तक है। लेकिन आदर्श (a और b) तब भी उपयोगी हो सकता है जब a और b का कोई महत्तम समापवर्तक न हो। ( वास्तव में, अर्न्स्ट कुमर ने फ़र्मेट के अंतिम प्रमेय के अपने उपचार में जीसीडी के प्रतिस्थापन के रूप में इस आदर्श का उपयोग किया, हालांकि उन्होंने इसे कुछ काल्पनिक, या आदर्श, रिंग तत्व 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."