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

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

लेहमर का 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)।
• गैर-नकारात्मक पूर्णांक ए और बी के लिए, जहां ए और बी दोनों शून्य नहीं हैं, आधार & 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 में, जेम्स ई निमन (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, फिर एक तत्व 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."