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

अंकगणित और संख्या सिद्धांत में, कम से कम सामान्य गुणक, सबसे कम सामान्य गुणक, या दो पूर्णांक a और b का सबसे छोटा सामान्य गुणक, जिसे आमतौर पर एलसीएम (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.$

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

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

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

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

$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 प्रत्येक प्राइम नंबर की उच्चतम शक्ति को एक साथ गुणा करने का उत्पाद होगा।तीन प्राइम नंबर 2, 3 और 7 की उच्चतम शक्ति 2 है³, 3², and 7¹ क्रमश।इस प्रकार,

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

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

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

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

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

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

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

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

सबसे बड़ा सामान्य भाजक = 2 × 2 × 3 = 12

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

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

यह विधि कई पूर्णांक के LCM को खोजने के लिए आसानी से काम करती है। चलो सकारात्मक पूर्णांक x = (x का एक परिमित अनुक्रम हो₁, x₂, ..., x_n), n > 1. The algorithm proceeds in steps as follows: on each step m it examines and updates the sequence X^(m) = (x₁^(m), x₂^(m), ..., x_n^(m)), X⁽¹⁾ = X, where X^(m) is the mth iteration of X, that is, X at step m of the algorithm, etc. The purpose of the examination is to pick the least (perhaps, one of many) element of the sequence X^(m). Assuming x_k0^(m) is the selected element, the sequence X^(m+1)की तरह परिभाषित किया गया है

एक्स_k^(m+1) = x_k^(m), k ≠ k₀: एक्स_k0^(m+1) = x_k0^(m) + x_k0⁽¹⁾

दूसरे शब्दों में, कम से कम तत्व को संबंधित एक्स द्वारा बढ़ाया जाता है जबकि बाकी तत्व एक्स से गुजरते हैं^(m) to X^(m+1)अपरिवर्तित।

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

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

एक्स⁽²⁾= (6, 4, 6)

एक्स⁽³⁾= (6, 8, 6)

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

एक्स⁽⁵⁾= (9, 8, 12)

एक्स⁽⁶⁾= (9, 12, 12)

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

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

४

7

12

२१

४२

प्रक्रिया सभी संख्याओं को 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

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

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

सूत्र

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

अंकगणित के मौलिक सिद्धांत के अनुसार, 1 से अधिक पूर्णांक को कारकों के आदेश तक, प्राइम नंबरों के उत्पाद के रूप में विशिष्ट रूप से प्रतिनिधित्व किया जा सकता है:

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

जहां घातांक 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.$

वास्तव में, प्रत्येक तर्कसंगत संख्या को विशिष्ट रूप से प्राइम्स के उत्पाद के रूप में लिखा जा सकता है, अगर नकारात्मक घातांक की अनुमति है।जब यह किया जाता है, तो उपरोक्त सूत्र मान्य रहते हैं।उदाहरण के लिए:

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

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

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

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

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

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

कम से कम आम मल्टीपल को आम तौर पर कम्यूटेटिव रिंगों पर इस प्रकार परिभाषित किया जा सकता है: चलो ए और बी एक कम्यूटेटिव रिंग आर। के तत्व हैं। ए और बी का एक सामान्य मल्टीपल आर का एक तत्व एम है जैसे कि ए और बी दोनों डिवाइड एम (जो कि है), वहाँ मौजूद तत्व X और y r के मौजूद हैं जैसे कि कुल्हाड़ी = m और by = m)।ए और बी का एक कम से कम सामान्य एक बहुराष्ट्रीय पदार्थ एक सामान्य कई है जो न्यूनतम है, इस अर्थ में कि किसी भी अन्य सामान्य कई एन के लिए, ए और बी, एम डिवाइड्स & nbsp; n।

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

यह भी देखें

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

]