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

अंकगणित और संख्या सिद्धांत में, दो पूर्णांक a और b न्यूनतम सामान्य गुणक (Least common multiple), निम्नतम सामान्य गुणक ( lowest common multiple), या लघुतम सामान्य गुणक (smallest common multiple) को एलसीएम (a, b) द्वारा दर्शाया जाता है, और यह सबसे लघुतम धनात्मक पूर्णांक (positive integer) होता है जो a और b दोनों से विभाज्य होता है।चूँकि पूर्णांकों का शून्य से भाग अपरिभाषित (undefined) है, इसलिए इस परिभाषा का अर्थ केवल तभी संभव है जब a और b दोनों शून्य से अलग हों।हालाँकि, कुछ लेखक एलसीएम (a,0) को सभी a के लिए 0 के रूप में परिभाषित करते हैं, क्योंकि a और 0 का एकमात्र सामान्य गुणज 0 है।

एलसीएम "न्यूनतम सार्व भाजक" (LCD) है जिसका उपयोग भिन्नों (fractions) को जोड़ने, घटाने या तुलना करने से पहले किया जाता है।

दो से अधिक पूर्णांकों a, b, c....... का लघुत्तम समापवर्त्य, जिसे आमतौर पर एलसीएम (a, b, c, . . .) द्वारा दर्शाया जाता है, को भी अच्छी तरह से परिभाषित किया जाता है। यह सबसे छोटा धनात्मक पूर्णांक है जो a, b, c......प्रत्येक से विभाज्य होता है।

अवलोकन

किसी संख्या का गुणज उस संख्या और पूर्णांक का गुणनफल होता है। उदाहरण के लिए 5 का गुणज 10 है क्योंकि 5 × 2 = 10, इसलिए 10, 5 और 2 से विभाज्य है। क्योंकि 10 सबसे छोटा धनात्मक पूर्णांक है जो 5 और 2 दोनों से विभाज्य है, यह 5 और 2 का सबसे छोटा सामान्य गुणज है। इसी सिद्धांत के अनुसार −5 और −2 का भी 10 सबसे छोटा सामान्य गुणज है।

संकेतन

दो पूर्णांकों a और b के लघुत्तम समापवर्त्य को एलसीएम (a, b) के रूप में दर्शाया जाता है। कुछ पुरानी पाठ्यपुस्तकें [a, b] का उपयोग करती हैं।

उदाहरण

$\operatorname {lcm} (4,6)$

4 के गुणज हैं

$4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,...$

6 के गुणज हैं

$6,12,18,24,30,36,42,48,54,60,66,72,...$

4 और 6 के सामान्य गुणज संख्याएँ हैं जो दोनों सूचियों में हैं

$12,24,36,48,60,72,...$

इस सूची में सबसे छोटी संख्या 12 है, इसलिए सबसे छोटा सामान्य गुणज 12 है।

अनुप्रयोग

साधारण भिन्नों (fractions) को जोड़ते, घटाते या तुलना करते समय, हर (denominator) के सबसे छोटा सामान्य गुणज (जिसे अक्सर न्यूनतम सार्व भाजक कहा जाता है) का उपयोग किया जाता है, क्योंकि प्रत्येक भिन्न (fraction) को उस भिन्न (fraction) के हर (denominator) के साथ दर्शाया जाता है। उदाहरण के लिए,

${2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}$

यहाँ हर 42 का इस्तेमाल किया गया था, क्योंकि यह 21 और 6 का सबसे छोटा सामान्य गुणक है।

गियर समस्या

मान लीजिए कि एक मशीन में दो मेशिंग गियर हैं, जिनमें क्रमशः m और n दांत हैं, और गियर्स को पहले गियर के केंद्र से दूसरे गियर के केंद्र तक खींचे गए रेखा खंड (लाइन सेगमेंट) द्वारा चिह्नित किया जाता है। जब गियर घूमना प्रारम्भ करते हैं, तो रेखा खंड (लाइन सेगमेंट) को फिर से संरेखित करने के लिए पहले गियर को जितने घुमावों को पूरा करना होगा, उनकी गणना $\operatorname {lcm} (m,n)$ का उपयोग करके की जा सकती है। पहले गियर को पूरा के लिए $\operatorname {lcm} (m,n) \over m$ रोटेशन को पूरा करना होगा। उस समय तक, दूसरे गियर ने $\operatorname {lcm} (m,n) \over n$ घुमाव बना लिए होंगे।

ग्रह संरेखण

