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

अंकगणित और संख्या सिद्धांत में, दो पूर्णांक a और b का कम से कम सामान्य गुणक (Least common multiple), सबसे कम सामान्य गुणक ( lowest common multiple), या सबसे छोटा सामान्य गुणक (smallest common multiple), जिसे आमतौर पर एलसीएम (a, b) द्वारा दर्शाया जाता है, सबसे छोटा धनात्मक पूर्णांक (positive integer) होता है जो a और b दोनों से विभाज्य होता है।चूँकि पूर्णांकों का शून्य से भाग अपरिभाषित (undefined) है, इसलिए इस परिभाषा का अर्थ केवल तभी संभव है जब a और b दोनों शून्य से अलग हों।हालाँकि, कुछ लेखक एलसीएम (a,0) को सभी a के लिए 0 के रूप में परिभाषित करते हैं, क्योंकि 0, a और 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) को इस हर (denominator) के साथ भिन्न (fraction) के रूप में व्यक्त किया जा सकता है।उदाहरण के लिए,

${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) का उपयोग करना

सूत्र (formula) के साथ महत्तम समापवर्तक (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 हो, क्योंकि gcd (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 से बड़ा प्रत्येक धनात्मक पूर्णांक केवल एक ही तरीके से अभाज्य संख्याओं (prime numbers) के गुणनफल के रूप में लिखा जा सकता है। अभाज्य संख्याओं को परमाणु तत्व मान सकते है, जो संयुक्त होने पर एक संमिश्र संख्या (composite number) बनाते हैं।

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

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

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

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

उदाहरण: LCM (8,9,21)

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

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

lcm प्रत्येक अभाज्य संख्या की उच्चतम घात (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.$

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

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

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

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

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

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

कम से कम सामान्य गुणक (Least common multiple) = 2 × 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

महत्तम समापवर्तक (greatest common divisor) = 2 × 2 × 3 = 12

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

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

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

मान लीजिए कि धनात्मक पूर्णांकों 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 बिल्कुल lcm(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) को विशिष्ट रूप से अभाज्य संख्याओं के गुणनफल के रूप में लिखा जा सकता है, यदि ऋणात्मक घातांक (negative exponents) की अनुमति हो। जब ऐसा किया जाता है, तो उपरोक्त सूत्र मान्य रहते हैं। उदाहरण के लिए,

${\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) लिखें। (ध्यान दें कि की सामान्य परिमाण-आधारित परिभाषा का उपयोग यहां नहीं किया गया है।)

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

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

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

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.$

Define divides in terms of lcm and gcd $a\geq b\iff a=\operatorname {lcm} (a,b),$ $a\leq b\iff a=\gcd(a,b).$

यह भी दिखाया जा सकता है यह जाली वितरण है;यानी, LCM GCD पर वितरित करता है और GCD LCM पर वितरित करता है:

$\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) अलग -अलग प्राइम नंबरों का उत्पाद होना चाहिए (यानी, 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 विभाजित करता है।

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

यह भी देखें

• विषम रद्दीकरण
• कोपरीम पूर्णांक
• 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

]