लुकास अनुक्रम
गणित में, लुकास अनुक्रम और कुछ स्थिर-पुनरावर्ती अनुक्रम हैं|निरंतर-पुनरावर्ती पूर्णांक अनुक्रम जो पुनरावृत्ति संबंध को संतुष्ट करते हैं
कहाँ और निश्चित पूर्णांक हैं. इस पुनरावृत्ति संबंध को संतुष्ट करने वाले किसी भी अनुक्रम को लुकास अनुक्रमों के रैखिक संयोजन के रूप में दर्शाया जा सकता है और अधिक सामान्यतः, लुकास अनुक्रम और में बहुपदों के अनुक्रम का प्रतिनिधित्व करते हैं और पूर्णांक गुणांक के साथ.
लुकास अनुक्रमों के प्रसिद्ध उदाहरणों में फाइबोनैचि संख्याएं, मेरसेन संख्याएं, पेल संख्याएं, लुकास संख्याएं, जैकबस्टल संख्याएं और फर्मेट संख्याओं का एक सुपरसेट शामिल हैं (नीचे देखें)। लुकास अनुक्रमों का नाम फ्रांस के गणितज्ञ एडवर्ड लुकास के नाम पर रखा गया है।
पुनरावृत्ति संबंध
दो पूर्णांक पैरामीटर दिए गए हैं और , पहली तरह के लुकास अनुक्रम और दूसरे प्रकार का पुनरावृत्ति संबंधों द्वारा परिभाषित हैं:
और
इसे दर्शाना कठिन नहीं है ,
उपरोक्त संबंधों को मैट्रिक्स (गणित) रूप में इस प्रकार बताया जा सकता है:
उदाहरण
लुकास अनुक्रमों की प्रारंभिक शर्तें और तालिका में दिए गए हैं:
स्पष्ट अभिव्यक्ति
लुकास अनुक्रमों के लिए पुनरावृत्ति संबंध का विशिष्ट समीकरण और है:
इसमें विवेचक है और एक बहुपद का मूल:
इस प्रकार:
ध्यान दें कि क्रम और क्रम पुनरावृत्ति संबंध को भी संतुष्ट करें। हालाँकि ये पूर्णांक अनुक्रम नहीं हो सकते हैं।
अलग जड़ें
कब , ए और बी अलग-अलग हैं और कोई भी इसे तुरंत सत्यापित कर सकता है
इससे यह पता चलता है कि लुकास अनुक्रमों की शर्तों को ए और बी के संदर्भ में निम्नानुसार व्यक्त किया जा सकता है
दोहराया गया रूट
मामला बिल्कुल तब होता है जब कुछ पूर्णांक S के लिए ताकि . इस मामले में कोई भी इसे आसानी से पा सकता है
गुण
कार्य उत्पन्न करना
सामान्य जनरेटिंग फ़ंक्शन हैं
पेल समीकरण
कब , लुकास अनुक्रम और कुछ पेल समीकरणों को संतुष्ट करें:
विभिन्न मापदंडों के साथ अनुक्रमों के बीच संबंध
- किसी भी संख्या c के लिए, अनुक्रम और साथ
- के समान विभेदक है और :
- किसी भी संख्या c के लिए, हमारे पास भी है
अन्य संबंध
लुकास अनुक्रमों की शर्तें उन संबंधों को संतुष्ट करती हैं जो फाइबोनैचि संख्याओं के बीच के सामान्यीकरण हैं और लुकास संख्याएँ . उदाहरण के लिए:
विभाज्यता गुण
परिणामों में वह भी शामिल है का गुणज है , यानी, अनुक्रम एक विभाज्यता क्रम है. इसका तात्पर्य, विशेष रूप से, वह है केवल तभी अभाज्य संख्या हो सकती है जब n अभाज्य हो। एक अन्य परिणाम वर्ग द्वारा घातांक का एक एनालॉग है जो तेजी से गणना की अनुमति देता है n के बड़े मानों के लिए। इसके अलावा, यदि , तब एक विभाज्यता क्रम है.
अन्य विभाज्यता गुण इस प्रकार हैं:[1]
- अगर तो समता (गणित) है विभाजित .
- मान लीजिए N, 2Q के सापेक्ष एक अभाज्य पूर्णांक है। यदि सबसे छोटा धनात्मक पूर्णांक r जिसके लिए N विभाजित होता है मौजूद है, तो n का वह सेट जिसके लिए N विभाजित होता है बिल्कुल r के गुणजों का समुच्चय है।
- यदि P और Q समता (गणित) हैं, तो को छोड़कर सदैव सम होते हैं .
- यदि P सम है और Q विषम है, तो समता (गणित) की n और के समान है सदैव सम रहता है.
- यदि P विषम है और Q सम है, तो के लिए हमेशा अजीब होते हैं .
- यदि P और Q विषम हैं, तो सम हैं यदि और केवल यदि n, 3 का गुणज है।
- यदि p एक विषम अभाज्य है, तो (लेजेन्ड्रे प्रतीक देखें)।
- यदि p एक विषम अभाज्य है और P और Q को विभाजित करता है, तो p विभाजित होता है हरएक के लिए .
- यदि p एक विषम अभाज्य है और P को विभाजित करता है लेकिन Q को नहीं, तो p विभाजित करता है यदि और केवल यदि n सम है।
- यदि p एक विषम अभाज्य है और P को नहीं बल्कि Q को विभाजित करता है, तो p कभी भी विभाजित नहीं होता है के लिए .
- यदि p एक विषम अभाज्य है और PQ को नहीं बल्कि D को विभाजित करता है, तो p विभाजित होता है यदि और केवल यदि p, n को विभाजित करता है।
- यदि p एक विषम अभाज्य है और PQD को विभाजित नहीं करता है, तो p विभाजित होता है , कहाँ .
अंतिम तथ्य फ़र्मेट के छोटे प्रमेय का सामान्यीकरण करता है। इन तथ्यों का उपयोग लुकास-लेहमर प्राइमलिटी परीक्षण में किया जाता है। अंतिम तथ्य का व्युत्क्रम (तर्क) मान्य नहीं है, जैसे फ़र्मेट के छोटे प्रमेय का व्युत्क्रम मान्य नहीं है। D और विभाजक के सापेक्ष एक भाज्य संख्या n मौजूद है , कहाँ . ऐसे सम्मिश्रण को लुकास स्यूडोप्राइम कहा जाता है।
लुकास अनुक्रम में किसी पद का एक अभाज्य कारक जो अनुक्रम में किसी भी पहले के पद को विभाजित नहीं करता है उसे आदिम कहा जाता है। कारमाइकल के प्रमेय में कहा गया है कि लुकास अनुक्रम में सभी लेकिन सीमित रूप से कई शब्दों में एक आदिम अभाज्य कारक होता है।[2] दरअसल, कारमाइकल (1913) ने दिखाया कि यदि डी सकारात्मक है और एन 1, 2 या 6 नहीं है, तो एक आदिम अभाज्य कारक है. मामले में डी नकारात्मक है, बिलु, हनरोट, वाउटियर और मिग्नोटे का गहरा परिणाम है[3] दर्शाता है कि यदि n > 30, तो एक आदिम अभाज्य कारक है और सभी मामलों को निर्धारित करता है कोई आदिम अभाज्य गुणनखंड नहीं है.
विशिष्ट नाम
P और Q के कुछ मानों के लिए लुकास अनुक्रमों के विशिष्ट नाम हैं:
- Un(1, −1) : फाइबोनैचि संख्याएँ
- Vn(1, −1) : लुकास नंबर
- Un(2, −1) : नंबर पेलें
- Vn(2, −1) : पेल-लुकास नंबर (साथी पेल नंबर)
- Un(1, −2) : जैकबस्थल संख्याएँ
- Vn(1, −2) : जैकबस्थल-लुकास संख्याएँ
- Un(3, 2): मेर्सन संख्या 2n− 1
- Vn(3, 2) : फॉर्म के नंबर 2n + 1, जिसमें फ़र्मेट नंबर शामिल हैं[2]:Un(6, 1) : वर्ग त्रिकोणीय संख्याओं का वर्गमूल।
- Un(x, −1) : फाइबोनैचि बहुपद
- Vn(x, −1) : लुकास बहुपद
- Un(2x, 1) : दूसरी तरह के चेबीशेव बहुपद
- Vn(2x, 1) : पहली तरह के चेबीशेव बहुपद को 2 से गुणा किया गया
- Un(x+1, x) : आधार x में पुनर्पुनित करता है
- Vn(x+1, x) : एक्सn + 1
कुछ लुकास अनुक्रमों की पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में प्रविष्टियाँ हैं:
−1 3 OEIS: A214733 1 −1 OEIS: A000045 OEIS: A000032 1 1 OEIS: A128834 OEIS: A087204 1 2 OEIS: A107920 OEIS: A002249 2 −1 OEIS: A000129 OEIS: A002203 2 1 OEIS: A001477 2 2 OEIS: A009545 OEIS: A007395 2 3 OEIS: A088137 2 4 OEIS: A088138 2 5 OEIS: A045873 3 −5 OEIS: A015523 OEIS: A072263 3 −4 OEIS: A015521 OEIS: A201455 3 −3 OEIS: A030195 OEIS: A172012 3 −2 OEIS: A007482 OEIS: A206776 3 −1 OEIS: A006190 OEIS: A006497 3 1 OEIS: A001906 OEIS: A005248 3 2 OEIS: A000225 OEIS: A000051 3 5 OEIS: A190959 4 −3 OEIS: A015530 OEIS: A080042 4 −2 OEIS: A090017 4 −1 OEIS: A001076 OEIS: A014448 4 1 OEIS: A001353 OEIS: A003500 4 2 OEIS: A007070 OEIS: A056236 4 3 OEIS: A003462 OEIS: A034472 4 4 OEIS: A001787 5 −3 OEIS: A015536 5 −2 OEIS: A015535 5 −1 OEIS: A052918 OEIS: A087130 5 1 OEIS: A004254 OEIS: A003501 5 4 OEIS: A002450 OEIS: A052539 6 1 OEIS: A001109 OEIS: A003499
अनुप्रयोग
- लुकास अनुक्रमों का उपयोग संभाव्य लुकास स्यूडोप्राइम परीक्षणों में किया जाता है, जो आमतौर पर इस्तेमाल किए जाने वाले बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण का हिस्सा हैं।
- लुकास अनुक्रमों का उपयोग कुछ प्रारंभिक प्रमाण विधियों में किया जाता है, जिनमें लुकास-लेहमर-रीज़ल परीक्षण, और एन+1 और हाइब्रिड एन−1/एन+1 विधियां जैसे ब्रिलहार्ट-लेहमर-सेल्फ्रिज 1975 शामिल हैं।[4]
- LUC लुकास अनुक्रमों पर आधारित एक सार्वजनिक-कुंजी क्रिप्टोसिस्टम है[5] जो एलगमाल (LUCELG), डिफी-हेलमैन (LUCDIF), और RSA (एल्गोरिदम) (LUCRSA) के एनालॉग्स को लागू करता है। एलयूसी में संदेश के एन्क्रिप्शन की गणना आरएसए या डिफी-हेलमैन जैसे मॉड्यूलर घातांक का उपयोग करने के बजाय, कुछ लुकास अनुक्रम के शब्द के रूप में की जाती है। हालाँकि, ब्लेइचेनबैकर एट अल द्वारा एक पेपर।[6] दर्शाता है कि मॉड्यूलर एक्सपोनेंटिएशन पर आधारित क्रिप्टोसिस्टम पर एलयूसी के कई कथित सुरक्षा लाभ या तो मौजूद नहीं हैं, या उतने पर्याप्त नहीं हैं जितना दावा किया गया है।
यह भी देखें
- लुकास स्यूडोप्राइम
- फ्रोबेनियस स्यूडोप्राइम
- सोमर-लुकास स्यूडोप्राइम
टिप्पणियाँ
- ↑ For such relations and divisibility properties, see (Carmichael 1913), (Lehmer 1930) or (Ribenboim 1996, 2.IV).
- ↑ 2.0 2.1 Yabuta, M (2001). "आदिम भाजक पर कारमाइकल के प्रमेय का एक सरल प्रमाण" (PDF). Fibonacci Quarterly. 39: 439–443. Retrieved 4 October 2018.
- ↑ Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). "लुकास और लेहमर संख्याओं के आदिम भाजक का अस्तित्व" (PDF). J. Reine Angew. Math. 2001 (539): 75–122. doi:10.1515/crll.2001.080. MR 1863855. S2CID 122969549.
- ↑ John Brillhart; Derrick Henry Lehmer; John Selfridge (April 1975). "New Primality Criteria and Factorizations of 2m ± 1". Mathematics of Computation. 29 (130): 620–647. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 2005583.
- ↑ P. J. Smith; M. J. J. Lennon (1993). "LUC: A new public key system". Proceedings of the Ninth IFIP Int. Symp. On Computer Security: 103–117. CiteSeerX 10.1.1.32.1835.
- ↑ D. Bleichenbacher; W. Bosma; A. K. Lenstra (1995). "लुकास-आधारित क्रिप्टोसिस्टम पर कुछ टिप्पणियाँ" (PDF). Lecture Notes in Computer Science. 963: 386–396. doi:10.1007/3-540-44750-4_31. ISBN 978-3-540-60221-7.
संदर्भ
- Carmichael, R. D. (1913), "On the numerical factors of the arithmetic forms αn±βn", Annals of Mathematics, 15 (1/4): 30–70, doi:10.2307/1967797, JSTOR 1967797
- Lehmer, D. H. (1930). "An extended theory of Lucas' functions". Annals of Mathematics. 31 (3): 419–448. Bibcode:1930AnMat..31..419L. doi:10.2307/1968235. JSTOR 1968235.
- Ward, Morgan (1954). "Prime divisors of second order recurring sequences". Duke Math. J. 21 (4): 607–614. doi:10.1215/S0012-7094-54-02163-8. hdl:10338.dmlcz/137477. MR 0064073.
- Somer, Lawrence (1980). "The divisibility properties of primary Lucas Recurrences with respect to primes" (PDF). Fibonacci Quarterly. 18: 316.
- Lagarias, J. C. (1985). "The set of primes dividing Lucas Numbers has density 2/3". Pac. J. Math. 118 (2): 449–461. doi:10.2140/pjm.1985.118.449. MR 0789184.
- Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. Vol. 126 (2nd ed.). Birkhäuser. pp. 107–121. ISBN 0-8176-3743-5.
- Ribenboim, Paulo; McDaniel, Wayne L. (1996). "The square terms in Lucas Sequences". J. Number Theory. 58 (1): 104–123. doi:10.1006/jnth.1996.0068.
- Joye, M.; Quisquater, J.-J. (1996). "Efficient computation of full Lucas sequences" (PDF). Electronics Letters. 32 (6): 537–538. Bibcode:1996ElL....32..537J. doi:10.1049/el:19960359. Archived from the original (PDF) on 2015-02-02.
- Ribenboim, Paulo (1996). The New Book of Prime Number Records (eBook ed.). Springer-Verlag, New York. doi:10.1007/978-1-4612-0759-7. ISBN 978-1-4612-0759-7.
- Ribenboim, Paulo (2000). My Numbers, My Friends: Popular Lectures on Number Theory. New York: Springer-Verlag. pp. 1–50. ISBN 0-387-98911-0.
- Luca, Florian (2000). "Perfect Fibonacci and Lucas numbers". Rend. Circ Matem. Palermo. 49 (2): 313–318. doi:10.1007/BF02904236. S2CID 121789033.
- Yabuta, M. (2001). "A simple proof of Carmichael's theorem on primitive divisors" (PDF). Fibonacci Quarterly. 39: 439–443.
- Benjamin, Arthur T.; Quinn, Jennifer J. (2003). Proofs that Really Count: The Art of Combinatorial Proof. Dolciani Mathematical Expositions. Vol. 27. Mathematical Association of America. p. 35. ISBN 978-0-88385-333-7.
- Lucas sequence at Encyclopedia of Mathematics.
- Weisstein, Eric W. "Lucas Sequence". MathWorld.
- Wei Dai. "Lucas Sequences in Cryptography".