मान लीजिए कि तारे के चारों ओर घूमने वाले तीन ग्रह हैं जो अपनी कक्षाओं को पूरा करने के लिए क्रमशः l, m और n इकाई समय लेते हैं। मान लें कि l, m और n पूर्णांक हैं। यह मानते हुए कि ग्रह एक प्रारंभिक रैखिक संरेखण के बाद तारे के चारों ओर घूमना शुरू कर देते हैं, सभी ग्रह $\operatorname {lcm} (l,m,n)$ समय की इकाइयों के बाद फिर से एक रैखिक संरेखण प्राप्त करते हैं। इस समय, पहला, दूसरा और तीसरा ग्रह $\operatorname {lcm} (l,m,n) \over l$, $\operatorname {lcm} (l,m,n) \over m$ तथा $\operatorname {lcm} (l,m,n) \over n$ तारे के चारों ओर क्रमशः परिक्रमा करते हैं।

गणना

महत्तम सामान्य भाजक (greatest common divisor) का उपयोग करना

सूत्र के साथ महत्तम सामान्य भाजक (GCD) से लघुत्तम समापवर्त्य की गणना की जा सकती है,

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

परिणाम से बड़े पूर्णांकों को प्रस्तुत करने से बचने के लिए, समतुल्य सूत्रों का उपयोग करना सुविधाजनक है,

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

जहां विभाजन का परिणाम हमेशा एक पूर्णांक होता है।

ये सूत्र तब भी मान्य होते हैं जब a और b में से कोई एक 0 हो, क्योंकि जीसीडी (a, 0) = |a|। हालाँकि, यदि a और b दोनों 0 हैं, तो ये सूत्र शून्य से भाग देंगे; इसलिए, lcm(0, 0) = 0 को एक विशेष स्थिति माना जाना चाहिए।

ऊपर दिए गए उदाहरण पर लौटने के लिए,

$\operatorname {lcm} (21,6)=6\times {\frac {21}{\gcd(21,6)}}=6\times {\frac {21}{3}}=6\times 7=42.$

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

प्राइम फैक्टरकरण का उपयोग करना

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

उदाहरण के लिए:

$90=2^{1}\cdot 3^{2}\cdot 5^{1}=2\cdot 3\cdot 3\cdot 5.$

यहां, संयुक्त संख्या 90 अभाज्य संख्या 2 के एक परमाणु, अभाज्य संख्या 3 के दो परमाणुओं और अभाज्य संख्या 5 के एक परमाणु से बनी है।

इस तथ्य का उपयोग संख्याओं के समूह का एलसीएम ज्ञात करने के लिए किया जा सकता है।

उदाहरण: एलसीएम (8,9,21)

प्रत्येक संख्या का गुणनखंड करें और इसे अभाज्य संख्या घातों के गुणनफल के रूप में व्यक्त करें।

${\begin{aligned}8&=2^{3}\\9&=3^{2}\\21&=3^{1}\cdot 7^{1}\end{aligned}}$

एलसीएम प्रत्येक अभाज्य संख्या की उच्चतम घात (highest power) को एक साथ गुणा करने का गुणनफल होता है। तीन अभाज्य संख्याओं 2, 3 और 7 की उच्चतम घात क्रमशः 23, 32 और 71 है। इस प्रकार,

