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

वेन आरेख 2, 3, 4, 5 और 7 के संयोजन के कम से कम सामान्य गुणकों को दर्शाता है (6 को छोड़ दिया जाता है क्योंकि यह 2 & nbsp; & times; & nbsp; 3, दोनों पहले से ही प्रतिनिधित्व कर रहे हैं)।कार्ड गेम जिसमें 5 खिलाड़ियों के बीच समान रूप से विभाजित होने के लिए इसके कार्ड की आवश्यकता होती है, उन्हें कम से कम 60 कार्ड की आवश्यकता होती है, 2, 3, 4 और 5 सेट के चौराहे पर संख्या, लेकिन 7 सेट नहीं।

अंकगणित और संख्या सिद्धांत में, कम से कम सामान्य गुणक, सबसे कम सामान्य गुणक, या दो पूर्णांक a और b का सबसे छोटा सामान्य गुणक, जिसे आमतौर पर lcm (a, b) द्वारा दर्शाया जाता है, सबसे छोटा धनात्मक पूर्णांक होता है जो a और b दोनों से विभाज्य होता है<रेफ> हार्डी एंड राइट, § 5.1, पी।48</ref> चूँकि पूर्णांकों का शून्य से भाग अपरिभाषित है, इसलिए इस परिभाषा का अर्थ केवल तभी संभव है जब a और b दोनों शून्य से भिन्न हों। कुछ भी, कुछ लेखक एलसीएम (ए, 0) को सभी के लिए 0 के रूप में परिभाषित करते हैं, क्योंकि 0 ए और 0 का एकमात्र सामान्य मल्टीपल है।

LCM सबसे कम सामान्य भाजक (LCD) है जिसका उपयोग अंशों को जोड़ने, घटाया या तुलना करने से पहले किया जा सकता है।

दो से अधिक पूर्णांक ए, बी, सी, से अधिक सामान्य कई कई।।।, आमतौर पर 'lcm (a, & nbsp; b, & nbsp; c।,।) द्वारा निरूपित किया गया है, यह भी अच्छी तरह से परिभाषित किया गया है: यह सबसे छोटा सकारात्मक पूर्णांक है जो प्रत्येक, B, C, में से प्रत्येक द्वारा विभाज्य है।।।

अवलोकन

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

संकेतन

दो पूर्णांक ए और बी में से कम से कम आम कई को एलसीएम (ए, बी) के रूप में दर्शाया गया है। Some older textbooks use [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 है। इसलिए, सबसे कम सामान्य मल्टीपल है & nbsp; 12।

अनुप्रयोग

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

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

जहां हर 42 का उपयोग किया गया था, क्योंकि यह 21 और 6 में से कम से कम आम है।

गियर समस्या

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

ग्रह संरेखण =

See also: Planetary alignment

मान लीजिए कि तीन ग्रह एक तारे के चारों ओर घूमते हैं जो अपनी कक्षाओं को पूरा करने के लिए क्रमशः एल, एम और एन इकाइयों को लेते हैं।मान लें कि एल, एम और एन पूर्णांक हैं।ग्रहों को एक प्रारंभिक रैखिक संरेखण के बाद स्टार के चारों ओर घूमना शुरू कर दिया, सभी ग्रहों ने फिर से एक रैखिक संरेखण प्राप्त किया $\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$ ऑर्बिट्स, क्रमशः, स्टार के चारों ओर।

गणना

सबसे महान सामान्य भाजक का उपयोग करना

कम से कम सामान्य मल्टीपल को सूत्र के साथ सबसे महान सामान्य भाजक (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

]