$\operatorname {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.$

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

एक ही विधि को वेन आरेख के साथ भी चित्रित किया जा सकता है, प्रत्येक सर्कल में प्रदर्शित दो संख्याओं में से प्रत्येक के अभाज्य गुणनखंड के साथ और वे सभी कारक जो प्रतिच्छेदन में समान रूप से साझा करते हैं। एलसीएम तब आरेख में सभी अभाज्य संख्याओं को गुणा करके पाया जा सकता है।

यहाँ एक उदाहरण है,

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5,

दो "2" और एक "3" को साझा करना,

कम से कम सामान्य गुणक = 2 × 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

महत्तम सामान्य भाजक (greatest common divisor) = 2 × 2 × 3 = 12

यह महत्तम सामान्य भाजक (GCD) के लिए भी काम करता है, सिवाय इसके कि वेन आरेख में सभी संख्याओं को गुणा करने के बजाय, केवल उन प्रमुख कारकों को गुणा किया जाता है जो प्रतिच्छेदन में हैं। इस प्रकार 48 और 180 का जीसीडी 2 × 2 × 3 = 12 है।

एक साधारण एल्गोरिथ्म का उपयोग करना

यह विधि अनेक पूर्णांकों का एलसीएम ज्ञात करने के लिए सरलता से कार्य करती है।

मान लीजिए कि धनात्मक पूर्णांकों X = (x1, x2, ..., xn), n > 1 का एक परिमित अनुक्रम है। एल्गोरिथ्म निम्नानुसार आगे बढ़ता है, प्रत्येक चरण m पर यह अनुक्रम X(m) = (x1(m), x2(m), ..., xn(m)), X(1) = X की जांच और अद्यतन करता है, जहां X(m) X का mवां पुनरावृत्ति है, जो कि एल्गोरिथम के चरण m पर X है , आदि। परीक्षा का उद्देश्य अनुक्रम X(m) के सबसे कम (शायद, कई में से एक) तत्व को चुनना है। यह मानते हुए कि xk0(m) चयनित तत्व है, अनुक्रम X(m 1) को इस प्रकार परिभाषित किया गया है

x_k^(m+1) = x_k^(m), k ≠ k₀

x_k0^(m+1) = x_k0^(m) + x_k0⁽¹⁾

दूसरे शब्दों में, सबसे छोटा तत्व संगत x से बढ़ जाता है जबकि शेष तत्व X^(m) से X^(m+1)तक अपरिवर्तित हो जाते हैं।

एल्गोरिथ्म तब बंद हो जाता है जब अनुक्रम X^(m) में सभी तत्व समान होते हैं। इनका उभयनिष्ठ मान L बिल्कुल एलसीएम (X) है।

उदाहरण के लिए, यदि x = x⁽¹⁾= (3, 4, 6), एल्गोरिथ्म में कदम उत्पादन

X⁽²⁾ = (6, 4, 6)

X⁽³⁾ = (6, 8, 6)

X⁽⁴⁾ = (6, 8, 12) दूसरा 6 चुनकर

X⁽⁵⁾ = (9, 8, 12)

X⁽⁶⁾ = (9, 12, 12)

X⁽⁷⁾ = (12, 12, 12) तो एलसीएम = 12।

तालिका-विधि का उपयोग करना

यह विधि किसी भी संख्या के लिए काम करती है। एक तालिका में सभी संख्याओं को लंबवत रूप से सूचीबद्ध करके यह शुरू होता है (इस उदाहरण में 4, 7, 12, 21, और 42

4

7

12

21

42

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

×	2
4	2
7	7
12	6
21	21
42	21

अब, यह मानते हुए कि 2 ने कम से कम एक संख्या को विभाजित किया है (जैसा कि इस उदाहरण में है), जांचें कि क्या 2 फिर से विभाजित होता है,

×	2	2
4	2	1
7	7	7
12	6	3
21	21	21
42	21	21

एक बार जब 2 वर्तमान कॉलम में किसी भी संख्या को विभाजित नहीं करता है, तो अगले बड़े अभाज्य 3 से विभाजित करके प्रक्रिया को दोहराएं, 3 अब विभाजित नहीं होता है तो अगले बड़े अभाज्यों का प्रयास करें, 5 फिर 7, आदि। प्रक्रिया समाप्त हो जाती है जब सभी संख्याओं को घटाकर 1 कर दिया जाता है (अंतिम अभाज्य भाजक के नीचे के स्तंभ में केवल 1 है)।

×	2	2	3	7
4	2	1	1	1
7	7	7	7	1
12	6	3	1	1
21	21	21	7	1
42	21	21	7	1

अब, एलसीएम निकालने के लिए शीर्ष पंक्ति में संख्याओं को गुणा करें। इस मामले में, यह 2 × 2 × 3 × 7 = 84 है।

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

सूत्र

अंकगणित का मौलिक प्रमेय

अंकगणित के मौलिक प्रमेय के अनुसार, 1 से अधिक के प्रत्येक पूर्णांक को विशिष्ट रूप से अभाज्य संख्याओं के गुणनफल के रूप में, गुणक (factors) के क्रम तक दर्शाया जा सकता है,

$n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod _{p}p^{n_{p}},$

जहां घातांक (exponents) n₂, n₃ ... गैर-नकारात्मक पूर्णांक हैं, उदाहरण के लिए, 84 = 2² 3¹ 5⁰ 7¹ 11⁰ 13⁰...

दो सकारात्मक पूर्णांक को देखते हुए ${\textstyle a=\prod _{p}p^{a_{p}}}$ तथा ${\textstyle b=\prod _{p}p^{b_{p}}}$, उनके कम से कम सामान्य और सबसे बड़े सामान्य भाजक को सूत्र द्वारा दिया गया है

$\gcd(a,b)=\prod _{p}p^{\min(a_{p},b_{p})}$

तथा

$\operatorname {lcm} (a,b)=\prod _{p}p^{\max(a_{p},b_{p})}.$

तब से

$\min(x,y)+\max(x,y)=x+y,$

यह देता है

$\gcd(a,b)\operatorname {lcm} (a,b)=ab.$

वास्तव में, प्रत्येक परिमेय संख्या (rational numbers) को विशिष्ट रूप से अभाज्य संख्याओं के गुणनफल के रूप में लिखा जा सकता है, यदि ऋणात्मक घातांक की अनुमति हो। जब ऐसा किया जाता है, तो उपरोक्त सूत्र मान्य रहते हैं। उदाहरण के लिए,

${\begin{aligned}4&=2^{2}3^{0},&6&=2^{1}3^{1},&\gcd(4,6)&=2^{1}3^{0}=2,&\operatorname {lcm} (4,6)&=2^{2}3^{1}=12.\\[8pt]{\tfrac {1}{3}}&=2^{0}3^{-1}5^{0},&{\tfrac {2}{5}}&=2^{1}3^{0}5^{-1},&\gcd \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{0}3^{-1}5^{-1}={\tfrac {1}{15}},&\operatorname {lcm} \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{1}3^{0}5^{0}=2,\\[8pt]{\tfrac {1}{6}}&=2^{-1}3^{-1},&{\tfrac {3}{4}}&=2^{-2}3^{1},&\gcd \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-2}3^{-1}={\tfrac {1}{12}},&\operatorname {lcm} \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-1}3^{1}={\tfrac {3}{2}}.\end{aligned}}$

जाली-सिद्धांत

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

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

यदि पूर्णांक चरों, जीसीडी, एलसीएम, और को शामिल करने वाला सूत्र सत्य है, तो जीसीडी को एलसीएम से बदलने और के साथ बदलने से प्राप्त सूत्र भी सत्य है। (याद रखें को डिवाइड के रूप में परिभाषित किया गया है)।

दोहरे सूत्रों के निम्नलिखित जोड़े सामान्य जाली-सैद्धांतिक पहचान के विशेष मामले हैं।

क्रमविनिमेयता (Commutative laws) $\operatorname {lcm} (a,b)=\operatorname {lcm} (b,a),$ $\gcd(a,b)=\gcd(b,a).$

Associative laws $\operatorname {lcm} (a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\operatorname {lcm} (a,b),c),$ $\gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c).$

Absorption laws $\operatorname {lcm} (a,\gcd(a,b))=a,$ $\gcd(a,\operatorname {lcm} (a,b))=a.$

Idempotent laws $\operatorname {lcm} (a,a)=a,$ $\gcd(a,a)=a.$

विभाजन को lcm और gcd के रूप में परिभाषित करें $a\geq b\iff a=\operatorname {lcm} (a,b),$ $a\leq b\iff a=\gcd(a,b).$

यह भी दिखाया जा सकता है यह जाली वितरण है, यानी एलसीएम जीसीडी पर वितरित करता है और जीसीडी एलसीएम पर वितरित करता है,

$\operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c)),$

$\gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c)).$

यह पहचान आत्म-दोहरी है,

$\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (b,c),\operatorname {lcm} (a,c))=\operatorname {lcm} (\gcd(a,b),\gcd(b,c),\gcd(a,c)).$

अन्य

• मान लीजिए कि D, ω(D) भिन्न अभाज्य संख्याओं का गुणनफल है (अर्थात, D वर्गमुक्त है)।

फिर$|\{(x,y)\;:\;\operatorname {lcm} (x,y)=D\}|=3^{\omega (D)},$ जहां पूर्ण सलाखों || एक सेट की कार्डिनैलिटी को निरूपित करें।

• अगर कोई नहीं $a_{1},a_{2},\ldots ,a_{r}$ शून्य है, फिर

$\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r-1}),a_{r}).$

क्रम विनिमय वलय में

कम से कम सामान्य गुणक को आम तौर पर क्रम विनिमय रिंगों पर परिभाषित किया जा सकता है, मान लीजिए कि a और b एक क्रम विनिमय रिंग R के तत्व हैं। a और b का एक सामान्य गुणक R का एक तत्व m है जैसे कि a और b दोनों m को विभाजित करते हैं (अर्थात , R के अवयव x और y इस प्रकार मौजूद हैं कि ax = m और by = m)। a और b का कम से कम सामान्य गुणक ((Least common multiple) एक सामान्य गुणक है जो न्यूनतम है, इस अर्थ में कि a और b के किसी भी अन्य सामान्य गुणक के लिए, m विभाजित करता है।

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

यह भी देखें

• विषम रद्दीकरण
• कोपरीम पूर्णांक
• चेबीशेव (Chebyshev) फ़ंक्शन

संदर्भ

• Crandall, Richard; Pomerance, Carl (2001), Prime Numbers: A Computational Perspective, New York: Springer, ISBN 0-387-94777-9
• Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
• Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766

]